22.1.1. 栈（stack）
栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶
（top）。它是后进先出（LIFO）的。对栈的基本操作只有 push（进栈）和 pop（出栈）两种，
前者相当于插入，后者相当于删除最后的元素。
22.1.2. 队列（queue）
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的
后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为
队尾，进行删除操作的端称为队头。
22.1.3. 链表（Link）
链表是一种数据结构，和数组同级。比如，Java 中我们使用的 ArrayList，其实现原理是数组。而
LinkedList 的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。
22.1.4. 散列表（Hash Table）
散列表（Hash table，也叫哈希表）是一种查找算法，与链表、树等算法不同的是，散列表算法
在查找时不需要进行一系列和关键字（关键字是数据元素中某个数据项的值，用以标识一个数据
元素）的比较操作。
散列表算法希望能尽量做到不经过任何比较，通过一次存取就能得到所查找的数据元素，因而必
须要在数据元素的存储位置和它的关键字（可用 key 表示）之间建立一个确定的对应关系，使每个
关键字和散列表中一个唯一的存储位置相对应。因此在查找时，只要根据这个对应关系找到给定
关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用 h(key)表示)。
用的构造散列函数的方法有：
（
1）直接定址法： 取关键字或关键字的某个线性函数值为散列地址。
即：h(key) = key 或 h(key) = a * key + b，其中 a 和 b 为常数。
（
2）数字分析法
（
3）平方取值法： 取关键字平方后的中间几位为散列地址。
（
4）折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址。
（
5）除留余数法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址，
即：h(key) = key MOD p p ≤ m
（
6）随机数法：选择一个随机函数，取关键字的随机函数值为它的散列地址，
即：h(key) = random(key)
22.1.5. 排序二叉树
首先如果普通二叉树每个节点满足：左子树所有节点值小于它的根节点值，且右子树所有节点值
大于它的根节点值，则这样的二叉树就是排序二叉树。
22.1.5.1. 插入操作
首先要从根节点开始往下找到自己要插入的位置（即新节点的父节点）；具体流程是：新节点与
当前节点比较，如果相同则表示已经存在且不能再重复插入；如果小于当前节点，则到左子树中13/01/2022
Page 247 of 283
寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可；如果
大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到
当前节点的右子树即可。
22.1.5.2. 删除操作
删除操作主要分为三种情况，即要删除的节点无子节点，要删除的节点只有一个子节点，要删除
的节点有两个子节点。
1. 对于要删除的节点无子节点可以直接删除，即让其父节点将该子节点置空即可。
2. 对于要删除的节点只有一个子节点，则替换要删除的节点为其子节点。
3. 对于要删除的节点有两个子节点，则首先找该节点的替换节点（即右子树中最小的节点），
接着替换要删除的节点为替换节点，然后删除替换节点。
22.1.5.3. 查询操作
查找操作的主要流程为：先和根节点比较，如果相同就返回，如果小于根节点则到左子树中
递归查找，如果大于根节点则到右子树中递归查找。因此在排序二叉树中可以很容易获取最
大（最右最深子节点）和最小（最左最深子节点）值。
22.1.6. 红黑树
R-B Tree，全称是 Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每
个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
22.1.6.1. 红黑树的特性
（
1）每个节点或者是黑色，或者是红色。
（
2）根节点是黑色。
（
3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL 或NULL)的叶子节点！]
（
4）如果一个节点是红色的，则它的子节点必须是黑色的。
（
5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
22.1.6.1. 左旋
对 x 进行左旋，意味着，将“
x 的右孩子”设为“
x 的父亲节点”；即，将 x 变成了一个左节点(x
成了为 z 的左孩子)！。 因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”
LEFT-ROTATE(T, x)
y ← right[x] // 前提：这里假设 x 的右孩子为 y。下面开始正式操作
right[x] ← left[y] // 将 “
p[left[y]] ← x // 将 “
p[y] ← p[x] // 将 “
if p[x] = nil[T]
y 的左孩子” 设为 “
x 的右孩子”，即 将β设为 x 的右孩子
x” 设为 “
y 的左孩子的父亲”，即 将β的父亲设为 x
x 的父亲” 设为 “
y 的父亲”
then root[T] ← y // 情况 1：如果 “
else if x = left[p[x]]
x 的父亲” 是空节点，则将 y 设为根节点
then left[p[x]] ← y // 情况 2：如果 x 是它父节点的左孩子，则将 y 设为“
x 的父节点
的左孩子”
else right[p[x]] ← y // 情况 3：(x 是它父节点的右孩子) 将 y 设为“
x 的父节点的右孩
子”
left[y] ← x // 将 “
p[x] ← y // 将 “
x” 设为 “
y 的左孩子”
x 的父节点” 设为 “
y
22.1.6.1. 右旋
对 x 进行右旋，意味着，将“
x 的左孩子”设为“
x 的父亲节点”；即，将 x 变成了一个右节点(x
成了为 y 的右孩子)！ 因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。
RIGHT-ROTATE(T, y)
x ← left[y] // 前提：这里假设 y 的左孩子为 x。下面开始正式操作
left[y] ← right[x] // 将 “
p[right[x]] ← y // 将 “
x 的右孩子” 设为 “
y 的左孩子”，即 将β设为 y 的左孩子
y” 设为 “
x 的右孩子的父亲”，即 将β的父亲设为 y
p[x] ← p[y]
if p[y] = nil[T]
// 将 “
y 的父亲” 设为 “
x 的父亲”
then root[T] ← x // 情况 1：如果 “
else if y = right[p[y]]
y 的父亲” 是空节点，则将 x 设为根节点
then right[p[y]] ← x // 情况 2：如果 y 是它父节点的右孩子，则将 x 设为“
y 的父节
点的左孩子”
else left[p[y]] ← x // 情况 3：(y 是它父节点的左孩子) 将 x 设为“
y 的父节点的左孩
子”
right[x] ← y // 将 “
p[y] ← x // 将 “
y” 设为 “
x 的右孩子”
y 的父节点” 设为 “
x”
22.1.6.1. 添加
第一步: 将红黑树当作一颗二叉查找树，将节点插入。
第二步：将插入的节点着色为"红色"。
根据被插入节点的父节点的情况，可以将"当节点 z 被着色为红色节点，并插入二叉树"划分为三
种情况来处理。
① 情况说明：被插入的节点是根节点。
处理方法：直接把此节点涂为黑色。
② 情况说明：被插入的节点的父节点是黑色。
处理方法：什么也不需要做。节点被插入后，仍然是红黑树。13/01/2022
Page 251 of 283
③ 情况说明：被插入的节点的父节点是红色。这种情况下，被插入节点是一定存在非空祖父节点
的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节
点本身就是黑色节点)。理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为 3
种情况(Case)
第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树22.1.6.2. 删除第一步：将红黑树当作一颗二叉查找树，将节点删除。这和"删除常规二叉查找树中删除节点的方法是一样的"。分 3 种情况：① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就 OK 了。② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复“该节点的内容”；之后，删除“它的后继节点”。第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来该树，使之重新成为一棵红黑树。选择重着色 3 种情况。① 情况说明：x 是“红+黑”节点。处理方法：直接把 x 设为黑色，结束。此时红黑树性质全部恢复。② 情况说明：x 是“黑+黑”节点，且 x 是根。处理方法：什么都不做，结束。此时红黑树性质全部恢复。③ 情况说明：x 是“黑+黑”节点，且 x 不是根。处理方法：这种情况又可以划分为 4 种子情况。这 4 种子情况如下表所示
