_{王道C++班级参考资料}
——
C语言部分^卷5数据结构
^{_节5二叉搜索树}

最新版本V3.0
王道C++团队
COPYRIGHT ⓒ 2021-2024. 王道版权所有

二叉树

_Gn!

树是一种层次化的数据结构，它在现实生活和计算机科学中广泛存在并发挥重要作用。比如：

1. 族谱(Family Tree)

2. 组织架构

3. 计算机文件系统的目录结构

4. ...

树这种数据结构的特点，是从一个单一的根结点开始，分支出多个结点，每个结点又可能有自己的子结点，形成一个分层次的树状结构。

不过在众多的树形结构中，我们只学习二叉树，原因很简单，它很重要！

它有多重要呢？

单就面试而言，在 LeetCode 中二叉树相关的题目共有 300 多道，占据总题目的近三分之一。同时，二叉树在整个算法板块中还起到承上启下的作用：它不但是数组和链表的延伸，又可以作为图的基础。总之，非常重要！

那什么是二叉树(BinaryTree)呢？

二叉树的定义：二叉树是一棵树，并且二叉树的每个结点最多有两棵子树。二叉树的子树又分为左子树和右子树。

那二叉树长什么样呢？

上面是一个玩笑，实际上二叉树长这样：

从根结点开始，每个结点最多有两棵子树，这就是一棵"二叉树"。

二叉树有两种比较独特的形态：完全二叉树和满二叉树。

完全二叉树，若二叉树的深度为 h，除第 h 层外，其它各层(1～h-1)的结点数目都达到最大值，第 h 层的结点都连续排列在最左边，这样的二叉树就是完全二叉树。

满二叉树，每一层的结点数目都达到最大值(包括最下面一层)。

如下图所示：

以上，关于二叉树的一些概念就搞清楚了。下面我们来看一下今天学习的核心——二叉搜索树，它是一种特殊的二叉树。

二叉搜索树

_Gn!

什么是二叉搜索树(BinarySearchTree)呢？

二叉搜索树是一种特殊的二叉树，其中每个结点的左子树只包含小于当前结点的值，右子树只包含大于当前结点的值。

当然二叉搜索树的定义非常适合使用递归：

二叉搜索树是一种特殊的二叉树，从根结点开始，其每个结点都满足：

1. 左子树中的每个结点的值都小于该结点的值，并且左子树本身也是二叉搜索树

2. 右子树中的每个结点的值都大于该结点的值，并且右子树本身也是二叉搜索树

所以二叉搜索树在定义时就已经和递归绑定了，我们在下面处理二叉搜索树时，递归是常用的手段。

如下图所示：

需要注意的是，二叉搜索树只是在二叉树的基础上规定了结点取值的大小关系，二叉搜索树并不一定就是完全二叉树、满二叉树。

基本操作

_Gn!

我们可以用一个结构体描述二叉搜索树的某个结点：

二叉搜索树-结点结构体

​x
1
typedef int KeyType;
2

3
// 二叉搜索树的结点类型
4
typedef struct node {
5
 KeyType key;       // 结点key值,具有唯一性
6
 struct node *left; // 左子树
7
 struct node *right;    // 右子树
8
} TreeNode;

其中key决定了结点在树中的存储位置，也是搜索的凭证。所以出于简化操作的目的，大多二叉搜索树都会规定key是唯一的。

二叉搜索树最重要、基础的操作有以下：

1. 插入。向树中添加一个新的结点。这个操作需要保持二叉搜索树的性质，即插入的结点必须放置在保持左子结点小于父结点，且右子结点大于父结点的正确位置上。

2. 搜索。根据key查找目标结点。在二叉搜索树当中，搜索操作可以高效地进行，通过比较目标值与结点值来决定向左子树或右子树移动。搜索操作的实现是比较简单的。

3. 删除。根据key从树中删除某个结点。这是二叉搜索树中最复杂的操作。

4. 遍历。遍历树中的所有结点。常见的遍历方式有前序遍历、中序遍历、后序遍历以及层次遍历。其中，中序遍历二叉搜索树会得到一个有序的结点序列。

通过以上描述，不难看出：二叉搜索树在实现时，虽然和线性结构完全不同，但可以借鉴一部分链表的操作。

下面我们一起来实现一个二叉搜索树。

编写头文件

_Gn!

编写头文件的操作我们已经驾轻就熟了，这里我们创建一个头文件"BST.h"，然后将类型定义，函数声明等都放入这个头文件中：

实现二叉搜索树头文件-参考代码

xxxxxxxxxx
41
1
#ifndef BST_H
2
#define BST_H
3

4
#include<stdbool.h>
5

6
typedef int KeyType;
7

8
typedef struct node {
9
 KeyType key;       // 结点key值,具有唯一性
10
 struct node *left; // 左子树
11
 struct node *right;    // 右子树
12
} TreeNode;
13

14
// 推荐定义一个二叉搜索树的结构体,这样更便于扩展
15
typedef struct {
16
 TreeNode *root;    // 根结点指针
17
}BST;
18

19
// 基础操作
20
// 创建一棵空的BST
21
BST *bst_create();
22
// 销毁一棵BST
23
void bst_destroy(BST *tree);
24

25
// 根据key插入一个新结点
26
bool bst_insert(BST *tree, KeyType key);
27
// 根据key搜索某个结点并返回
28
TreeNode *bst_search(BST *tree, KeyType key);
29
// 根据key删除一个结点
30
bool bst_delete(BST *tree, KeyType key);
31

32
// 深度优先-先序遍历
33
void bst_preorder(BST *tree);   
34
// 深度优先-中序遍历
35
void bst_inorder(BST *tree);    
36
// 深度优先-后序遍历
37
void bst_postorder(BST *tree);  
38
// 广度优先-层次遍历
39
void bst_levelorder(BST *tree); 
40

41
#endif // !BST_H

也就是说，我们要实现一个如下图所示的二叉搜索树：

下面我们可以基于此头文件定义，来实现这个二叉搜索树。

实现创建操作

_Gn!

创建二叉搜索树的操作非常简单，也就是直接分配一个结构体对象就可以了。参考代码如下：

创建二叉搜索树-参考代码

xxxxxxxxxx
5
1
// 新建一棵空的二叉搜索树
2
BST *bst_create() {
3
 // 根结点指针自动初始化为NULL, 表示此树为空树
4
 return calloc(1, sizeof(BST));
5
}

注意：用calloc可以直接返回，因为它会自动初始化0值。如果用malloc，则不要忘记手动初始化根节点为NULL。

实现插入操作

_Gn!

插入操作的实现相对复杂一些，为了让大家更好的理清逻辑，我们就基于以下二叉搜索树来讲解：

假如我要插入一个Key为20的结点，那么怎么做才能够插入该结点而不破坏二叉搜索树的性质呢？

从大的思路上讲，只要分下述步骤就好了：

1. 根据二叉搜索树的结点规则，找到结点插入的位置。

2. 创建新结点，并初始化新结点。

3. 将新结点插入到目标位置。

非常简单，但具体而言：

1. 找到插入的位置，不仅要找到目标位置，还需要找到目标位置的父结点，因为二叉搜索树的搜索路径本质上就是一条单链表，而单链表只能在一个确定结点的后面插入新结点。在寻找插入位置时，若发现Key已存在，则不进行插入，插入失败。（要保证结点Key是唯一的）

2. 新结点的插入操作实际上就是在一个目标结点后面插入一个新结点。

