《我的第一本算法书》阅读笔记 1-8 二叉查找树

Dear 丶 2022-10-22 04:19 111阅读 0赞

**目录**

二叉查找树性质

插入数据——插入1

插入数据——插入4

删除节点——节点无子结点的情况

删除节点——有一个字节点的情况

删除节点——节点有子树的情况

查找结点

解说

补充说明

来源

--------------------

二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，采用了图的树形结构 （关于树形结构的详细说明请参考 4-2 节）。数据存储于二叉查找树的各个结点中。

--------------------

### 二叉查找树性质 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

这就是二叉查找树的示例。结点中的数字便是存储的数据。此处以不存在相同数字为前提进行说明。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

二叉查找树有两个性质。第一个是每个结点的值均大于其左子树上任意一个结点的值。比如 结点9大于其左子树上的3和8。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

同样，结点15也大于其左子树上任意一个结点的值。

![20210403213103989.png][]

第二个是每个结点的值均小于其右子树上任意一个结点的值。比如结点 15 小于其右子树上的 23、17和28。

![2021040321333477.png][]

根据这两个性质可以得到以下结论。首先，二 叉查找树的最小结点要从顶端开始，往其左下的末端寻找。此处最小值为3。

![20210403213401900.png][]

反过来，二叉查找树的最大结点要从顶端开 始，往其右下的末端寻找。此处最大值为28。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

### 插入数据——插入1 ###

下面我们来试着往二叉查找树中添加数据。比如添加数字1。

![20210403213434509.png][]

首先，从二叉查找树的 顶端结点开始寻找添加 数字的位置。将想要添 加的1与该结点中的值 进行比较，**小于它则往左移，大于它则往右移**。

![20210403213514795.png][]

由于1＜9，所以将1往左移.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4][]

由于1＜3，所以继续将1往左移，但前面已经没有结点了，所以把 1 作为新结点添加到左下方。

![20210403213600287.png][]

这样，1的添加操作便完成了.

![20210403213614335.png][]

--------------------

### 插入数据——插入4 ###

接下来，我们再试试添加数字4。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5][]

和前面的步骤一样， 首先从二叉查找树 的顶端结点开始寻找添加数字的位置。

![20210403213650813.png][]

由于4＜9，所以将其往左移.

![20210403213705284.png][]

由于4＞3，所以将其往右移。

![20210403213719909.png][]

由于4＜8，所以需要将其往左移，但前面已经没 有结点了，所以把 4 作为新结点添加到左下方。

![20210403213736440.png][]

于是4的添加操作也完成了

--------------------

### 删除节点——节点无子结点的情况 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6][]

接下来看看如何在二叉查找树中删除结点。比如我们来试试删除结点28

![20210403213806536.png][]

如果需要删除的结点没有子结点，直接删掉该结点即可。

--------------------

### 删除节点——有一个字节点的情况 ###

![20210403213827652.png][]

再试试删除结点8。

![20210403213858132.png][]

如果需要删除的结点只有一个子结点，那么先 删掉目标结点……

![20210403213920692.png][]

然后把子结点移到被删除结点的位置上即可。

--------------------

### 删除节点——节点有子树的情况 ###

![20210403213942916.png][]

最后来试试删除结点9

![20210403213955191.png][]

如果需要删除的结点有两个子结点，那么先删 掉目标结点……

![2021040321401621.png][]

然后在被删除结点的左子树中寻找最大结点……

(Tips :  删除9的时候，我们将“左子树中的最大结点”移动到了删除结点的位置上，但是根据二叉查找树的性质可知，移动“**右子树中的最小结点**”也没有问题。)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7][]

最后将最大结点移到被删除结点的位置上。这样一来，就能在满足二叉查找树性质的前提下删除结点了。 如果需要移动的结点（此处为4）还有子结点，就递归执行前面的操作（关于递归，请参照7-4节的内容）。

--------------------

### 查找结点 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 8][]

下面来看看如何在二叉查找树中查找结点。比 如我们来试试查找12。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 9][]

