我很难理解二叉搜索树是如何构建的。他们是否需要对初始数据进行排序才能找到最顶层的根?
问问题
6693 次
1 回答
8
二叉搜索树的形状取决于两件事:
- 插入元素的顺序,以及
- 树在插入过程中做了什么平衡操作(如果有的话)。
如果您有一个没有任何重新平衡逻辑的纯二叉搜索树,那么插入元素的顺序将对树的形状产生很大影响。例如,取值 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。
希望这可以帮助!
于 2013-06-19T20:39:18.613 回答