第七章-查找

reallylearning2026/5/28大约 36 分钟

第七章-查找

7.1 查找的基本概念

查找。在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找结果分为两种：一是查找成功，即在数据集合中找到了满足条件的数据元素；二是查找失败。
查找表。用于查找的数据集合称为查找表，由同一类型的数据元素组成，可以是数组、链表等数据类型。对查找表经常进行的操作一般有4种：①查询某个特定的数据元素是否在查找表中；②检索满足条件的某个特定的数据元素的各种属性；③在查找表中插入一个数据元素；④从查找表中删除某个数据元素。
静态查找表。若一个查找表的操作只涉及上述操作①和②，则无须动态地修改查找表，此类查找表称为静态查找表。与此对应，需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、哈希查找等；适合动态查找表的查找方法有二叉排序树的查找、哈希查找等。
关键字。数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如“学号”这一数据项唯一地标识一名学生。
平均查找长度。在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为：$$ASL = \sum_{i=1}^nP_iC_i$$式中， $n$ 是查找表的长度； $P_i$ 是查找第 $i$ 个数据元素的概率，一般认为每个数据元素的查找概率相等，即 $P_i=l/n$ ； $C_i$ 是找到第 $i$ 个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

7.2 顺序查找和折半查找

7.2.1 顺序查找

顺序查找又称线性查找，主要用于在线性表中进行查找。顺序查找通常分为：
1、对一般的无序线性表的顺序查找；
2、对按关键字有序的顺序表的顺序查找。

一般线性表的顺序查找

作为一种最直观的查找方法，其基本思想是
1. 从线性表的一端开始，逐个检查关键字是否满足给定的条件。
2. 若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；
3. 若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。
下面给出其算法：

typedef struct{ //查找表的数据结构
    ElemType *elem; //元素存储空间基址，建表时按实际长度分配，从1号位置开始存储
    int TableLen; //表的长度
}SSTable;
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key; //哨兵
    for(i=ST.TableLen;ST.elem[i]!=key;--i); //从后向前查找
    return i; //若表中不存在关键字为key的元素，将查找到i为0时退出for循环
}

上述算法中，将 ST.elem[0] 称为哨兵，引入它的目的是使得 Search_Seq 内的循环不必判断数组是否会越界。算法从尾部开始查找，若找到 ST.elem[i]==key 则返回 i 值，查找成功。否则一定在查找到 ST.elem[0]==key 时跳出循环，此时返回的是 0，查找失败。在程序中引入 “哨兵”，可以避免很多不必要的判断语句，从而提高程序效率。
对于有 n 个元素的表，给定值 key 与表中第 $i$ 个元素相等，即定位第 $i$ 个元素时，需进行 $n-i+1$ 次关键字的比较，即 $C_i = n-i+1$ 。
查找成功时，顺序查找的平均长度为：

\mathrm{ASL}_{i\text{成功}}=\sum_{i=1}^nP_i(n-i+1)

当每个元素的查找概率相等，即 $P_i = 1/n$ 时，有：

\mathrm{ASL}_{i\text{成功}}=\sum_{i=1}^{n}P_{i}(n-i+1)=\frac{n+1}{2}

查找不成功时，与表中各关键字的比较次数显然是 $n+1$ 次，即：

\mathrm{ASL}_{i\text{不成功}}=n+1

通常，查找表中记录的查找概率并不相等。若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由大至小重新排列。

综上所述，顺序查找的缺点是当 $n$ 较大时，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用。同时还需注意，对链表只能进行顺序查找。

有序表的顺序查找

若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。
假设表L是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为key，当查找到第i个元素时，发现第i个元素对应的关键字小于key，但第i+1个元素对应的关键字大于key，这时就可返回查找失败的信息，因为第i个元素之后的元素的关键字均大于key，所以表中不存在关键字为key的元素。

二叉树表示

可以用如图 $7.1$ 所示的判定树来描述有序顺序表的查找过程：

