算法和数据结构1.8二叉查找树

二叉查找树（二叉搜索树或二叉排序树）是一种数据结构。采用了图的树形结构。数据存储于二叉查找树的各个结点中。

二叉查找树的示例如下图：结点中的数字就是存的数据。（这里以不存在相同的数字为例）

1.png

二叉查找树性质：

1.每个结点的值大于其左树上任意结点的值
2.每个结点的值小于其右树上任意结点的值

比如9大于其左树上的3和8。

根据这两个性质可以得出结论：
二叉查找树的最小结点从顶端开始，往其左树的末端寻找。此处最小值是3。
二叉查找树的最大结点从顶端开始，网右树的末端寻找。此处的最大值是28。

二叉树添加数据：

假设往当前二叉树里面添加一个数据，比如添加数字1。

2.png

先从顶端开始比较：
因为 1 < 15 ,所以往左下位置继续寻找

3.png

接下来和9比较，因为1 < 9 ，所以继续往左下位置寻找

4.png

接下来和和3比较，因为1 < 3 ,所以继续向左下位置寻找

5.png

最终左下没有值了，得到的结果是

6.png

接下来操作再添加一位数字4

7.png

先将4和15比较4 < 15 ,往左树寻找

8.png

4 < 9 ,再往左树寻找，
4 > 3 ,往右树寻找，

9.png

4 < 8 ,将4添加到8的左树位置，添加完成。

12.png 11.png

二叉树删除数据

尝试性删除结点28，

10.png

删除结果如下图

13.png

下面尝试删除带子节点的结点8

14.png

删除之后效果

15.png

下面删除带子树的节点9

16.png

删除之后，先将左树上最大结点4放在被删除的结点位置（这里树的结构没有达到最优解，那么还需要继续递归调整结点的操作）

（备注说明：将左树中的最大结点和右树中的最小结点放在9的原有置都可以）

当前情况下将4放在该位置已经是最优解，因此不用再做调整。

17.png

数据查找：

查找数据也是从顶端开始和被查找值的大小进行对比，12 < 15 ,所以需要查找左树。

18.png

12 > 4 ,查找右树

19.png

到此查到结束。

时间计算

因为二叉查找树有前面两个性质，所以在查找数据或者寻找合适添加数据位置时候，只要将其和现有数据比较大小，就可以根据比较结果得知该往那边移动了。

比较的次数取决于树的高度。所以如果结点数目为n,而且树比较均衡，比较大小和移动的次数最多就是log₂n

因此时间复杂度为O（logn）。但是，如果树的形状朝单侧纵向延伸，树就变得很高，此时的时间复杂度就变成了O（n）。

应用

有很多以二叉查找树为基础的扩展数据结构。比如“平衡二叉查找树”。这种结构可以修正形状不均衡的树，让其始终保持均衡的形态，以提高查找效率。

虽然二叉查找树中的一个结点最多有两个子结点，但我们可以把子结点数扩展为m.

像这种结点数可以自由设定，并且形状均衡的树叫做B树。