于是，我们就可以完成这个插入操作。参考代码如下：

插入操作-参考代码

xxxxxxxxxx
58
1
/*
2
* 向二叉搜索树中新增一个结点
3
* 1.若key已存在，则不新增，插入失败
4
* 2.若key不存在，则进行新增，插入成功
5
*/
6
bool bst_insert(BST *tree, KeyType key) {
7
    // 1.遍历找到插入的位置
8
    // 初始化两个指针,一个用于找到插入位置,一个用于指向它的父结点
9
    TreeNode *parent = NULL;
10
    TreeNode *curr = tree->root;
11
    int diff;   // while循环一定执行,不用担心diff未初始化
12
    while (curr != NULL) {  // 此遍历就是为了查找NULL,curr最终等于NULL说明查找到了插入位置
13
        diff = key - curr->key;
14
        if (diff > 0) {
15
            // 待插入结点的key大于当前结点key
16
            // 向右遍历查找
17
            parent = curr;
18
            curr = curr->right;
19
        }
20
        else if (diff < 0)
21
        {
22
            // 待插入结点的key小于当前结点key
23
            // 向左遍历查找
24
            parent = curr;
25
            curr = curr->left;
26
        }
27
        else
28
        {
29
            // 待插入结点的key等于当前结点key
30
            // key重复,插入失败
31
            return false;
32
        }
33
    }   // 循环结束,说明curr是NULL,即key不重复,找到了插入的位置,parent指针指向待插入位置的父结点
34

35
    // 2.新建一个结点,初始化结点
36
    // 重要建议: 在二叉搜索树中新建结点,请一律使用calloc,安全第一!
37
    TreeNode *new_node = calloc(1, sizeof(TreeNode));
38
    if (new_node == NULL) {
39
        printf("calloc failed in bst_insert.\n");
40
        exit(1);
41
    }
42
    new_node->key = key;
43
    // 3.将新结点链接到二叉树上(链表的尾插)
44
    if (parent == NULL) {
45
        // 说明此时树是一个空树
46
        tree->root = new_node;  // 新结点成为根结点
47
        return true;    // 插入成功
48
    }
49
    // 插入的结点不是第一个结点
50
    if (diff < 0) {
51
        // 插入左子树
52
        parent->left = new_node;
53
    }else{
54
        // 插入右子树
55
        parent->right = new_node;
56
    }
57
    return true;
58
}

总得来说，插入操作还是比较简单的，基本上就是遍历链表，并且进行结点的插入操作。

下面我们来实现一下二叉搜索树的其它操作。

实现查询操作

_Gn!

先来实现一个简单的，在上面的插入操作当中，你实际上已经实现了查询操作。参考代码如下：

查询操作-参考代码

xxxxxxxxxx
26
1
// 根据key值来搜索一个结点，并将结点直接返回 
2
// 本质上就是带有条件的查找单链表结点
3
TreeNode *bst_search(BST *tree, KeyType key) {
4
 // 1.初始化一个curr指针用于遍历结点
5
 TreeNode *curr = tree->root;
6

7
 // 2.比较key值和当前结点的key值,然后确定向左遍历还是向右
8
 while (curr != NULL) {
9
     int diff = key - curr->key;
10
     if (diff > 0) {
11
         // 向右
12
         curr = curr->right;
13
     }
14
     else if (diff < 0) {
15
         // 向左
16
         curr = curr->left;
17
     }
18
     else
19
     {
20
         // 找到了key相等的结点,查找成功返回该结点
21
         return curr;
22
     }
23
 }
24
 // 3.如果遍历中没找到key相等的结点,那就是没有该结点
25
 return NULL;
26
}

非常简单。

实现删除操作

_Gn!

在具体实现二叉搜索树的删除结点之前，我们先引入一个新的概念——度(Degree)。

在数据结构中，度是指一个结点拥有的子结点的数量。在二叉搜索树当中，任何结点的度都只有三种情况：

1. 度为0：结点没有任何子结点，这种结点我们称之为"叶子结点"。

2. 度为1：结点有一个子结点（只有左子树或只有右子树）。

3. 度为2：结点有两个子结点，即左右子树都有。

在实现删除操作时，我们需要根据结点"度"的不同，来决定删除结点后树结构变化的逻辑，这是整个删除操作的核心逻辑。

整个删除操作的逻辑，可以细分为以下三步：

1. 找到被删除的结点。当然，现在你应该很熟悉这个操作了，因为这实际上就是在链表中删除一个结点，所以需要找到目标结点和它的父结点。

2. 根据删除结点的"度"不同，决定删除结点后树结构的变化逻辑。

3. free这个结点。

整个过程中，第一步和第三步都非常简单，参考代码如下：

删除操作-参考代码1

xxxxxxxxxx
49
1
// 根据key查找目标结点,将它删除掉,但不能因删除操作导致树断开或不符合BST的性质
2
bool bst_delete(BST *tree, KeyType key) {
3
    // 1.遍历找到目标结点
4
    // 本质上是删除单链表结点的操作
5
    // 所以需要初始化两个指针,一个指向待删除结点,一个指向它的父结点
6
    TreeNode* curr = tree->root;
7
    TreeNode* parent = NULL;
8
    while (curr != NULL) {
9
        int diff = key - curr->key;
10
        if (diff > 0) {
11
            // 向右
12
            parent = curr;
13
            curr = curr->right;
14
        }
15
        else if (diff < 0)
16
        {
17
            // 向左
18
            parent = curr;
19
            curr = curr->left;
20
        }
21
        else
22
        {
23
            // 找到目标结点
24
            // 目的达成,直接break结束循环
25
            break;
26
        }
27
    }
28

29
    /*
30
    * while循环结束时, 有两种可能性:
31
    * 1.找到目标key结点, 于是break结束循环.
32
    *   此时curr指向目标结点, parent指向目标结点的父结点
33
    * 
34
    * 2.目标key结点不存在, 于是curr是一个NULL时结束循环
35
    *   这其实就相当于在插入结点时,我们找到了插入位置
36
    *   但在删除时,我们不需要
37
    *   找不到目标结点,直接返回false结束函数,表示删除失败
38
    */
39
    if (curr == NULL){
40
        return false;
41
    }
42

43
    // 2.根据目标结点的度不同,决定不同的删除逻辑
44
    // ...
45

46
    // 3.free目标结点, 删除成功
47
    free(curr);
48
    return true;
49
}

这种面对复杂问题，先剥茧抽丝的做出分解，先解决容易思考和易实现的部分，然后花精力专注于核心逻辑的方法是非常有效的。

这种分解问题的方式不仅使得复杂问题的复杂性降低，更重要的是它也有助于保证最终代码的清晰性，组织性甚至扩展性。这种思考问题、编程解决问题的方式是值得学习的。

下面我们就来分析一下删除操作的核心逻辑。

核心逻辑分析

_Gn!

现在，我们来分析一下删除操作，最核心的逻辑——如何根据度不同决定删除结点后树结构变化的逻辑。

首先我们要明确一个前提：

现在我们已经找到了待删除的目标结点，curr指针指向它，并且我们还找到了它的父结点，parent指针指向它。

然后，我们仍然先思考简单的部分：

三种度的情况当中，删除叶子结点(度为0)和度为1的结点都是比较简单的，只需要让被删结点的父结点指向被删结点的子结点即可。（也就是链表删除确定位置后面的一个结点）

很明显度为0和1的两种情况可以合并处理，只需要让目标结点的前驱结点指向它的后继结点即可。参考下图：