树中的圆形结点表示有序顺序表中存在的元素；树中的矩形结点称为失败结点(若有n个结点，则相应地有 $n+1$ 个查找失败结点)，它描述的是那些不在表中的数据值的集合。若查找到失败结点，则说明查找不成功。
在有序表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时，查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数。查找不成功的平均查找长度在相等查找概率的情形下为：

\mathrm{ASL}_{\text{不成功}}=\sum_{j=1}^{n}q_{j}(l_{j}-1)=\frac{1+2+\cdots+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}

上式中， $q_j$ 是到达第 $j$ 个失败结点的概率，在相等查找概率的情形下，它为 $\frac{1}{n+1}$ ， $l_j$ 是第 $j$ 个失败结点所在的层数。

注意

有序表的顺序查找和下面的折半查找的思想是不一样的，且有序表的顺序查找中的线性表可以是链式存储结构，而折半查找中的线性表只能是顺序存储。

7.2.2 折半查找

折半查找又称二分查找，它仅适用于有序的顺序表，其基本思想如下：
1. 首先将给定值key与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；
2. 若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分。
3. 然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
算法如下：
常规循环实现：

int Binary_Search(SeqList L,ElemType key){
    int low=0,high=L.TableLen-1,mid;
    while(low<=high){
        mid=(low+high)/2; //取中间位置
        if(L.elem[mid]==key)
            return mid; //查找成功则返回所在位置
        else if(L.elem[mid]>key)
            high=mid-1; //从前半部分继续查找
        else
            low=mid+1; //从后半部分继续查找
    }
    return -1; //查找失败，返回-1
}

递归实现：

#include <iostream>
using namespace std;

// 有序表定义
struct SSTable {
    int* elem;
    int length;
};
// 折半查找 递归算法
int BinarySearch(SSTable ST, int low, int high, int key) {
    // 查找失败
    if (low > high)
        return 0;
    // 求中间位置
    int mid = (low + high) / 2;
    // 找到
    if (key == ST.elem[mid])
        return mid;
    // 递归左半区
    else if (key < ST.elem[mid])
        return BinarySearch(ST, low, mid - 1, key);
    // 递归右半区
    else
        return BinarySearch(ST, mid + 1, high, key);
}

二叉判定树表示

折半查找的过程可用图 $7.2$ 所示的二叉树来描述，称为判定树：

树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况。

从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左子结点值，且均小于其右子结点值。若有序序列有 $n$ 个元素，则对应的判定树有 $n$ 个圆形的非叶结点和 $n+1$ 个方形的叶结点。
判定树是一棵平衡二叉树。用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率查找时，查找成功的平均查找长度为：

\mathrm{ASL}=\frac{1}{n}\sum_{i=1}^nl_i=\frac{1}{n}\left(1\times1+2\times2+\cdots+h\times2^{n-1}\right)=\frac{n+1}{n}\log_2(n+1)-1\approx\log_2(n+1)-1

式中， $h$ 是树的高度，并且元素个数为 $n$ 时树高 $h=[\log_2(n+1)]$ 。所以折半查找的时间复杂度为 $O(log_2n)$ ，平均情况下比顺序查找的效率高。
因为折半查找需要方便地定位查找区域，所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。

常考问题总结

查找失败的比较次数

最多/坏比较次数：公式： $H=\lfloor \log_2n \rfloor+1$ ，
以 $n=16=2^4$ 为例， $H=4+1=\boldsymbol5$ 次，等于判定树高度。
最少比较次数： $H - 1=\lfloor \log_2n \rfloor$ ，
以 $n=16=2^4$ 为例， $H-1=4$ 次，落在判定树最浅层的外部节点。

平均查找长度ASL

成功查找： $\boldsymbol{ASL_{成功}\approx \log_2(n+1)-1}$
失败查找： $\boldsymbol{ASL_{失败}\approx \log_2(n+1)}$
时间复杂度：统一为 $\boldsymbol{O(\log_2 n)}$

7.2.3 分块查找

分块查找也称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。
基本思想是：将查找表分为若干子块。块内的元素可以无序，但块之间是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

