了解二进制搜索树构造

Question

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

Answer 1

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

1. 插入元素的顺序,以及
2. 树在插入期间执行的平衡操作(如果有).

如果您的纯二进制搜索树没有任何重新平衡逻辑,那么插入元素的顺序将对树的形状产生强烈影响.例如,取值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中.

希望这可以帮助!