但还有一种特殊情况不要忘记了，如果删除的是根结点(度为0或1的根结点)：

这种情况需要更新根结点指针root，千万不要忘记了！！！

度为2的情况会复杂一些，但既然度为1和0的情况可以合并处理，那我们就不由得想到一个思路：

能不能将度为2的情况处理降级为度为0或1呢？这样三种情况就能用同一段代码处理了，这样代码更简洁优雅，思路也很明确。

那么可不可以呢？当然是可以的。

度为2结点的降级删除思路

以下为了便于描述，都假设这个待删除的，度为2的结点是A结点。

首先度为2的结点肯定是无法直接删除的，因为这样将导致整棵树形结构的断开。

那么我们就换个思路——既然总要干掉一个结点，既然我们看重的是删除一个"key"值，那么能不能找个结点做"替死鬼"呢？

而且这个"替死鬼"最好还是度为0或1的，这样不就实现了删除度2结点的降级处理吗？

显然，这个"替死鬼"是存在的，这个结点就是A结点的右子树中的最小结点或者左子树的最大结点。

为什么是它呢？

因为右子树最小结点的key，肯定大于A结点的所有左子树，又肯定小于右子树的所有结点，让它替代A结点的父结点位置再合适不过了。（左子树的最大结点同理）

于是对于度为2结点(假如是A)的删除，我们进行如下处理：

1. 遍历A结点的右子树，找到右子树的最小结点B，然后用B结点的key值覆盖掉A结点的key值。这样就相当于删除了A结点。

2. 然后再删除B结点，而不是删除原本度为2的A结点。

经过这样的一番处理，我们就把删除度为2结点的操作，处理降级成删除度为0或1的情况——因为右子树的最小结点B只有两种可能：

1. 叶子结点，没有任何子树的结点。度为0

2. 只有一棵右子树但没有左子树的结点。度为1

如果你没看明白这个思路，那么可以参考下图理解：

总之，在二叉搜索树（BST）中通过交换元素值来实现删除操作是一种常用且推荐的方法，特别是对于度为2的节点。这种方法的优势在于它维持了树的结构和性质，同时简化了删除操作。

降级完成后，剩下的工作就很简单了，接下来只需要统一处理删除度为0或1的情况。这就是单链表在知道前驱结点后后继结点的情况下，删除当前结点。

非常简单，只需要——将被删除结点的父结点parent，指向被删除结点的子结点child就可以了：

1. 被删除的结点是父结点的左子树结点，那么parent的left指针指向child结点。

2. 被删除的结点是父结点的右子树结点，那么parent的right指针指向child结点。

当然还有删除度为0或1的根结点场景也不要忘记了：

被删除结点如果是父结点，这时只需要将根结点指针指向child结点即可。

以上整个思路就理清楚了，下面就可以实现这个过程了。

代码实现

_Gn!

于是BST二叉搜索树的删除结点操作的总体参考代码，就如下所示：

删除操作-参考代码2

xxxxxxxxxx
90
1
// 根据key查找目标结点,将它删除掉,但不能因删除操作导致树断开或不符合BST的性质
2
bool bst_delete(BST *tree, KeyType key) {
3
    // 1.遍历找到目标结点
4
    // 本质上是删除单链表结点的操作
5
    // 所以需要初始化两个指针,一个指向待删除结点,一个指向它的父结点
6
    TreeNode *curr = tree->root;
7
    TreeNode *parent = NULL;
8
    while (curr != NULL) {
9
        int diff = key - curr->key;
10
        if (diff > 0) {
11
            // 向右
12
            parent = curr;
13
            curr = curr->right;
14
        }
15
        else if (diff < 0)
16
        {
17
            // 向左
18
            parent = curr;
19
            curr = curr->left;
20
        }
21
        else
22
        {
23
            // 找到目标结点
24
            // 目的达成,直接break结束循环
25
            break;
26
        }
27
    }
28
    /*
29
    * while循环结束时, 有两种可能性:
30
    * 1.找到目标key结点, 于是break结束循环.
31
    *   此时curr指向目标结点, parent指向目标结点的父结点
32
    *
33
    * 2.目标key结点不存在, 于是curr是一个NULL时结束循环
34
    *   这其实就相当于在插入结点时,我们找到了插入位置
35
    *   但在删除时,我们不需要
36
    *   找不到目标结点,直接返回false结束函数,表示删除失败
37
    */
38
    if (curr == NULL) {
39
        return false;
40
    }
41

42
    // 2.根据目标结点的度不同,决定不同的删除逻辑
43
    // 2.1 将度为2的结点删除降级成删除度为1或0
44
    if (curr->left != NULL && curr->right != NULL) {
45
        /*
46
        * curr结点有左子树也有右子树,它就是一个度为2的结点,于是进行降级处理
47
        * 降级处理最终:
48
        * 1.需要找到curr结点的右子树最小结点,以及该最小结点的前驱结点
49
        * 2.需要用最小结点的key值覆盖curr结点的key值
50
        * 所以整个过程不要直接使用curr和parent指针遍历,而是新建两个临时指针
51
        * 指针名字的目的是为了代码更好的可读性,所以必要的时候,不要不舍得申请临时指针
52
        */
53
        TreeNode *min_node = curr->right;   // 从右子树根结点开始遍历查找最小结点
54
        TreeNode *min_parent = curr;
55

56
        while (min_node->left != NULL) {        // 既然是找最小结点,肯定是一直找到最左边的结点
57
            min_parent = min_node;
58
            min_node = min_node->left;
59
        }   // 循环结束时,min_node结点是最左边的子节点,也就是最小结点.parent则是最小结点的父节点
60

61
        // 找到最小结点了,将它的key值替换curr结点的key值
62
        curr->key = min_node->key;
63
        // 更新curr结点为待删除的最小结点,以及更新parent结点为最小结点的父结点
64
        // 这样做是为了后续统一利用curr和parent删除度0或1的结点
65
        curr = min_node;
66
        parent = min_parent;
67
    }   // curr是待删除的度为0或1的结点,parent是它的父结点
68

69
    // 2.2 统一处理度为0或1结点的删除,但是不要忘记删除根结点的特殊情况
70
    // 这里的操作就是在知道前驱和后继的情况下,删除链表的一个结点
71
    // 但BST又有点特殊,你需要先搞清楚后继是哪个结点,才能够让前驱指向后继
72
    TreeNode *child = (curr->left != NULL) ? curr->left : curr->right;
73

74
    // 处理删除的是度0或1的根结点的特殊情况
75
    if (parent == NULL) {
76
        tree->root = child;
77
    }
78
    else if (parent->left == curr) {
79
        // BST你需要搞清楚删除的是左子树还是右子树
80
        // 待删除的是左子树
81
        parent->left = child;
82
    }
83
    else {
84
        // 待删除的是右子树
85
        parent->right = child;
86
    }
87
    // 3.free目标结点, 删除成功
88
    free(curr);
89
    return true;
90
}

总结一下这个删除逻辑：

1. 查找要删除的节点：

2. 遍历BST，找到与给定键值key匹配的结点和它的前驱结点。分别用curr指针和parent指针指向。

3. 如果没有找到相应的节点（即curr指针为 NULL时），则返回 false，表示未找到目标结点，删除失败。