分块查找的过程分为两步：

在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表。注意，若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指分块中查找。
在块内顺序查找。
例如关键码集合为 ${88,24,72,61,21,6,32,11,8,31,22,83,78,54}$ ，按照关键码值 $24,54,78,88$ ，分为 $4$ 个块和索引表，如图 $7.3$ 所示：

分块查找的平均查找长度为索引查找和块内查找的平均长度之和，设索引查找和块内查找的平均查找长度分别为 $L_I$ ， $L_S$ ，则分块查找的平均查找长度为：

\mathrm{ASL}=L_{\mathrm{I}}+L_{\mathrm{S}}

将长度为 $n$ 的查找表均匀地分为 $b$ 块，每块有 $s$ 个记录，在等概率情况下，
若在块内和索引表中均采用顺序查找，则平均查找长度为：

\mathrm{ASL}=L_{\mathrm{I}}+L_{\mathrm{S}}={\frac{b+1}{2}}+{\frac{s+1}{2}}={\frac{s^{2}+2s+n}{2s}}

此时，若 $s=\sqrt{n}$ ，则平均查找长度取最小值 $\sqrt{n+1}$ ；
若对索引表采用折半查找时，则平均查找长度为：

\mathrm{ASL}=L_{\mathrm{I}}+L_{\mathrm{S}}=\log_2(b+1)+{\frac{s+1}{2}}

7.3 树形查找

7.3.1 二叉排序树(BST)

构造一棵二叉排序树的目的并不是排序，而是提高查找、插入和删除关键字的速度，二叉排序树这种非线性结构也有利于插入和删除的实现。

1. 二叉排序树的定义

二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：

若左子树非空，则左子树上所有结点的值均小于根结点的值。
若右子树非空，则右子树上所有结点的值均大于根结点的值。
左、右子树也分别是一棵二叉排序树。
根据二叉排序树的定义，左子树结点值 < 根结点值 < 右子树结点值，因此对二叉排序树进行中序遍历，可以得到一个递增的有序序列。
结点定义代码：

typedef struct BiTNode {
    int data; // 节点数据
    struct BiTNode *lchild, *rchild; // 左右子节点指针
} BiTNode, *BiTree;

2. 二叉排序树的查找

二叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过程。若二叉排序树非空，先将给定值与根结点的关键字比较，若相等，则查找成功；若不等，若小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。这显然是一个递归的过程。
二叉排序树的非递归查找算法：

BSTNode *BST_Search(BiTree T, ElemType key) {
    while (T != NULL && key != T->data) {   // 若树空或等于根结点值，则结束循环
        if (key < T->data)
            T = T->lchild;                  // 小于，则在左子树上查找
        else
            T = T->rchild;                  // 大于，则在右子树上查找
    }
    return T;
}

二叉排序树的查找怎么用递归算法实现？

// 递归查找函数
BiTree BST_Search(BiTree T, int key) {
   if (T == NULL) {
       return NULL; // 树为空或未找到目标节点
   }
   if (key == T->data) {
       return T; // 找到目标节点
   } else if (key < T->data) {
       return BST_Search(T->lchild, key); // 在左子树中继续查找
   } else {
       return BST_Search(T->rchild, key); // 在右子树中继续查找
   }
}

3. 二叉排序树的插入

二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字值等于给定值的结点时再进行插入的。

插入结点的过程如下：若原二叉排序树为空，则直接插入；否则，若关键字 $k$ 小于根结点值，则插入到左子树，若关键字 $k$ 大于根结点值，则插入到右子树。新插入的结点一定是一个叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。
二叉排序树插入算法：

// 二叉排序树插入
int BSTInsert(BiTree &T, int k) {
    if (T == NULL) {
        // 树为空，直接创建新结点作为根
        T = (BSTree)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return 1;
    } else if (k == T->data) {
        // 关键字已存在，插入失败
        return 0;
    } else if (k < T->data) {
        // 小于根结点，插入左子树
        return BSTInsert(T->lchild, k);
    } else {
        // 大于根结点，插入右子树
        return BSTInsert(T->rchild, k);
    }
}

