标签: binary-search-tree

任何人都可以用一个例子解释二叉树和二叉搜索树 之间的区别吗？

为什么std::map实现为红黑树？

那里有几个平衡的二叉搜索树(BST).选择红黑树的设计权衡是什么？

堆和BST有什么区别？

何时使用堆以及何时使用BST？

如果你想以排序的方式获取元素,BST是否优于堆？

二进制搜索树比哈希表有什么优势？

哈希表可以在Theta(1)时间查找任何元素,并且添加元素也同样容易....但我不确定反过来的优势.

我在这里读到了一个名为验证二叉搜索树的访谈练习.

这究竟是如何工作的？在验证二叉搜索树时会有什么需要？我写了一个基本的搜索树,但从未听说过这个概念.

参考: 我被问到这个问题@MS SDE采访,第3轮.这不是一个家庭作业问题.我也考虑了一下,并在下面提到了我的方法.

问题: 修改BST以使其尽可能平衡.不用说,你应该尽可能高效地做到这一点.

提示: 采访者说这是一个合乎逻辑的问题,如果你有不同的想法,你会得到答案.没有困难的编码.
- >话虽如此,我认为他不指望我指向AVL/RB树.

我的解决方案: 我提出,我会按顺序遍历树,将中间元素作为新树的根(让我们称之为新的根).然后转到中间元素的左侧部分,将其中间元素作为树根新子根的左子树的根.同样适用于正确的部分.递归地执行此操作将提供最佳平衡BST.

我为什么要在这里张贴它: 但他对答案不满意:(那么,有没有办法做这个没有用于权重/ RB着色策略,还是他只是和我一起鬼混？请放入你的专家想法.

重复？没有! 我知道有这个问题但是请求者提出的解决方案太复杂了,而另一个讨论了AVL树.

我正在研究各种树木,并遇到了AVL树木和树木.我想知道

1. AVL树和splay树有什么区别？
2. 我们在什么基础上选择这些发辫？
3. 这些树的积极和消极是什么？
4. 这些树的大O符号表现如何？

链接列表和BinarySearchTree之间的主要区别是什么？BST只是维护LinkedList的一种方式吗？我的导师谈到了LinkedList,然后讨论了BST,但没有比较它们或者没有说何时更喜欢一个而不是另一个.这可能是一个愚蠢的问题,但我真的很困惑.如果有人能够以简单的方式澄清这一点,我将不胜感激.

这是我到目前为止所得到的但它不起作用:

class Node:
    rChild,lChild,data = None,None,None

    def __init__(self,key):
        self.rChild = None
        self.lChild = None
        self.data = key

class Tree:
    root,size = None,0
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self,node,someNumber):
        if node is None:
            node = Node(someNumber)
        else:
            if node.data > someNumber:
                self.insert(node.rchild,someNumber)
            else:
                self.insert(node.rchild, someNumber)
        return

def main():
    t = Tree()
    t.root = Node(4)
    t.root.rchild = Node(5)
    print t.root.data #this works
    print t.root.rchild.data #this works too
    t = Tree()
    t.insert(t.root,4)
    t.insert(t.root,5)
    print t.root.data #this fails
    print t.root.rchild.data …

今天我接受采访时,我被要求编写一个程序,该程序采用二叉树,如果它也是二进制搜索树则返回true,否则为false.

我的方法1:执行有序遍历并将元素存储在O(n)时间内.现在扫描数组/元素列表并检查^第 i ^个索引处的元素是否大于^第(i + 1)^个索引处的元素.如果遇到这种情况,则返回false并退出循环.(这需要O(n)时间).最后回归真实.

但这位先生希望我提供一个有效的解决方案.我尝试但是我没有成功,因为要查找它是否是BST我必须检查每个节点.

而且他指着我思考递归.我的方法2:如果对于任何节点N N>左<N和N>右> N,并且N的左节点的有序后继小于N并且有序后继,则BT是BST N的右节点大于N,左右子树是BST.

但这会很复杂,而且运行时间似乎并不好.如果您知道任何最佳解决方案,请帮忙.