4. 处理度为2的节点。如果 curr是一个度为2的节点（即同时拥有左右子树），执行以下步骤：

   1. 找到curr结点右子树中的最小节点以及它的父结点（这一步使用了min_node和min_parent的临时指针），这一步只需要不停向左遍历curr结点的左子树即可找到。

   2. 将min_node结点的key值，覆盖原先curr结点的值，这一步实现了在逻辑上删除curr结点。

   3. 更新 curr 和 parent指针，使它们指向min_node及min_parent结点，以便进行后续的删除操作。

   4. 这一步完成时，curr指针指向的结点，也就是待删除的结点，度一定为0或1。parent则指向它的父结点。

5. 统一处理度为0或1的节点：

   1. 先确定待删除curr结点的后继结点，用child指针指向它。child是空指针则表示删除的是叶子结点。

   2. 若 parent 为 NULL，表明待删除的是度为0或1的根节点，更新根结点指针，让它指向child结点。

   3. 如果 parent 非 NULL，根据curr结点是 parent 的左子节点还是右子节点，相应地将 parent 的 left 或 right 指针更新为指向 child。

6. 完成删除操作：

   1. 释放 curr 所指向的节点的内存。

   2. 删除操作完成后，返回 true，表示成功删除了目标节点。

以上，如果还有不明白的，就仔细画图分析一下。

实现遍历操作

_Gn!

在实现销毁二叉树操作之前，我们先来实现它的遍历操作。因为只有学会遍历，才可能实现销毁。

在二叉搜索树当中，深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）是两种常见的遍历策略，用于查找、检索或处理树中的数据。

对于一个如上图所示的二叉搜索树，它的遍历策略如下：

深度优先搜索策略

_Gn!

深度优先搜索会尽可能深地探索树的分支，然后回溯到之前的根结点，再探索其他分支。深度优先搜索又可以分三种方式：

1. 先序遍历（Pre-order）：首先访问当前结点，然后深入遍历访问它的左子树，最后再深入遍历访问它的右子树。也就是DLR

2. 中序遍历（In-order）：首先深入遍历访问它的左子树，然后访问当前结点，最后再深入遍历访问它的右子树。也就是LDR

3. 后序遍历（Post-order）：首先深入遍历访问它的左子树，然后再深入遍历访问它的右子树，最后访问当前结点。也就是LRD

所以，这些命名中的"先、中、后"指的是当前结点(根结点)D的访问顺序。先访问根结点，就是先序，后访问就是后序，中间访问就是中序。

需要注意的是：

在DFS遍历时，总是左子树先于右子树被访问，这是由传统和习惯决定的，并且这种约定也使得中序遍历能够升序访问所有结点。当然你也可以设计实现一个先访问右子树的深度优先搜索算法，但这一般没有太大意义。

DFS在实现时，直观、简单且有效的策略就是递归，这是因为：

1. 二叉搜索树的定义本身就是递归的。每一个结点都可以视为根结点，有左子树和右子树。这种自然的递归结构使得递归成为处理树结构的自然选择。

2. DFS算法的描述本身也是递归的。比如先序遍历，无论遍历到哪个结点它总是先访问根结点，再访问左子树，最后访问右子树。这个过程会始终重复，深入到一棵树的每个分支直到无法继续再进行回溯，直到遍历完整棵树。

总之，三种深度优先遍历的实现参考代码如下：

深度优先搜索策略三种实现-参考代码

xxxxxxxxxx
103
1
/*
2
* 利用递归实现BST的先序遍历
3
* root参数表示此一轮递归调用中的根结点
4
* 先序遍历是: DLR
5
* 分解的思路是:
6
* 对于任何一棵树root来说:
7
* 1.总是先输出根结点的值
8
* 2.然后递归遍历它的左子树
9
* 3.最后递归遍历它的右子树
10
* preoder(root) = D + preorder(root->left) + preorder(root->right)
11
* 这就是递归体
12
* 这样的分解不会无休止进行,如果分解成一棵空树,也就是root是空指针时,返回函数
13
* 这就是递归的出口
14
*/
15
static void preorder(TreeNode* root) {
16
    // 1.递归的出口
17
    if (root == NULL) {
18
        return;
19
    }
20
    // 2.递归体
21
    printf("%d ", root->key);
22
    preorder(root->left);
23
    preorder(root->right);
24
}
25

26
void bst_preorder(BST* tree) {
27
    if (tree == NULL) {
28
        // 树为空直接返回
29
        return;
30
    }
31
    // 利用辅助函数递归实现BST的先序遍历
32
    preorder(tree->root);
33
    printf("\n");
34
}
35

36

37
/*
38
* 利用递归实现BST的中序遍历
39
* root参数表示此一轮递归调用中的根结点
40
* 中序遍历是: LDR
41
* 分解的思路是:
42
* 对于任何一棵树root来说:
43
* 1.总是先递归遍历它的左子树
44
* 1.然后再输出根结点的值
45
* 3.最后递归遍历它的右子树
46
* inorder(root) = inorder(root->left) + D + inorder(root->right)
47
* 这就是递归体
48
* 这样的分解不会无休止进行,如果分解成一棵空树,也就是root是空指针时,返回函数
49
* 这就是递归的出口
50
*/
51
static void inorder(TreeNode* root) {
52
    // 1.递归的出口
53
    if (root == NULL) {
54
        return;
55
    }
56
    // 2.递归体
57
    inorder(root->left);
58
    printf("%d ", root->key);
59
    inorder(root->right);
60
}
61
void bst_inorder(BST* tree) {
62
    if (tree == NULL) {
63
        // 树为空直接返回
64
        return;
65
    }
66
    // 利用辅助函数递归实现BST的中序遍历
67
    inorder(tree->root);
68
    printf("\n");
69
}
70

71
/*
72
* 利用递归实现BST的后序遍历
73
* root参数表示此一轮递归调用中的根结点
74
* 中序遍历是: LRD
75
* 分解的思路是:
76
* 对于任何一棵树root来说:
77
* 1.总是先递归遍历它的左子树
78
* 3.然后递归遍历它的右子树
79
* 3.最后再输出根结点的值
80
* postorder(root) = postorder(root->left) + postorder(root->right) + D
81
* 这就是递归体
82
* 这样的分解不会无休止进行,如果分解成一棵空树,也就是root是空指针时,返回函数
83
* 这就是递归的出口
84
*/
85
static void postorder(TreeNode* root) {
86
    // 1.递归的出口
87
    if (root == NULL) {
88
        return;
89
    }
90
    // 2.递归体
91
    postorder(root->left);
92
    postorder(root->right);
93
    printf("%d ", root->key);
94
}
95
void bst_postorder(BST* tree) {
96
    if (tree == NULL) {
97
        // 树为空直接返回
98
        return;
99
    }
100
    // 利用辅助函数递归实现BST的后序遍历
101
    postorder(tree->root);
102
    printf("\n");
103
}

比较需要注意的是三个static修饰的辅助函数，之所以需要三个辅助函数，是因为原先函数传入的参数是BST类型，而递归需要处理的是树结点TreeNode类型。

当然这种模块化编程的设计方式，可以增强代码的可读性，也使得代码更便于理解和维护。

广度优先搜索策略

_Gn!

除了深度优先，在遍历二叉搜索树时还可以选择广度优先搜索策略。

所谓广度优先搜索（Breadth-First Search，BFS）策略，指的是按照树的层次结构从上到下、从左到右依次访问每个结点，所以也叫层次遍历。

与深度优先搜索（DFS）不同，层次遍历不会立即深入树的分支，而是首先探索根结点所在的层级，然后是第二层，以此类推，直到访问了所有层级。