4. 二叉排序树的构造

构造二叉排序树的算法实现：

// 构造二叉排序树的算法描述如下：
void Creat_BST(BiTree &T, KeyType str[], int n) {
    T = NULL;                      // 初始时 T 为空树
    int i = 0;
    while (i < n) {                // 依次将每个关键字插入二叉排序树
        BST_Insert(T, str[i]);
        i++;
    }
}

5. 二叉排序树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操作的实现过程按 3 种情况来处理：

若被删除结点 $z$ 是叶结点，则直接删除，不会破坏二叉排序树的性质。
若结点 $z$ 只有一棵左子树或右子树，则让 $z$ 的子树成为 $z$ 父结点的子树，替代 $z$ 的位置。
若结点 $z$ 有左、右两棵子树，则令 $z$ 的直接后继（或直接前驱，即在中序遍历序列中在 $z$ 旁边的两个元素）替代 $z$ ，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。
删除代码实现：

BSTNode* FindMin(BSTNode* root) {  
    BSTNode* cur = root;  
    while (cur && cur->left) {  
        cur = cur->left;  
    }  
    return cur;  
}  
  
BSTNode* BSTDelete(BSTNode* root, int key) {  
    if (root == nullptr) {  
        return nullptr;  
    }  
    if (key < root->key) {  
        root->left = BSTDelete(root->left, key);  
        return root;  
    }  
    if (key > root->key) {  
        root->right = BSTDelete(root->right, key);  
        return root;  
    }  
  
    if (root->left == nullptr && root->right == nullptr) {  
        delete root;  
        return nullptr;  
    }  
    if (root->left == nullptr || root->right == nullptr) {  
        BSTNode* child = (root->left != nullptr) ? root->left : root->right;  
        delete root;  
        return child;  
    }  
  
    BSTNode* succ = FindMin(root->right);  
    root->key = succ->key;  
    root->right = BSTDelete(root->right, succ->key);  
    return root;  
}

6. 二叉排序树的查找效率分析

二叉排序树的查找效率，主要取决于树的高度。
最好的情况（平衡二叉树）： $n$ 个节点的二叉树最小高度为 $O(\log_2 n)+1$ ，平均查找长度为 $O(\log_2 n)$
在最坏情况：每个节点只有一个分支，树的高度=节点数= $n$ ，则其平均查找长度为 $O(\frac{n+1}{2})$ ，如图 $7.4(b)$ 所示。

在等概率情况下，图 $7.4(a)$ 查找成功的平均查找长度为

\text{ASL}_a = (1 + 2 \times 2 + 3 \times 4 + 4 \times 3)/10 = 2.9

而图 $7.4(b)$ 查找成功的平均查找长度为

\text{ASL}_b = (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10)/10 = 5.5

如何计算查找失败的

ASL

计算查找失败的 $ASL$ 要补齐失败节点，之后只看失败节点即可，层数要看其父节点所在的层数来计算，总数为失败节点总数，以图 $7.4$ 为例构建可得

在等概率情况下，图 $7.4(a)$ 查找失败的的平均查找长度为$$ASL_{失败}=\frac{7\times3+2\times4}{9}= \frac{29}{9}\approx3.22$$

而图 $7.4(b)$ 查找失败的平均查找长度为$$\text{ASL} = \frac{2\times3 + 3 + 4 + 5 + 6 + 7\times2}{9} = 4.22$$

从查找过程看，二叉排序树与二分查找相似。就平均时间性能而言，二叉排序树上的查找和二分查找差不多。但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树，如图 $7.4$ 所示。
就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，平均执行时间为 $O(\log_2 n)$ 。二分查找的对象是有序顺序表，若有插入和删除结点的操作，所花的代价是 $O(n)$ 。当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其查找操作；若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

7.3.2 平衡二叉树

1. 平衡二叉树的定义