从二叉查找树的顶端结点开始往下查找。和添 加数据时一样，把12和结点中的值进行比较， 小于该结点的值则往左移，大于则往右移。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 10][]

由于12＞4，所以往右移。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 11][]

找到结点12了。

### 解说 ###

我们可以把二叉查找树当作是二分查找算法思想的树形结构体现（二分查找的详细 说明在 3-2 节）。因为它具有前面提到的那两个性质，所以在查找数据或寻找适合添加 数据的位置时，只要将其和现有的数据比较大小，就可以根据比较结果得知该往哪边移 动了。

比较的次数取决于树的高度。所以如果结点数为 n，而且树的形状又较为均衡的话， 比较大小和移动的次数最多就是 log2n。因此，时间复杂度为 O(logn)。但是，如果树的 形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了 O(n)。

### 补充说明 ###

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

另外，虽然文中介绍的二叉查找树中一个结点最多有两个子结点，但我们可以把**子结点数扩展为 m**（m 为预先设定好的常数）。像这种**子结点数可以自由设定**，**并且形状均衡**的树便是 **B 树**。

### 来源 ###

《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/9d7d4b160cd446c3b4b312872fab2df4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/a6390f3df2ee492a82e3ef73e2ee7a2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20221022/734d55f35bbc4b7c93cb11ac88d65bc7.png
[20210403213103989.png]: /images/20221022/5c2549f596654e59898305656cfff046.png
[2021040321333477.png]: /images/20221022/4a9a541f22b746e99720a10c58ace46f.png
[20210403213401900.png]: /images/20221022/6867241c028d4cd191ff224bc58afba2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: /images/20221022/038874073abe4a92a9a03e5fb8f76106.png
[20210403213434509.png]: /images/20221022/8f93a01fe8b04eaa98c635f4c59fb09d.png
[20210403213514795.png]: /images/20221022/894b01fbb90845cd9cd381d418923473.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: /images/20221022/61e81ba475d34b7e9afabbec32459734.png
[20210403213600287.png]: /images/20221022/7f9d3b74efd44fe793ad9ebadadc363f.png
[20210403213614335.png]: /images/20221022/5cb66fca79914701951ef3dc34ad1020.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5]: /images/20221022/435705f702fc42aeafc800acd4f6af1a.png
[20210403213650813.png]: /images/20221022/fd4a66f2f39846e2888af5e8841e536a.png
[20210403213705284.png]: /images/20221022/0c3aef8b00f74c358b7552418c156ddd.png
[20210403213719909.png]: /images/20221022/fc0cb67ca2de4f9ea40d81ddae51a37b.png
[20210403213736440.png]: /images/20221022/7e6bfc9c4e3a43a7b7ff6f010502db5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6]: /images/20221022/2328749636084b0e953e4c7a052981f0.png
[20210403213806536.png]: /images/20221022/0bbb4fbbf3d4466e96480ea1955c12de.png
[20210403213827652.png]: /images/20221022/868a63153eeb469d8484f5f04af0e4cd.png
[20210403213858132.png]: /images/20221022/8ed8e0ce34914b7796f99025db984b6e.png
[20210403213920692.png]: /images/20221022/f5032626fab14a8d9827689c9d50c1ca.png
[20210403213942916.png]: /images/20221022/dceacf5d3d9045aca2074bd950fac2c5.png
[20210403213955191.png]: /images/20221022/bda0a8b210174eb9974acb1c972caf78.png
[2021040321401621.png]: /images/20221022/766b404592a54aecb40ccf5cdb7c54ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7]: /images/20221022/156dc3a0f3da48d1a29fc0dea7df5dcb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 8]: /images/20221022/b465bd9e902145cb977993baa896f0a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 9]: /images/20221022/4ffe344939b64a529ee877e1e2ea8c20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 10]: /images/20221022/c2097709b9904f0c9d6481ccd0edf5ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 11]: /images/20221022/ebc8b0b8ec874aa3b1aa06be195debc7.png