层次遍历，是比较符合人类阅读树形结构习惯的，比如一个族谱，我们总会先看看祖先，然后逐代从左往右向下看。

那么如何实现层次遍历算法呢？

我们可以借助一个队列来实现——将一个二叉搜索树的元素从根结点开始入队，然后入队左子树结点，右子树结点。这样在出队时，就可以实现根结点，左子树结点，右子树结点逐层出队输出的结果。

在以往的课程中，我们已经实现了一个队列，我们可以直接将头文件和源文件复制进来，然后使用。

注：这里我使用的是一个链式队列，它的代码在队列_链式队列一小节中有，当然你需要将队列的元素类型修改一下。

参考代码如下：

BST层次遍历-参考代码

xxxxxxxxxx
25
1
// 层次遍历
2
// 要包含队列对应的头文件且要修改队列中元素的类型为TreeNode*类型
3
void bst_levelorder(BST *tree) {
4
    LinkedListQueue *q = create_queue(); // 创建一个队列
5
    // 1.首先让根结点入队
6
    enqueue(q, tree->root);
7
    // 2.当队列不为空时，执行循环
8
    // 在这个循环中，我们将会逐个访问每一层的节点，并将它们的子节点加入队列
9
    while (!is_empty(q)) {
10
        TreeNode *node = dequeue(q); // 出队获取当前结点
11
        printf("%d ", node->key);    // 打印当前节点的键值
12

13
        // 如果当前节点的左子节点存在，将左子节点加入队列
14
        if (node->left != NULL) {
15
            enqueue(q, node->left);
16
        }
17

18
        // 如果当前节点的右子节点存在，将右子节点加入队列
19
        if (node->right != NULL) {
20
            enqueue(q, node->right);
21
        }
22
    }
23
    printf("\n");
24
    destroy_queue(q); // 完成遍历后，销毁队列释放资源
25
}

层次遍历的思路是：

1. 新建一个空的队列，然后让二叉搜索树的根结点入队

2. 判断队列是否为空

   1. 若队列为空，则说明层次遍历结束，树的所有结点都已完成遍历。

   2. 若队列不为空，则首先出队列一次，然后判断左子树是否为空，若不为空左子树结点入队。最后判断右子树是否为空，若不为空右子树结点入队。

3. 最后，不要忘记销毁队列，避免内存泄漏。

需要注意的是，队列的元素要在头文件"list_queue.h"中修改成：

xxxxxxxxxx
1
1
typedef TreeNode* E;

作为一个结点指针类型，使用=直接赋值操作是可以的，所以其他位置代码是不需要修改的。这说明，以往我们采取这种别名的方式定义元素类型，提高了代码的可维护性。

此版本层次遍历打印的效果大体是：30 10 40 5 15 35 70 3 12 75。所有的结点值都打印在了同一行。

上述遍历只是按照顺序输出的了结点key值，如果期望能够打印出BST的层次结构，实现打印一层结点值就换行一次，实现一个更佳效果的层次遍历。我们可以修改一下链式队列的结构体类型定义，增加一个size属性，用来记录队列中元素的个数：

xxxxxxxxxx
6
1
// 队列的结构
2
typedef struct {
3
    QueueNode* front;  // 队列的头部
4
    QueueNode* rear;   // 队列的尾部
5
    int size;   // 队列中元素的个数
6
} LinkedListQueue;

同样还需要在出队、入队操作函数中增加size操作的代码。（size--或size++）

这样利用队列中元素的个数这个属性，我们就可以实现一个更好的层次遍历，参考下列代码：

BST层次遍历2-参考代码

xxxxxxxxxx
31
1
// 优化：层次遍历时将BST树的每一层的层级输出出来
2
void bst_levelorder2(BST *tree) {
3
    LinkedListQueue *q = create_queue(); // 创建一个队列
4
    // 1.首先让根结点入队
5
    enqueue(q, tree->root);
6
    // 2.当队列不为空时，执行循环
7
    // 在这个循环中，我们将会逐个访问每一层的节点，并将它们的子节点加入队列
8
    while (!is_empty(q)) {
9
        // 刚进入while循环时,队列的size属性就是这一层结点的个数
10
        int level_size = q->size;   // 当前层次结点的个数
11
        // 于是下面循环出队列n次，就是出队打印完所有本层结点，并将所有下一层结点都入队
12
        for (int i = 0; i < level_size; i++) {
13
            TreeNode *node = dequeue(q); // 出队获取当前结点
14
            printf("%d ", node->key);    // 打印当前节点的键值
15

16
            // 如果当前节点的左子节点存在，将左子节点加入队列
17
            if (node->left != NULL) {
18
                enqueue(q, node->left);
19
            }
20

21
            // 如果当前节点的右子节点存在，将右子节点加入队列
22
            if (node->right != NULL) {
23
                enqueue(q, node->right);
24
            }
25
        }
26
        // 出队打印完一层，换行
27
        printf("\n");
28
    }
29
    printf("\n");
30
    destroy_queue(q); // 完成遍历后，销毁队列释放资源
31
}

其中的核心逻辑在于每一次while循环的开头，队列的size属性(也就是队中元素的个数)，都表示BST当前层次的结点数量。

实现销毁操作

_Gn!

到此为止，我们已经学习了多种遍历方式遍历二叉搜索树，而销毁操作无非就是在遍历过程中free结点。那么该选择什么遍历方式呢？

很显然，最适合的遍历方式是后序遍历——它总是首先访问结点的左右子树，最后才访问结点本身。

这样利用递归，就可以实现每个结点的所有子树都被释放之后，才释放该结点本身，从而防止内存泄漏。也就是将以往输出打印结点值的代码改成free函数调用即可。

参考代码如下：

销毁操作-参考代码

xxxxxxxxxx
18
1
// 递归释放BST的结点，总是最后释放根结点，所以采用后序遍历的方式实现
2
static void destory(TreeNode *root) {
3
    if (root == NULL) {
4
        return;
5
    }
6
    // 后序,先访问左右子树,再free根结点
7
    destory(root->left);
8
    destory(root->right);
9
    free(root);
10
}
11
void bst_destroy(BST *tree) {
12
    if (tree == NULL) {
13
        return;
14
    }
15
    // 递归释放树结点
16
    destory(tree->root);
17
    free(tree);
18
}

以上。

测试用例

_Gn!

给出一个测试用例，大家可以自行测试一下，自己写的BST二叉搜索树是否正确。

测试用例-参考代码

xxxxxxxxxx
70
1
#include "BST.h"
2
#include <stdio.h>
3

