标签: binary-search-tree

我认为我知道答案,最小的复杂性是O(nlogn).

但是,有没有什么办法可以在O(n)复杂度中从堆中创建二进制搜索树？

我知道,BST不允许重复.例如,如果我有一个单词"RABSAB".

上述字符串的二进制搜索树是:

    R
    /\
   A  S
    \
     B

如果我们想在树中包含重复项,该怎么办？树怎么会改变？我在接受采访时被问到这个问题.

他们让我画画:

1. 二叉树
2. 不平衡的二进制搜索树
3. 没有重复的二叉搜索树
4. 带有重复项的二叉搜索树

任何帮助表示赞赏!

PS:通过绘制相关树帮助我

可能重复:
确定两个二叉树是否相等

昨天接受采访,一个问题让我,这里是:

描述

有2 binary trees,检查他们是否平等.

当且仅当tree1->child == tree2->child一棵树左右时,它们是相等的children can be swapped with each other.

例如:

    5     6
   / \   / \           they are equal.
   1 2   2  1

    5         6
   / \       / \           they are equal.
  1   2     2   1
 /     \   /    / 
3       4 4     3

任何想法都表示赞赏.

我需要从CLRS算法书中获得这个练习的提示:

证明无论我们在高度-h二进制搜索树中从哪个节点开始,对Tree-Successor的k次连续调用都需要O(k + h)时间.

我正在学习左倾红黑树.

在本文提出的删除算法中,如果密钥匹配节点并且该子节点的右子树为NULL,则删除该节点.但是可能还有一个左子树也没有考虑.

我无法理解为什么左子树也是NULL.删除最小值或最大值时也会执行类似的操作.有人可以指导我吗？

给定一组值,可以存在许多可以由这些值形成的不同的可能二进制搜索树.例如,对于值1,2和3,我们可以从这些值中生成五个BST:

1      1      2      3      3
 \      \    / \    /      /
  2      3  1   3  1      2
   \    /           \    /
    3  2             2  1

许多基于平衡二叉搜索树的数据结构使用树旋转作为重构BST的原语,而不会破坏所需的二进制搜索树不变量.树旋转可用于将节点拉到其父节点之上,如下所示:

                rotate
         u      right           v
        / \     ----->         / \
       v   C                  A   u
      / \       <-----           / \
     A   B      rotate          B   C
                 left

给定一个包含一组值的BST,是否总是可以将该BS​​T转换为任意其他BST用于同一组值？例如,我们是否可以仅使用树旋转将上述五个BST中的任何一个转换为任何其他BST？

我试图理解删除二叉搜索树的递归方法是如何工作的.我在许多地方遇到的代码如下所示:

void destroy_tree(struct node *leaf)
{
  if( leaf != 0 )
  {
      destroy_tree(leaf->left);
      destroy_tree(leaf->right);
      free( leaf );
  }
}

我无法理解a)如果例程中没有返回,它是如何工作的？b)当free()被调用时？我想想,例如,这样一棵树:

                           10
                         /    \
                        6      14
                       / \    /  \
                      5   8  11  18

所以我的理解是我遍历10-> 6-> 5,然后我调用destroy_tree(5->左).因此,leaf if if为NULL,并且if-dependent不执行,因此5不被删除.我在哪里弄错了这个推理？如何在这里进行卷绕和退绕？任何帮助都很感激:-)

好的,我想要一个二元搜索树来平衡,我知道为什么它不起作用,但我不知道如何解决它.这就是我的平衡方法.

    public void balance(){
    if(isEmpty()){
        System.out.println("Empty Tree");
        return;
    }
    if(!isEmpty()){
        values = new Object[count()];
        index = 0;
        createAscendingArray(root);
        clear();
        balanceRecursive(0, index);
                    values = null;
    }


}

private void createAscendingArray(TreeNode<E> current){
    if(current == null)
        return;
    if(current.getLeftNode() != null)
        createAscendingArray(current.getLeftNode());
    else if(current.getRightNode() != null)
        createAscendingArray(current.getRightNode());
    values[index] = current.getData();
    index++;


}

private void balanceRecursive(int low, int high){
    if(low == high)
        return;
    else if(low > high/2)
        balanceRecursive(high/2, high);
    else if(low < high/2)
        balanceRecursive(low, high/2);  

    E insert = (E) values[(low + high)/2];
    insertItem(insert);

}

为了增加一些清晰度,index是预定义的私有int变量,values也是预定义的Object …

假设我有一个std::map<int, std::string> myMap包含数据的

1. Red
2. Blue
3. Green
5. Fuchsia
6. Mauve
9. Gamboge
10. Vermillion

还有一个std::map<int, std::string>::iterator it指向元素

5. Fuchsia

我想做类似的事情（编造）

std::map<int, std::string> myHead = eject(myMap, myMap.begin(), it);

这将导致myMap包含

5. Fuchsia
6. Mauve
9. Gamboge
10. Vermillion

并myHead包含

1. Red
2. Blue
3. Green

我可以通过做类似的事情来实现这一点

std::map<int, std::string> myHead;
myHead.insert(myMap.begin(), it);
myMap.erase(myMap.begin(), it);

但这至少在某些情况下似乎不是最理想的，例如，如果我选择了一个点，以至于我只是从子树中分离出来。（我承认我实际上并没有仔细考虑这里算法复杂性的实际细节，但是如果我们想象一个值类型复制成本非常高的情况，那么很明显，上面的一般情况下不可能是最优的.)

问题：有没有办法std::map以最佳方式执行此操作，或者我是否必须编写自己的二叉搜索树来访问内部结构来完成此操作？

我正在观看关于算法的大学讲座，似乎其中许多课程几乎完全依赖某种特定类型的二叉搜索树来进行查询/数据库/搜索任务。

我不明白这种对Binary Search Trees 的痴迷。似乎在绝大多数情况下，在静态数据的情况下，BSP 可以用排序数组替换，如果插入动态发生，则可以用排序的桶列表替换，然后可以对它们进行二分搜索。

通过这种方法，你会得到相同的算法复杂性（至少查询）为BST，方式更好的高速缓存一致性，这样少的内存碎片（取决于你是用什么语言少GC allocs），并有可能要简单得多写。

基本问题是 BSP 完全没有内存——他们的重点完全是 O(n) 复杂性，他们忽略了内存碎片和缓存一致性的非常真实的性能考虑......我错过了什么吗？