data-structures - 了解二叉搜索树的构造

Question

我很难理解二叉搜索树是如何构建的。他们是否需要对初始数据进行排序才能找到最顶端的根？

Answer 1

二叉搜索树的形状取决于两件事:

元素插入的顺序，以及

树在插入期间执行哪些平衡操作(如果有)。

如果您有一个没有任何重新平衡逻辑的纯二叉搜索树，那么插入元素的顺序将对树的形状产生很大的影响。例如，取值 1、2、3、4、5、6、7。如果按照 4、2、6、1、3、5、7 的顺序插入它们，您将得到这棵树:

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

这样做的原因是我们经历了以下一系列树:

     4

     4
   /
  2

     4
   /   \
  2     6 

     4
   /   \
  2     6
 /
1

     4
   /   \
  2     6
 / \
1   3

     4
   /   \
  2     6
 / \   /
1   3 5

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

另一方面，如果按 1、2、3、4、5、6、7 的顺序插入值，则会得到这棵树:

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

有趣的是，以排序的顺序将元素插入 BST 是您可以为树做的最糟糕的事情之一，因为它使树成为线性结构。您最好选择要插入的元素的随机排列，或者(如果事先知道它们)对它们进行排序并在排序序列上使用以下递归算法:

如果没有元素，你就完成了。

除此以外:

将中位数插入 BST。

将元素的前半部分递归插入到 BST 中。

将元素的后半部分递归插入到 BST 中。

希望这可以帮助!