了解二进制搜索树构建

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是o 最糟糕的你可以为树做的事情，因为它使树成为线性结构。你最好挑选元素的随机排列插入，或对它们进行分类，并使用在排序序列中的下列递归算法（如果他们事先所有已知）：

• 如果没有的元素，你完成了。
• 否则：
  • 将中位数插入BST。
  • 将前半部分元素递归地插入到BST中。
  • 以递归方式将第二部分元素插入到BST中。

希望这有助于！ “