红黑树

作者: 和风细羽 | 来源:发表于2018-11-09 18:32 被阅读0次

数据结构—树—红黑树
TreeMap
数据结构与算法-AVL 红黑树
[转载]红黑树
拿下红黑树
红黑树
彻底理解红黑树（二）之插入
彻底理解红黑树（三）之删除
Golang红黑树
数据结构红黑树添加、修改原理分析

1. 简介

红黑树（RBT）性质
①、结点非红即黑；
②、根节点是黑色；
③、所有 NULL 结点称为叶子节点，且认为颜色为黑；
④、所有红节点的子结点都为黑色；
⑤、从任一结点到其叶子节点的所有路径上都包含相同数目的黑结点。

红黑树

图上有 NIL 的为叶子节点，也可以使用一般的叶子节点，但会使算法更复杂。

所有性质 1 ~ 5 合起来约束了该树的平衡性能

红黑树上的最长路径不可能大于 2 倍最短路径。

由第 ① 条和第 ④ 条可以确定：从一个结点到其叶子节点的一条最长的路径一定是红黑交错的，而最短路径一定是纯黑色的结点；再结合第 ②、③ 条可知：最长路径 <= 2 * 最短路径。

一颗二叉树的平衡性能越好，那么它的效率越高！显然红黑树的平衡性能比 AVL 略差些。实际上红黑树的效率仍能达到 O(log₂N)。

2. 插入

插入点不能为黑结点，那样将破坏性质 ⑤，所以应插入红结点。

如果它的父结点是红的，就会破坏性质 ④，所以要做 "旋转" 操作和一些节点的变色。

为了叙述方便，给要插入的节点标为 N（红），父节点为 P，祖父节点为 G，叔节点为 U。

插入情形
1、该树为空树，直接插入根结点的位置，违反性质 ①，把结点颜色改为黑。

2、插入结点 N 的父结点 P 为黑色，不违反任何性质，无需做任何修改。

3、N、P、U 都为红，这里不论 P 是 G 的左孩子，还是右孩子；不论 N 是 P 的左孩子，还是右孩子。

情形 3

操作：如图把 P、U 改为黑色，G 改为红色，未结束。

解析：N、P 都为红，违反性质 ④；若把 P 改为黑，符合性质 ④，显然左边少了一个黑节点，违反性质 ⑤；所以把 G、U 都改为相反色，这样一来通过 G 的路径的黑节点数目没变，即符合 ④、⑤，但是 G 变红了，若 G 的父节点又是红的不就又违反了 ④。所以经过上边操作后未结束，需把 G 作为起始点，即把 G 看做一个插入的红节点继续向上检索----属于哪种情况，按那种情况操作~要么中间就结束，要么直到根结点，如果根节点变红，因为无法再向上检索，那就把它变为黑色。

4、N、P 为红，U 为黑，P 为 G 的左孩子，N 为 P 的左孩子（或者 P 为 G 的右孩子，N 为 P 的右孩子；反正就是同向的）。

情形 4

操作：如图 P、G 变色，P、G 变换即左左单旋（或者右右单旋），结束。

解析：要知道经过 P、G 变换（旋转），变换后 P 的位置就是当年 G 的位置，所以红 P 变为黑，而黑 G 变为红都是为了不违反性质 ⑤，而维持到达叶节点所包含的黑节点的数目不变！

记忆法：也就是相当于把红 N 头上的红节点移到对面黑 U 的头上；这样即符合了性质 ④ 也不违反性质 ⑤。

5、N、P 为红，U 为黑，P 为 G 的左孩子，N 为 P 的右孩子（或者 P 为 G 的右孩子，N 为 P 的左孩子；反正两方向相反）。

情形 5

操作：需要进行两次变换（旋转），图中只显示了一次变换-----首先 P、N 变换，颜色不变；然后就变成了情形 4 的情况，按照情况 4 操作，即结束。

解析：由于 P、N 都为红，经变换，不违反性质 ⑤；然后就变成 4 的情形，此时 G 与 G 现在的左孩子变色，并变换，结束。

3. 删除

需先找到“替代点”来替代删除点而被删除，也就是删除的是替代点

替代点 N 的至少有一个子节点为 NULL，可以通过一直查找 lChild 指针来确定 N。

若 N 为红色，则 N 的另一个节点 M 也为 NULL，那么直接把 N 删了，不违反任何性质，结束；

若 N 为黑色，N 的另一个节点 M 不为 NULL，则 M 一定是红色的，且 M 的子节点都为 NULL，那么把 N 删掉，M 占到 N 的位置，并改为黑色，不违反任何性质，结束；

若 N 为黑色，N 的另一个节点 M 也为 NULL，则把 N 删掉，该位置置为NULL，显然这个黑节点被删除了，破坏了性质 ⑤，那么要以 N 节点为起始点检索看看属于以下那种情况，并作相应的操作。

N 为黑点，P 为父节点，S 为兄弟节点。

删除情形
1、S 为红色（父节点 P 一定是黑，子节点一定是黑），N 是 P 的左孩子（或者 N 是 P 的右孩子）。

情形 1

操作：P、S 变色，并交换----相当于 AVL 中的 RR 型旋转，即以 P为中心S向左旋（或者是 AVL 中的 LL 型旋转），未结束。

解析：P 的左边将要少一个黑节点，这样操作相当于在 N 头上又加了一个红节点----不违反任何性质，但是到通过 N 的路径仍少了一个黑节点，需要再对 N 进行一次检索，并作相应的操作才可以平衡。

2、P、S 及 S 的孩子们都为黑。

情形 2

操作：S 改为红色，未结束。

解析：S 变为红色后，经过 S 节点的路径的黑节点数目也减少了 1，那个从 P 出发到其叶子节点到所有路径所包含的黑节点数目（记为num）相等了。但是这个num 比之前少了 1，因为左右子树中的黑节点数目都减少了！一般地，P 是他父节点 G 的一个孩子，那么由 G 到其叶子节点的黑节点数目就不相等了，所以说没有结束，需把 P 当做新的起始点开始向上检索。

3、P 为红（S一定为黑），S 的孩子们都为黑。