4
int main() {
5
    // 创建二叉搜索树
6
    BST *tree = bst_create();
7
    if (!tree) {
8
        printf("二叉搜索树创建失败。\n");
9
        return 1;
10
    }
11

12
    // 插入元素
13
    int elements[] = { 50, 30, 70, 20, 40, 60, 80, 30 }; // 包含重复元素30
14
    printf("正在插入元素: ");
15
    int arr_len = sizeof(elements) / sizeof(elements[0]);
16
    for (int i = 0; i < arr_len; i++) {
17
        if (bst_insert(tree, elements[i])) {
18
            printf("%d ", elements[i]); // 打印成功插入的元素
19
        }
20
        else {
21
            printf("(重复 %d) ", elements[i]); // 打印重复元素的信息
22
        }
23
    }
24
    printf("\n");
25
    // 预期结果：重复的元素不应该被插入到树中。
26

27
    // 中序遍历，应该输出有序序列
28
    printf("中序遍历输出(预期有序): ");
29
    bst_inorder(tree);
30
    printf("\n");
31
    // 预期结果：20, 30, 40, 50, 60, 70, 80
32

33
    // 先序遍历输出 预期结果：50 30 20 40 70 60 80
34
    printf("先序遍历输出: ");
35
    bst_preorder(tree);
36
    printf("\n");
37

38
    // 后序遍历输出 预期结果：20 40 30 60 80 70 50
39
    printf("后序遍历输出: ");
40
    bst_postorder(tree);
41
    printf("\n");
42

43
    // 层次遍历输出 预期结果：50 30 70 20 40 60 80
44
    printf("层次遍历输出: ");
45
    bst_levelorder(tree);
46
    printf("\n");
47

48
    // 测试搜索存在和不存在的情况 预期结果：找到了
49
    int searchKey = 40;
50
    printf("搜索键 %d 的结果: %s\n", searchKey, bst_search(tree, searchKey) ? "找到了" : "未找到");
51

52
    // 预期结果：未找到
53
    searchKey = 100;
54
    printf("搜索键 %d 的结果: %s\n", searchKey, bst_search(tree, searchKey) ? "找到了" : "未找到");
55

56
    // 测试删除操作
57
    printf("删除元素 70 和 20\n");
58
    bst_delete(tree, 70);
59
    bst_delete(tree, 20);
60

61
    // 再次进行中序遍历验证删除操作 // 预期结果：30, 40, 50, 60, 80
62
    printf("删除元素后中序遍历输出: ");
63
    bst_inorder(tree);
64
    printf("\n");
65

66
    // 销毁二叉搜索树
67
    bst_destroy(tree);
68

69
    return 0;
70
}

以上。

性能分析

_Gn!

对于一个二叉搜索树而言，它的插入、查询以及删除操作的效率都取决于它的高度h。

也就是说，时间复杂度是O(h)。

这是因为这些操作，都需从根结点开始，沿树向下进行寻找，于是这些操作的时间复杂度就往往与树的高度成正比。当然，在更多的时候，我们会以二叉搜索树的结点数量来评估它的效率。

此时就需要思考一个非常重要的问题：

对于一个n个结点的二叉搜索树，它的高度是多少呢？

具体的推论过程，放在下面，这里直接给出答案：

1. n个结点的二叉搜索树，在最佳理想情况下，在形态上是一个完全二叉树，此时树的高度最小。是log₂n向下取整。

2. n个结点的二叉搜索树，高度最高时，就是一个单链表，此时树的高度最大，高度就是n。

所以对一个n个结点的二叉搜索树，它操作的时间复杂度：

1. 最佳情况：O(log n)

2. 最差情况：O(n)

那么我们在上面实现的一个二叉搜索树，它的效率是更接近最佳还是最差呢？

显然，我们上面实现的 BST 并不能保证树的高度始终为log₂n左右：

1. 如果按照key大小顺序进行插入，那么就会得到一个向左或向右的单链表。

2. 即便没有直接按照key的大小顺序插入，即便只是随机的插入，但普通的BST在频繁的插入和删除操作之后，由于没有内设的平衡机制，总会导致树有向一侧倾斜的趋势。

总之，要想保证BST的增加，查找，删除的时间复杂度为 O(logn)，我们需要在添加结点和删除结点后，做一些调整操作，以保证二叉树的高度大约是log₂n。

这种二叉搜索树被称之为——自平衡二叉搜索树，简称平衡二叉树。

不同的平衡二叉树对平衡的定义是不同的，常见的平衡二叉树有：

1. AVL树。

   1. 平衡的条件是：任何结点的两个子树的高度差不能超过1。

   2. 如果在插入或删除结点后树变得不平衡，会通过旋转树操作来恢复平衡。

   3. 因为高度平衡的特性，AVL树在查找、插入和删除操作上都提供O(logn)的效率。

   4. 因为高度平衡的特性，AVL树在插入和删除操作时，可能需要更频繁的旋转，带来额外的性能开销。

2. 红黑树。

   1. 红黑树通过确保树的结构满足特定的性质来保持平衡，它并不强制要求子树的高度差不超过1。它的平衡性要求比AVL树更低。

   2. 红黑树的查找、插入和删除操作的时间复杂度同样是O(logn)。

   3. 红黑树在平衡性要求上不如AVL树严格，所以插入和删除的操作就只需要较少的旋转来重新平衡，性能更优。

总的来说，平衡二叉树中应用最广，名气最大的还属红黑树了，下面我们简单介绍一下红黑树。

补充了解：n个结点的二叉搜索树，高度h的取值范围的计算过程

高度h的最大值非常好思考，当n个结点的二叉搜索树构成一条单链表时，它的高度最高，即h = n。

高度h的最小值情况也非常好思考，当n个结点的二叉搜索树在结构上是一个完全二叉树时，高度最低。

但这个最低高度具体是多少呢？

想直接计算上面的最低高度值，比较困难不好思考。我们逆向思维，先思考下面一个问题：

高度为h的一个完全二叉搜索树，它的结点取值范围n是多少呢？(注：树的高度h是从0开始计算的)

1. n的最小取值是当此二叉搜索树在形态上，是一个最底层只有一个结点的完全二叉树时：

2. 在一棵高度为 h 的完全二叉树当中，前 h 层（从第0层到第h−1层）的总结点数是：2⁰ + 2¹ + 2² + 2³ + ... + 2^h-1

3. 这是一个等比数列的求和，其结果是：2^h - 1

4. n的最小取值时，第h层就只有一个结点。

5. 于是高度为h的一个完全二叉搜索树，n的最小取值是2^h

6. n的最大取值是当此二叉搜索树在形态上，是一个满二叉树时：

7. h层高度的满二叉树，总结点数是：2⁰ + 2¹ + 2² + 2³ + ... + 2^h-1 + 2^h

8. 这同样一个等比数列的求和，其结果是：2^{h + 1} - 1

9. 于是高度为h的一个完全二叉搜索树，n的最大取值是2^{h + 1} -1

也就是说：

高度为h的一个完全二叉搜索树，它的结点取值范围n是：

$$\begin{array}{}\text{(1)}& 2^h\le n\le 2^{h+1}-1\end{array}$$

从左侧不等式开始：

$$\begin{array}{}\text{(2)}& 2^h\le n\end{array}$$

两边同时取以2为底的对数：

$$\begin{array}{}\text{(3)}& h\le {\log }_{2}n\end{array}$$

同样的道理从右侧不等式开始，就可以得到一个关于h的完整不等式：

$$\begin{array}{}\text{(4)}& {\log }_2(n+1)-1\le h\le {\log }_{2}n\end{array}$$

在二叉搜索树是完全二叉树的情况下，高度h由于必须是一个整数，所以它的取值范围是：

$$\begin{array}{}\text{(5)}& \lceil {\log }_2(n+1)-1\rceil \le h\le \lfloor {\log }_{2}n\rfloor \end{array}$$

不等式的左边向上取整，而右边向下取整。比如在n = 15时：

$$\begin{array}{}\text{(6)}& {\log }_2(16)-1=4-1=3\end{array}$$

$$\begin{array}{}\text{(7)}& {\log }_2(15)\approx 3.906\end{array}$$

这就说明在一般情况下，h的取值可以直接等同于右边不等式的值，此时h的取值可以直接当成：

$$\begin{array}{}\text{(8)}& h=\lfloor {\log }_{2}n\rfloor \end{array}$$

表示h的取值是log₂n向下取整。

