标签: binary-search-tree

我听说过一种新的平衡 BST 数据结构，称为zip 树。什么是zip树？它是如何工作的？

这是一个面试问题.在BST中找到第二个最大值.

最大元素是BST中最右边的叶子.第二个最大值是其父或其左子.因此解决方案是遍历BST以找到最右边的叶子并检查其父和左子.

是否有意义？

我可以看到,当在BST中查找值时,每次我们将节点与我们要查找的值进行比较时,我们会将树的一半留下.

但是,我不明白时间复杂性的原因O(log(n)).所以,我的问题是:

如果我们有一个N元素的树,为什么查找树并检查特定值是否存在的时间复杂度为O(log(n)),我们如何得到它？

我不需要代码,只需要解释.我的教科书说

级别顺序:级别i的每个节点在级别i + 1的任何节点之前被处理

我对广度优先搜索的理解是你从左边开始首先探索离根最近的节点？这有什么不同？这是一个方形和矩形的情况吗？

给定二叉搜索树和整数K,我想找到小于K的最大元素.

在下面的树中,

for K = 13, result = 12
for K = 10, result = 8
for K = 1 (or) 2, result = -1

      10

  5       12

2   8   11  14

我尝试了以下逻辑.但有没有更好的方法呢？

int findNum(node* node, int K)
{
        if(node == NULL)
        {
                return -1;
        }
        else if(K <= node->data)
        {
                return findNum(node->left,K);
        }
        else if(K > node->data)
        {
                int t = findNum(node->right,K);
                return t > node->data ? t : node->data;
        }

        return -1;
}

我正在学习关于数据库的类中的B +树,我想知道B +树对二元搜索树有什么具体优势？

对于大多数笔记操作来说,它们似乎都具有O(logN)平均复杂度,但B +树在每个子节点上还有一个额外的(可忽略的？)搜索时间,其中BST显然只花费O(1)时间来确定哪个子节点前进到.

现实世界的优势使B +树在数据库中比BST更受欢迎？

之前的这个问题询问了将值1-7插入到二叉搜索树中的方法有多少,这将导致以下树:

       4
     /   \
    2     6
   / \   / \
  1   3 5   7

(顺便说一句,答案是80).

更一般地假设您获得了一个包含一组值的任意BST,并且想知道有多少可能的方法将这些值插入到最终生成结果树的BST中.有没有一种有效的算法来确定这个？

谢谢!

在Python 2.7或Python 3.x中是否存在任何自平衡二叉搜索树(RED-BLACK,AVL或其他)内置类型？

我正在寻找与Java的TreeMap或TreeSet等效的东西.

如果没有这样的内置插件,他们为什么会被忽略？是否有特殊原因,因为不包括此类工具？

从我对Haskell的有限知识来看,似乎Maps(来自Data.Map)应该像其他语言中的字典或散列表一样使用,但它们被实现为自平衡二进制搜索树.

为什么是这样？使用二叉树将查找时间减少到O(log(n))而不是O(1),并且要求元素在Ord中.当然有一个很好的理由,那么使用二叉树有什么好处呢？

也:

在什么应用程序中,二叉树比哈希表更差？反过来呢？在许多情况下,一个人会比另一个人更受欢迎吗？Haskell中是否有传统的哈希表？

我使用以下方法遍历*300 000级别的二叉树:

Node* find(int v){
   if(value==v)
      return this;
   else if(right && value<v)
      return right->find(v); 
   else if(left && value>v)
      return left->find(v);
}

但是由于堆栈溢出,我得到了分段错误.关于如何在没有递归函数调用开销的情况下遍历深层树的任何想法？

*"遍历"我的意思是"搜索具有给定值的节点",而不是完整的树遍历.