平衡二叉树是一种特殊的二叉搜索树，它具有自平衡的特性，保持了树的左右子树高度相差不超过1的特性。这种平衡性质确保了在最坏情况下的插入、删除和查找操作的时间复杂度都为 $O(log n)$ ，其中 $n$ 是树中节点的数量，空树也是平衡二叉树。平衡二叉树（Balanced Binary Tree），也称AVL树。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是 $-1$ 、 $0$ 或 $1$ 。

2. 平衡二叉树的特点

高度平衡：任意节点的左右子树高度差不超过 $1$ ，确保树的高度近似于 $\log n$ ，从而保证了插入、删除和查找等操作的高效性。
左右子树也是平衡二叉树：平衡二叉树的左右子树也是平衡二叉树，通过递归地保持平衡性。

3. 平衡二叉树的实现

平衡二叉树的实现有多种，其中最常见的是 AVL 树和红黑树。

AVL 树：AVL 树是一种严格的平衡二叉树，它通过在插入或删除节点后进行旋转操作来保持树的平衡性。具体来说，AVL 树中任意节点的左右子树高度差的绝对值不超过1。
红黑树：前面我们提到了红黑树，它也是一种平衡二叉树，但相对于 AVL 树来说，它更加灵活一些。红黑树通过节点的颜色属性和一些规则来保持平衡，确保了树的高度近似于 $\log n$ 。
平衡二叉树常被用于需要高效的插入、删除和查找操作的场景，例如数据库系统中的索引结构和动态集合的实现。在选择平衡二叉树时，需要考虑具体应用场景和对性能的要求，以及对平衡性维护的成本。

4. 平衡二叉树的插入

二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 $1$ 的结点 $A$ ，再对以 $A$ 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

5. 调整二叉树的平衡

总结：怎么判断一颗树，需要左旋还是右旋，还是左右旋和右左旋？

先查看这颗树整体的偏坠情况，比如向左偏，再查看左子树的偏坠情况，比如向右偏，如果树和子树的偏坠方向不同，那么需要旋转两个方向，我们先把子树旋转成和整棵树一样的偏坠情况，再将整棵树进行旋转。

LL平衡旋转（右单旋转）
当在左子树中添加结点，造成不平衡时，以根结点的左孩子为中心，将根结点向右旋转
二叉树的右旋操作与左旋操作相反，是将一个节点的左子节点旋转到其父节点的位置上，同时该节点成为其左子节点的右子节点。
简单示例：

复杂一点的例子如下：
RR平衡旋转（左单旋转）
当在右子树中添加结点，造成不平衡时，以根结点的右孩子为中心，将根结点向左旋转
二叉树的左旋操作是指将一个节点的右子节点旋转到其父节点的位置上，同时该节点成为其右子节点的左子节点。
简单示例：

复杂一点的例子如下：

更复杂一点的例子如下：

左/右旋代码思路：
LR平衡旋转（先左后右双旋转）
示例：
第一次左旋是以15为中心向左旋转同时将15的左孩子移动为10的右孩子
第二次右旋是以15为中心向右旋转将17及其孩子移动为15的右子树
RL平衡旋转（先右后左双旋转）
示例：

6. 平衡二叉树的删除

具体步骤：

删除结点（方法同“二叉排序树”）
- 若删除的结点是叶子，直接删。
- 若删除的结点只有一个子树，用子树顶替删除位置
- 若删除的结点有两棵子树，用前驱（或后继）结点顶替，并转换为对前驱（或后继）结点的删除。
一路向北找到最小不平衡子树，找不到就完结撒花
找最小不平衡子树下，“个头”最高的儿子、孙子
根据孙子的位置，调整平衡（LL/RR/LR/RL）
- 孙子在LL：儿子右单旋
- 孙子在RR：儿子左单旋
- 孙子在LR：孙子先左旋，再右旋
- 孙子在RL：孙子先右旋，再左旋
如果不平衡向上传导，继续步骤2
- 对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传递）
  平衡二叉树的删除操作时间复杂度为 $O(\log_2 n)$

7. 平衡二叉树的查找效率分析