总之，n个结点的二叉搜索树，高度h的取值范围：

1. 最大值是n

2. 最小值就是log₂n向下取整

红黑树(了解)

_Gn!

平衡二叉树当中，最常用的就是红黑树。

红黑树在许多编程语言的标准库中都被广泛使用，如Java中的TreeMap和TreeSet以及HashMap的部分实现，以及C++中的map、multimap、set和multiset等，它们的底层数据结构实现都是红黑树。

在这一小节，我们就不讲红黑树的具体实现了，只浅谈一下理论模型。

为了更好的理解红黑树的理论模型，我们先来了解一下"2-3-4树"，理解了它，就基本上理解了红黑树。

2-3-4 树

_Gn!

2-3-4树和红黑树之间有着密切的关系，它们实际上是等价的数据结构，可以互相转换。这种关系主要体现在它们的结构和平衡操作上。

2-3-4 树具有以下两个性质：

1. 2-3-4树是一种多路搜索树，其中每个结点可以包含最多三个键和四个子结点，这就是它的：

   1. 2-结点：一个 key 值，两个孩子。

   2. 3-结点：两个 key 值，三个孩子。

   3. 4-结点：三个 key 值，四个孩子

   4. 注意：结点命名中的2-3-4表示该结点的孩子数量，而不是key值的数量。

2. 2-3-4树是一种能够动态保持完美平衡的树，所有叶子结点都在同一层，这样从根结点到任意一个叶子结点的路径都是一样长的(完美平衡)。

如下图所示：

下面我们重点来看一下2-3-4 树保持动态完美平衡的方式。也就是看一下2-3-4 树的基本操作，尤其是插入操作。

查找操作

_Gn!

我们先来看一下2-3-4 树的查找操作，来进一步理解2-3-4 树的性质。当然，2-3-4 树的查找和普通 BST 的查找方式几乎一致。

如下图所示：

过程如下：

1. 从树的根结点开始查找结点L

2. 确定要查找的关键字L的位置。由于L在K和R之间，因此我们向树的中间子树走去，到达包含M和O的结点。

3. 在结点M和O中，由于L小于M，我们向左走，到达包含关键字L的结点。在这个结点中找到关键字L，因此查找操作成功。

插入操作

_Gn!

查找操作没有引入结点的变化，不会影响树的平衡，但插入操作就不同了。为了维持平衡，操作就比普通BST树复杂很多。

我们将插入操作分为下面几种情况：

如果是在2-结点中插，直接将2-结点转换为3-结点。如下图所示：

过程如下：

1. 要插入的结点key是B

2. 插入操作从树的根结点开始查找插入位置。B小于K，所以沿着根结点的左子树继续查找。

3. 接下来，我们到达了包含关键字C和E的结点。由于B小于C，我们继续向左子树移动。

4. 到达一个包含关键字"A"的叶子结点。在这个结点中，"B"应当插入"A"的右边，因为"B"大于"A"。

5. 在这个2-结点（只包含一个关键字的结点）中插入B，它变成了一个3-结点（包含两个关键字的结点），现在包含A和B。

6. 这种插入方法保持了树的平衡性。如果"B"被插入为"A"的子结点，将违反2-3-4树的性质，因为所有叶子结点都必须在同一层。

如果是在3-结点中插入，直接将3-结点转换为4-结点。如下图所示：

过程如下：

1. 要插入的结点key是X

2. 插入操作从树的根结点开始查找插入位置。由于"X"大于R，我们知道它应该位于R的右侧。因此，我们向右子树移动。

3. 在右子树中，我们到达了含有单个关键字W的节点。

4. 由于"X"大于W，我们再次向右移动，到达了含有关键字Y和Z的节点。

5. 在这个3-节点中，"X"应该插入Y的左边。

6. 将"X"插入现有的3-节点（含有Y和Z的节点），节点将变成一个4-节点，现在包含X, Y, 和Z三个关键字。

以上两个操作都是比较容易理解的，为了保证2-3-4 树的平衡性，只增加结点的key数量，而不是增加树的层级。

那么问题来：

如果就是在4-结点中插入key，又该怎么办呢？如下图所示：

按照顺序查找插入位置，发现"H"需要插入到4-结点的"G"和"J"之间，但2-3-4 树可没有5-结点，怎么办呢？

答：分裂这个4-结点。如下图所示：

具体操作是：

1. 分裂4-结点"F G J"，可以选择一个key将它放入父结点中。进行结点分裂。

2. 我们选择将"G"放入父节点中，这是因为"G"是4-结点"F G J"的中间key，将它放入父节点中。原先的F和J就可以均匀分布在这个父节点下方。

3. 4结点分裂成两个2-结点后，就可以查找"H"的插入位置。

4. H应该插入J的左边，所以可以和J一起组成一个3-结点。

5. 这样就在不破坏2-3-4 树平衡的情况下，完成了4-结点插入操作。

在这个4-结点分裂的操作过程中，使得父节点的key数量增多了。于是又有了一个问题：

如果父结点也是4-结点，那又该怎么办呢？

有两种解决办法：

1. 自底向上分裂法：

   1. 如果分裂一个4-子结点时发现它的父节点也是4-结点，那么就继续分裂这个4-父节点。

   2. 这个过程自底向上，沿着查找路径一直分裂，可以一直分裂到根结点。(如果根结点也是4-结点，那么需要增加树的高度)

   3. 这个方式，相当于走回头路，需要来回遍历树，效率不高。一般更推荐下面的"自顶向下分裂法"

2. 自顶向下分裂法：

   1. 在查找插入位置的过程中，只要遇到4-结点就分裂它。

   2. 这种设计使得在插入操作，真正想分裂一个4-结点时，它的父节点肯定不是4-结点，所以它不会来回遍历树，效率更高。(因为父节点如果是4-结点，在向下遍历的过程中已经被分裂了)

   3. 这种分裂方式还会带来一个好处，在查找到插入位置时，一定可以直接进行插入。(因为当前结点肯定不是4-结点了)

   如下图所示：

   

至此，关于2-3-4 树的插入操作，我们已经搞清楚了。下面用几幅2-3-4 树的生长过程图，来进一步帮助大家理解2-3-4 树。

这个生长过程是：

1. 插入A：树开始时为空。首先插入关键字"A"，创建了一个2-节点。

2. 插入S：接着插入"S"，它被添加到现有的2-节点中，使之成为一个3-节点。

3. 插入E：然后插入"E"，它被添加到现有的3-节点中，使之成为一个4-节点。

4. 插入R，树增长一个层级：然后插入"R"，此时树仅有一个4-结点，按照上面的自顶向下分裂法，需要分裂这个4-结点。

   1. 由于这个4-结点是一个根结点，所以分裂这个4-结点会使得树的高度增加一层。

   2. 这个分裂过程会把中间key值"E"作为新的根结点，A和S分别成为新的左右子树。

   3. R比S小，所以它和S组成了一个新的3-结点。

5. 插入C：当插入"C"时，它被放在"A"和"E"之间的位置，导致原先的2-节点（包含"A"）变成了一个3-节点。

6. 插入D：插入"D"后，由于"A"和"C"之间有空间，它被插入，形成一个满载的4-节点，现在包含"A"、"C"和"D"。

7. 插入I：最后插入"I"。这个关键字适合在"E"的右子节点中插入，这是一个3-节点包含"R"和"S"。由于3-节点还有空间，"I"被插入，形成了另一个满载的4-节点。

下面继续进行插入：

