简介
红黑树是平衡二叉查找树的一种,前面我们提到,非平衡的 BST,在只有随机插入和查询的情况下,时间复杂度是 $O(\log n)$ 的,然而,如果同时存在随机插入和随机删除,那么时间复杂度会退化到 $O(\sqrt n)$,这是我们无法接受的。
红黑树在插入和删除时,会维持树的平衡,即保证树的高度在 $[\log n, \log(n + 1)]$,理论上极端情况可能树高最大会到达 $2 * \log n$,实际上很难遇到(尽管这样,还是保证了 $O(\log n)$ 的增删查改时间复杂度。
红黑树其实是 2-3 查找树或者 2-3-4 查找树的一种二叉树的实现方式。其中基于 2-3 树实现的红黑树被称为左倾红黑树(Left-Leaning Red-Black Trees, LLRB),基于 2-3-4 树实现的就是普通的红黑树,左倾红黑树实现起来比红黑树更简单一些(《算法 第四版》里面也主要讲的左倾红黑树),因此先讲左倾红黑树。
2-3 查找树
在普通的二叉树中,非叶子结点可以有一个或者两个子结点,如果没有子结点,那么就是叶子结点。
而 2-3 查找树的限制要严格很多。我们将拥有一个 key 和两个链接 的结点称为 2- 结点,拥有两个 key 和三个链接的结点称为 3- 结点。
- 2- 结点含有一个 key,两个 link;
- 3- 结点含有两个不同的 key,三个 link。
3- 结点含有两个 key($key_1 < key_2$),三个链接,左链接指向 2-3 树中的 key 都小于 $key_1$,中间链接指向的 2-3 树中的 key 都满足 $key_1 < key < key_2$,右链接指向的 2-3 树中的 key 都大于 $key_2$。
2-3 查找树只能由 2- 结点或者 3- 结点组成(这里不统计空结点(null)),可以看到 2-3 查找树的限制是非常严格的,这也让它可以拥有一些非常理想的性质。
一颗完美平衡的 2-3 查找树中所有空结点(null)到根结点的距离都应该是相同的,后续我们都使用 2-3 树指代一颗完美平衡的 2-3 查找树。(其他情况下表示的可能是一种更一般的结构)。
查找
将二叉查找树的查找算法一般化就能得到 2-3 树的查找算法。
向 2- 结点中插入新 key
首先进行一次未命中的查找,如果未命中的查找结束于一个 2- 结点,那么我们往这个 2- 结点中插入新的 key,使这个 2- 结点变成 3- 结点就好了,不影响所有结点的树高。
插入 key 时,由于 2-3 树的性质,我们必定是在叶子结点处执行插入。
向 3- 结点中插入新的 key
1. 向一个只含有一个 3- 结点的树中插入新 key
先组成一个临时的 4- 结点,然后将 4- 结点中的三个 key 中间的 key 上移作为剩下的 3- 结点的父结点。如下图所示:
注意到,这样操作之后,2-3 树的高度 $+1$ 了,所有原来位置的结点高度均 $+1$。
2. 向一个父结点为 2- 结点的 3- 结点中插入新 key
还是先组成一个临时的 4- 结点,然后将 4- 结点的三个 key 中中间的 key 上移,将这个 key 插入到本来为 2-结点的父结点组成 3- 结点,树的高度不变,如下图所示:
3. 向一个父结点为 3- 结点的 3- 结点中插入新 key
还是先组成一个临时的 4- 结点,然后将 4- 结点的三个 key 中中间的 key 上移,即将这个 key 插入到父结点中:此时情形就可以转化成 $1$ 或者 $2$ 或者 $3$。
如果转换成 $3$,那么就相当于是递归操作。
因此,对于 $3$ 这一插入类型,我们可以从递归的角度去理解它,递归终止条件就是切换到情形 $1$ 或者 $2$,每次递归中执行的操作就是构成一个临时的 4- 结点,然后将 4- 结点的三个 key 中中间的 key 上移,插入到父结点中。
如下图所示:
从插入操作我们可以分析得出,对 2-3 树来说,插入操作不会破坏它的完美平衡!要么整棵树的高度不变,要么整颗树的高度 $+1$,因此,根结点到所有 null 结点的长度依旧是相同的。
2-3 树的树高介于 $\log n$ 和 $\log_3 n$ 之间。
删除结点
待会再自己写,《算法 第四版》上并没有写。。。
总结
直接实现 2-3 树比较复杂,执行插入、删除操作时要维护和变换的信息比较多,可能性能还不如普通的二叉查找树。
尽管我们可以用不同的数据类型表示 2- 结点和 3- 结点并写出变换所需的代码,但用这种直白的表示方法实现大多数的操作并不方便,因为需要处理的情况实在太多。我们需要维护两种不同类型的结点,将被查找的键和结点中的每个键进行比较,将链接和其他信息从一种结点复制到另一种结点,将结点从一种数据类型转换到另一种数据类型,等等。实现这些不仅需要大量的代码,而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。
左倾红黑树(LLRB)
红黑树的基本思想是用标准的二叉查找树(结点都是 2- 结点),以及一些额外的信息(用来替换 3- 结点)来表示 2-3 树。
我们将树中的 link 分为两类,一类是 red link 将两个 2- 结点连接起来,就构成了一个 3- 结点,合法的 LLRB 要求只有父结点和左子结点之间的 link 才能是红色的;另一类是 black link 将两个 2- 结点连接起来,对应 2-3 树中的普通 link。
准确说,我们将 3- 结点表示为由一个左斜的 red link 相连的两个 2- 结点,如所示,我们可以直接使用标准 BST 的 get
方法。
LLRB 的另一种定义是含有 red 和 black link 并且满足下列条件的二叉查找树:
- red link 均为左斜 link;
- 没有一个结点同时和两条 red link 相连;
- 该树是完美黑色平衡的,即任意 null 结点到根结点的路径上的 black link 数量相同。
如果我们将一颗 LLRB 中的 red link 画平,那么所有 null 结点到根结点的距离都将是相同的。
由于每个结点都只有一个父结点,因此对每个结点来说,从它的父结点到它自身的 link 是唯一的,因此我们可以将 link 的颜色保存再表示结点的类 Node 的布尔成员变量 color 中。我们规定 null link 是黑色的
const bool kRed = true;
const bool kBlack = false;
class Node {
private:
int key_;
int val_;
int cnt_;
bool color_;
Node *left_;
Node *right_;
public:
Node(int key, int val, int cnt, bool color) :
key_(key), val_(val), cnt_(cnt), color_(color), left_(nullptr), right_(nullptr) {
}
private:
bool isRed(Node *x) {
if (x == nullptr) {
return false;
}
return x->color_ == kRed;
}
};
标签:结点,插入,查找,link,key,红黑树
From: https://www.cnblogs.com/zwyyy456/p/17502175.html