假设以 $n_h$ 表示深度为 $h$ 的平衡树中含有的最少结点数，
则有 $n_0=0, n_1=1, n_2=2$ ，递推公式为 $n_h = n_{h-1} + n_{h-2} + 1$ ，
可以证明含有 $n$ 个结点的平衡二叉树的最大深度为 $O(\log_2 n)$ ，平衡二叉树的平均查找长度为 $O(\log_2 n)$

7.3.3 红黑树

1. 红黑树的定义

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个额外的属性来存储节点的颜色，可以是红色或黑色。红黑树具有以下性质：

节点颜色：每个节点要么是红色，要么是黑色。
根节点颜色：根节点必须是黑色。
叶子节点颜色：叶子节点（外部节点、NIL节点，即空节点）都是黑色。
相邻节点颜色：不能有两个相邻的红色节点，即红色节点的子节点和父节点不能同时为红色。
黑色节点路径：从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点，称为黑色节点路径相等。
节点的黑高 bh：从某一结点出发(不含该节点)到达任一空叶节点的路径上黑节点的总数。

红黑树结点代码：

struct RBnode {       // 红黑树的结点定义
    int key;          // 关键字的值
    RBnode* parent;   // 父节点指针
    RBnode* lChild;   // 左孩子指针
    RBnode* rChild;   // 右孩子指针
    int color;        // 结点颜色，如：可用 0/1 表示 黑/红，也可使用枚举型enum表示颜色
};

结论1：从根节点到叶结点的最长路径不大于最短路径的2倍

有了上面的几个性质作为限制，即可避免二叉查找树退化成单链表的情况。

但是，仅仅避免这种情况还不够，这里还要考虑某个节点到其每个叶子节点路径长度的问题。
如果某些路径长度过长，那么，在对这些路径上的及诶单进行增删查操作时，效率也会大大降低。

这个时候性质4和性质5用途就凸显了，有了这两个性质作为约束，即可保证任意节点到其每个叶子节点路径最长不会超过最短路径的2倍。原因如下：

当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（性质4限定了不能出现两个连续的红色节点）。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。

此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的2倍。

结论2：有n个内部结点的红黑树高度为

h \leq 2\log_2(n+1)

由结论1可知，从根到叶结点（不含叶结点）的任何一条简单路径上都至少有一半是黑结点，因此，根的黑高至少为 $h/2$ ，于是有 $n\ge 2^{h/2}-1$ ，即可求得结论。
由结论2也可推出，黑高为 $h$ 的红黑树的内部结点数最少是 $2^h - 1$ ，最多是 $2^{2h}-1$ 。
可见，红黑树的“适度平衡”，由 AVL 树的“高度平衡”，降低到“任意一个结点左右子树的高度，相差不超过2倍”，也降低了动态操作时调整的频率。对于一棵动态查找树，若插入和删除操作比较少，查找操作比较多，则采用 AVL 树比较合适，否则采用红黑树更合适。但由于维护这种高度平衡所付出的代价比获得的效益大得多，红黑树的实际应用更广泛，C++中的 map 和 set（Java 中的 TreeMap 和 TreeSet）就是用红黑树实现的。

2. 红黑树的搜索

红黑树和 AVL 树在搜索操作上有一些相似之处，但也有一些不同之处。
相似之处包括：
时间复杂度：在平衡状态下，红黑树和 AVL 树的搜索操作都具有相同的时间复杂度，即 $O(\log_2 n)$ ，其中 n 是树中节点的数量。
搜索过程：在进行搜索时，都是从根节点开始，按照特定的规则向左或向右递归地搜索，直到找到目标值或者搜索到叶子节点为止。