1. 树的初始状态：树的初始状态是一个根节点E，下面有两个子节点。左子节点是一个4-节点包含A, C, D，右子节点是一个4-节点包含I, R, S。

2. 插入N：

   1. 首先，N需要被插入到E的右子树当中，具体位置是"I"和"R"之间。

   2. 插入过程遇到4-结点"I R S"，所以分裂它。

   3. 在分裂过程中，中间关键字R被提升到了根节点E，新的根结点变成了一个3-结点，现在包含E, R。

   4. I和S则成为这个根结点新的左右子树。

   5. N需要插入到"I"的右边，所以"I R"组成了一个新的3-结点，完成插入。

3. 插入B：

   1. 首先，B需要被插入到ER的左子树当中，具体位置是"A"和"C"之间。

   2. 插入过程遇到4-结点"A C D"，所以分裂它。

   3. 在分裂过程中，中间关键字C被提升到根节点中，新的根结点变成了一个4-结点，现在包含C，E， R。

   4. A和D则成为这个根结点新的左右子树。

   5. B需要插入到"A"的右边，所以"A B"组成了一个新的3-结点，完成插入。

4. 插入X：

   1. 从根结点开始查找插入位置，发现根结点已经是一个4-结点，于是立刻分裂它。

   2. 根结点分裂导致树的高度增加了一层，E成为了新的2-根节点，C和R成为它的2-子节点

   3. X需要插入到S的右边，于是S和X形成了一个新的3-结点，完成插入。

从上面的例子，大家应该可以看出2-3-4树是如何保持完美平衡的了。

性能分析

_Gn!

2-3-4 树的增加，删除，查找操作的时间复杂度都取决于树的高度 h，那么树的高度如何计算呢？

假设树的key数量是N，那么：

1. 最坏情况下，树中全部是2-结点。

   1. 每个2-结点可以视为传统二叉搜索树中的一个节点。

   2. 那么树的高度最坏情况下，也是h = log₂N。

2. 最好情况时，树中全部都是4-结点。

   1. 在这种情况下，树中的每层4-结点可以被视为在传统二叉树中的两层节点。

   2. 那么树的高度 h = log₄N = (1 / 2) * log₂N = log₂N / 2

   3. 也就是说，树的高度在最好的情况下，在结点相同的情况下，只有传统二叉搜索树的一半。

可能大家对这个对数结果的高度没什么感觉和概念，那么我们可以举两个例子：

1. 当N = 100万时，2-3-4树的高度在 10 到 20 之间。

2. 当N = 10亿时，2-3-4树的高度在 15 到 30 之间。

所以，2-3-4树的性能是非常nice，当然这也不是没有代价。代价就是实现和内存管理的巨大复杂性，以及空间的较高占用。

如何实现？

_Gn!

2-3-4 树这么厉害，那么如何真正实现和使用它呢？

如果为2-结点，3-结点，4-结点分别编写不同的结点类型，那么处理起来会非常麻烦，我们不得不处理各个结点类型之间的转换。

所以实际上，由于其实现的复杂性，业界并没有直接选择去实现2-3-4树，而是选择一种更巧妙，更简单，但等价的数据结构实现，这就是红黑树。

红黑树可以看成2-3-4 树的一种简化的实现方式，设计非常之巧妙。

红黑树的实现逻辑

_Gn!

红黑树实际上还是一棵普通的二叉搜索树，在2-3-4树中，一个节点可以包含1到3个键和2到4个子节点。而在红黑树中，每个节点包含1个键和2个子节点（标准的二叉树结构）。

用C语言的结构体描述，就如下：

红黑树的结点-结构体代码

xxxxxxxxxx
6
1
typedef struct treenode_s {
2
  int key;
3
  bool color;
4
  struct treenode_s* left;
5
  struct treenode_s* right;
6
}TreeNode;

比起我们前面实现的二叉搜索树，就多了一个color成员，用于指示当前结点的颜色——红结点或者黑结点。

结点转换

_Gn!

那么红黑树如何通过颜色描述2-3-4树的三种结点呢？这里就存在一个结点转换的过程：

1. 2-结点直接对应红黑树中的一个黑色节点。

2. 3-结点对应红黑树中的一个黑色节点再加上一个红色节点。

3. 4-结点对应红黑树中的一个黑色节点再加上两个红色节点。

3-结点转换过程：

在上图中，转换后的每个结点都只有一个key，一个黑结点和红结点就构成了以往的3-结点。

4-结点转换过程：

4-结点的转换尤其要注意，只有上述一种方式，下列几种方式都是不可以的：

之所以这样，目的是为了保证红黑树的高度最低，提升效率。

除了上面的结点颜色理解方式，理解红黑树还可以用"黑边红边"来理解，如下图所示：

这种理解方式会根据结点成员color的取值，决定它和父节点链接"边"的颜色。一个结点成员color的取值是红色，那么就表示该结点和父节点链接的边是"红色"的。

而这个红色的边，可以理解成：被红色边链接的几个结点就是逻辑上的同一个结点。

比如根据上图：

1. 一个2-3-4树中的3-结点，可以转换成红黑树中一个父结点用"红边"链接左子树或者右子树。

2. 一个2-3-4树中的4-结点，可以转换成红黑树中一个父结点用"红边"同时链接左子树和右子树。

当然，一个2-3-4树中的2-结点，它和父节点之间的链接肯定是"黑边"。总之，通过以上方式，我们就完成了2-3-4树中三种结点到红黑树结点的转换。

红黑树的定义

_Gn!

我们来看一看经典教科书《算法导论》对红黑树的定义：

叶子结点：在《算法导论》定义红黑树时，将NULL子树定义为叶子结点。这么定义叶子结点是为了更便于描述红黑树的规则。

红黑树是满足以下性质的二叉搜索树：

1. 节点颜色：每个节点或是红色的，或是黑色的。(NULL结点，叶子结点是黑色的)

2. 根节点规则：树的根节点是黑色的。

3. 红色节点规则：如果一个节点是红色的，则它的两个子节点都是黑色的（即红色节点不能有红色的子节点，也就是说不能有两个连续的红色节点）。

4. 黑色高度规则：从任何一个节点，到该节点的任意叶子节点的路径上，包含相同数目的黑色节点。

在这个规则当中，需要解释一下的第3条和第4条规则，思考一下为什么会有这两条规则呢？

解释：

1. 红色结点的规则，也就是禁止出现连续的红色节点。这实际上就是指——"4-结点转换成红黑树结点的方式只有一种"。这样的设计规则保证了树的最小高度，简化了树的结构，保证了各种操作的效率。

2. 黑色高度规则，也就是所有路径上黑色节点的数量相同。这条规则确保了从任何一个节点到其所有叶子节点的路径上，黑色节点的数量都是相同的。这种均匀分布的黑色节点保证了红黑树的严格平衡。这同样是为了保障操作的效率。

总之，这两条规则共同工作，使得红黑树在插入、删除和查找操作时都能保持较好的平衡性，从而在保证了操作效率的同时，也保持了树的结构简洁。正是这种平衡和效率的结合，使得红黑树成为了一种在各种计算环境下广泛应用的数据结构。

转换

_Gn!

我们上面讲过红黑树是2-3-4 树的一种简化实现，实际上它们之间确实是存在对应的关系。但这种对应的关系不是一一对应，1比1的，而是一棵2-3-4 树实际上有多种红黑树的表示形式：

这是因为2-3-4 树的 3-结点转换为红黑树时，可以倾向任意一边。

The End