不同之处包括：
平衡条件：AVL 树严格要求每个节点的左右子树高度之差不超过1，因此它在维护平衡性方面比较严格，可能需要频繁地进行旋转操作来调整树的结构；而红黑树则是通过更加宽松的平衡条件来保持树的平衡，它只要求树的黑高度保持平衡，因此旋转操作相对较少。
旋转操作：由于 AVL 树的平衡要求更严格，因此在插入或删除节点时可能需要执行更多的旋转操作来保持平衡；而红黑树由于平衡条件相对宽松，所以在插入或删除节点时可能需要执行较少的旋转操作。
实现复杂度：AVL 树的实现相对红黑树来说更加复杂，因为它需要维护更加严格的平衡条件，这导致 AVL 树的插入、删除等操作可能会比红黑树稍慢一些。

总的来说，红黑树和 AVL 树都是用于解决二叉搜索树退化问题的重要数据结构，它们在搜索操作上有着相似的时间复杂度，但在细节上有一些区别。选择使用哪种结构取决于具体的应用场景和性能要求

3. 红黑树的插入

结论3：新插入的结点都设为红色的，可以简化树的平衡过程

假设新插入的结点初始着为黑色，则这个结点所在的路径比其他路径多出一个黑结点（几乎每次插入都破坏性质⑤），调整起来也比较麻烦。若插入的结点是红色的，则此时所有路径上的黑结点数量不变，仅在出现连续两个红结点时才需要调整，而且这种调整也比较简单。

假设要插入的结点是X 父结点是P 祖父结点是G 叔父结点是U

X是根结点
放入根结点中，将颜色变为黑色
X的父结点是黑色的
无需做任何调整，就是一个标准的红黑树
X的父结点是红色的
- 如果叔父结点U也是红色的，可以推断出祖父结点G必是黑色的
  当增加新结点时造成两个红色结点相邻此时使用变色处理
  P和U由从红色变为黑色 G由黑色变为红色如果G是根结点再次恢复为黑色
- 如果叔父结点U是黑色的，并且X在左侧
  以P为中心，向右旋转，G和U下移，此时如果P有右孩子，右孩子R移动到G的左孩子处
  将P变为黑色将G变为红色
- 如果叔父结点U是黑色的，并且X在右侧
  先通过左旋恢复成第二种情况然后再右旋和变色

举个例子

假设我们插入这些数据：12 23 34 40 45 67 78 89 90 100 110 120 130 140
插入12，12为根节点，根节点一定为黑；插入23，符合红黑树的基本性质，无需做出调整

插入45

不满足红色节点一定有两个黑色子节点，对12 节点左旋，23变成根，颜色变为黑色，12原来为黑色，旋转后这条路径多了一个黑色节点，所以为了满足性质5，必须将其颜色换为红色。
插入34

插入34，不满足红色节点一定有两个黑色子节点，所以将34的父节点和叔叔节点涂成黑色，祖父节点变成红色，但23是根，必须为黑色，所以如上图所示 23，12，45节点颜色为黑色
插入40

插入数据情况总结

如果插入的节点，父节点为红色，叔叔节点（插入节点的父节点的兄弟节点）为红色，那么就要把父节点和叔叔节点涂成黑色，祖父节点涂成红色（但如果是根节点涂成黑色）。
如果插入的节点，父节点为红色，父节点是祖父节点的右支，叔叔节点为黑色，且
（1）要插入的节点为父节点的右支，那么对其祖父节点左旋。
（2）要插入的节点为父节点的左支，那么对父节点先右旋，然后按照旋转后的位置重新进行规则判断，接着对其祖父节点进行左旋。
如果插入的节点，父节点为红色，父节点是祖父节点的左支，叔叔节点为黑色，且
（1）要插入的节点为父节点的左支，那么对其祖父节点右旋。
（2）要插入的节点为父节点的右支，那么对父节点先左旋，然后按照旋转后的位置重新进行规则判断，接着对其祖父节点进行右旋。（相当于如果是<，那么先左后右，如果是>,那么先右后左）

4. 红黑树的删除

如果被删除节点是叶子节点，可以直接删除。

如果删除节点是非叶子节点，那么需要找到他的前驱或后继节点，来替换掉被删除节点的键和值，再删除他的前驱或后继节点。

修复删除后的红黑树

1.被删除节点是红色

这种情况不影响红黑树的性质，可以直接删除

2.被删除节点是黑色

2.1. 兄弟节点是黑色，且兄弟节点有红色的子节点

2.1.1. 兄弟节点的左子节点是红色

此时父亲节点的右子树为空，左子树为ll（兄弟节点在父亲节点的左侧，兄弟节点的左子节点在兄弟节点的左侧 left-left），

调整方法：将兄弟节点的颜色染为原来父亲节点的颜色，再将兄弟节点的左子节点和父亲节点染为黑色，再对父亲节点右旋。

这样此子树的黑高就与删除前的黑高相等，此子树与删除前的子树相比，少了一个红色节点。

2.1.2. 兄弟节点的右子节点是红色

此时父亲节点的右子树为空，左子树为lR（left-right）

对兄弟节点进行左旋，并交换兄弟节点与兄弟节点的右子节点的颜色，

就可转换为2.1.1 的情况

2.2.兄弟节点是黑色，且兄弟节点的子节点都为黑色。

这里要特别说明，空节点也是黑色节点

2.2.1. 父节点是红色

将父亲节点染为黑色，兄弟节点染为红色即可

2.2.2. 父节点是黑色

这种情况下，被删除节点、父亲节点、和兄弟节点都是黑色，被删除节点被删除后，不能在以父节点为根节点的子树范围内，保持黑高不变，此子树黑高必须减一，再扩大调整的范围，向上继续修复红黑树。

具体操作为：将兄弟节点染为红色（以父节点为根节点的子树黑高减一），再以父亲节点为删除节点，修复红黑树。

2.3. 兄弟节点是红色

父节点必定为黑色（性质4），且必定有黑色子节点，否则黑高不平衡（性质5）

父亲节点染为红色，兄弟节点染为黑色，再对父亲节点右旋，

此时就转换成了2.2.1的情况

:::tips
在红黑树中，删除节点可能导致违反红黑树的性质，因此需要进行一系列操作来修正树的结构，以保持其平衡。根据被删除节点的不同情况，可以总结如下红黑树删除情况：

情况1：被删除节点是红色节点的情况：
- 这种情况下，删除节点不会违反红黑树的性质，因为被删除的节点是红色的，不会影响黑色节点的数量或者红黑树的黑高度。直接删除即可，不需要额外的操作。
情况2：被删除节点是黑色节点，且有一个红色子节点：
- 这种情况下，直接用红色子节点替代被删除节点，并将红色子节点染黑即可。不会破坏红黑树的性质。
情况3：被删除节点是黑色节点，且没有红色子节点：
- 这是红黑树删除操作中最复杂的情况之一，可能会导致红黑树的性质被破坏。需要通过旋转和重新着色来修正树的结构，以保持其平衡和红黑树性质：
  - 如果被删除节点是根节点，则直接删除即可。
  - 如果被删除节点是其父节点的唯一子节点，则删除该节点后，调整其父节点的颜色，使其变为红色（如果父节点原来是黑色，则删除一个黑色节点会导致黑高度不一致）。
  - 如果被删除节点有一个兄弟节点：
    - 如果兄弟节点是红色的，通过旋转和重新着色操作，将情况转化为兄弟节点是黑色的情况。
    - 如果兄弟节点是黑色的，并且兄弟节点的两个子节点都是黑色的：
      - 将兄弟节点染红，将父节点设为新的当前节点，继续进行递归操作。
    - 如果兄弟节点是黑色的，并且兄弟节点有一个红色子节点和一个黑色子节点：
      - 将兄弟节点的黑色子节点变为红色，进行适当的旋转和重新着色操作，以达到平衡。
情况4：删除的节点有两个子节点：
- 这种情况下，通常会找到被删除节点的后继节点（即比被删除节点大的最小节点），将后继节点的值复制到被删除节点上，并删除后继节点。然后处理删除后继节点的情况，转化为情况1、2或3。

总的来说，红黑树的删除操作需要注意维护红黑树的性质，主要是通过旋转和重新着色来确保树的平衡和性质不被破坏。

:::