紅黑樹(Red Black Tree)
? 紅黑樹也是一種自平衡的二叉搜索樹
以前也叫做平衡二叉B樹(Symmetric Binary B-tree)
?紅黑樹必須滿足以下 5 條性質(zhì)
1.節(jié)點是RED或者BLACK
2.根節(jié)點是BLACK
3.葉子節(jié)點(外部節(jié)點安皱，空節(jié)點)都是BLACK
4.RED 節(jié)點的子節(jié)點都是 BLACK
?RED 節(jié)點的 parent 都是 BLACK
? 從根節(jié)點到葉子節(jié)點的所有路徑上不能有 2 個連續(xù)的 RED 節(jié)點
5.從任一節(jié)點到葉子節(jié)點的所有路徑都包含相同數(shù)目的BLACK節(jié)點
? 為何這些規(guī)則下徐伐，就能保證平衡?
請問下面這棵是紅黑樹么?
?紅黑樹必須滿足以下 5 條性質(zhì)
1.節(jié)點是RED或者BLACK
2.根節(jié)點是BLACK
3.葉子節(jié)點(外部節(jié)點，空節(jié)點)都是BLACK
4.RED 節(jié)點的子節(jié)點都是 BLACK
?RED 節(jié)點的 parent 都是 BLACK
? 從根節(jié)點到葉子節(jié)點的所有路徑上不能有 2 個連續(xù)的 RED 節(jié)點
5.從任一節(jié)點到葉子節(jié)點的所有路徑都包含相同數(shù)目的BLACK節(jié)點
不是活尊，不滿足第5條性質(zhì)，38后面有null子葉博脑，根節(jié)點到38這個節(jié)點包含的BLACK節(jié)點數(shù)與其他不一樣饲嗽。
紅黑樹的等價變換
?紅黑樹 和 4階B樹(2-3-4樹)具有等價性
?BLACK 節(jié)點與它的 RED 子節(jié)點融合在一起，形成1個B樹節(jié)點
?紅黑樹的 BLACK 節(jié)點個數(shù) 與 4階B樹的節(jié)點總個數(shù) 相等
?網(wǎng)上有些教程:用 2-3樹 與 紅黑樹 進行類比卵凑，這是極其不嚴謹?shù)模?-3樹 并不能完美匹配 紅黑樹 的所有情況
?注意:因為PPT界面空間有限庆聘，后面展示的紅黑樹都會省略NULL 節(jié)點
紅黑樹 vs 2-3-4樹
?思考:如果上圖最底層的BLACK 節(jié)點是不存在的，在B樹中是什么樣的情形?
整棵B樹只有1個節(jié)點勺卢，而且是超級節(jié)點
幾個英文單詞
? parent:父節(jié)點
? sibling:兄弟節(jié)點
? uncle:叔父節(jié)點( parent 的兄弟節(jié)點)
? grand:祖父節(jié)點( parent 的父節(jié)點)
一些輔助函數(shù)
private Node<E> color(Node<E> node, boolean color) {
if (node == null) return node;
((RBNode<E>)node).color = color;
return node;
}
private Node<E> red(Node<E> node) {
return color(node, RED);
}
private Node<E> black(Node<E> node) {
return color(node, BLACK);
}
private boolean colorOf(Node<E> node) {
return node == null ? BLACK : ((RBNode<E>)node).color;
}
private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}
private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}
public Node<E> sibling() {
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
添加
?已知
B樹中伙判，新元素必定是添加到葉子節(jié)點中
4階B樹所有節(jié)點的元素個數(shù) x 都符合 1 ≤ x ≤ 3
? 建議新添加的節(jié)點默認為 RED，這樣能夠讓紅黑樹的性質(zhì)盡快滿足(性質(zhì) 1值漫、2澳腹、3织盼、5 都滿足，性質(zhì) 4 不一定)
?如果添加的是根節(jié)點酱塔，染成BLACK 即可
添加的所有情況
? 有 4 種情況滿足紅黑樹的性質(zhì) 4 :parent 為 BLACK
同樣也滿足 4階B樹 的性質(zhì)
因此不用做任何額外處理
? 有 8 種情況不滿足紅黑樹的性質(zhì) 4 :parent 為 RED( Double Red )
其中前 4 種屬于B樹節(jié)點上溢的情況
添加 – 修復(fù)性質(zhì)4 – LL\RR
?判定條件:uncle 不是RED
1.parent 染成 BLACK沥邻，grand 染成 RED
2.grand 進行單旋操作
LL:右旋轉(zhuǎn)
RR:左旋轉(zhuǎn)
添加 – 修復(fù)性質(zhì)4 – LR\RL
?判定條件:uncle 不是RED
- 自己染成BLACK，grand染成RED
- 進行雙旋操作
LR:parent 左旋轉(zhuǎn)羊娃， grand 右旋轉(zhuǎn)
RL:parent 右旋轉(zhuǎn)唐全， grand 左旋轉(zhuǎn)
添加 – 修復(fù)性質(zhì)4 – 上溢 – LL
?判定條件:uncle 是RED
1parent、uncle 染成 BLACK
2.grand 向上合并
染成 RED蕊玷，當做是新添加的節(jié)點進行處理
?grand 向上合并時邮利，可能繼續(xù)發(fā)生上溢
? 若上溢持續(xù)到根節(jié)點，只需將根節(jié)點染成 BLACK
添加 – 修復(fù)性質(zhì)4 – 上溢 – RR
?判定條件:uncle 是RED
1.parent垃帅、uncle 染成 BLACK
2.grand 向上合并
染成 RED延届，當做是新添加的節(jié)點進行處理
添加 – 修復(fù)性質(zhì)4 – 上溢 – LR
?判定條件:uncle 是RED
- parent、uncle 染成 BLACK
- grand 向上合并
染成 RED贸诚，當做是新添加的節(jié)點進行處理
添加 – 修復(fù)性質(zhì)4 – 上溢 – RL
?判定條件:uncle 是RED
- parent方庭、uncle 染成 BLACK
- grand 向上合并
染成 RED，當做是新添加的節(jié)點進行處理
@Override
protected void afterAdd(Node<E> node) {
Node<E> parent = node.parent;
// 添加的是根節(jié)點 或者 上溢到達了根節(jié)點
if (parent == null) {
black(node);
return;
}
// 如果父節(jié)點是黑色酱固，直接返回
if (isBlack(parent)) return;
// 以上已經(jīng)處理前4種情況
// 中間4種
// 叔父節(jié)點
Node<E> uncle = parent.sibling();
// 祖父節(jié)點
Node<E> grand = red(parent.parent);
if (isRed(uncle)) { // 叔父節(jié)點是紅色【B樹節(jié)點上溢】
black(parent);
black(uncle);
// 把祖父節(jié)點當做是新添加的節(jié)點
afterAdd(grand);
return;
}
// 最后四種
// 叔父節(jié)點不是紅色
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
black(parent);
} else { // LR
black(node);
rotateLeft(parent);
}
rotateRight(grand);
} else { // R
if (node.isLeftChild()) { // RL
black(node);
rotateRight(parent);
} else { // RR
black(parent);
}
rotateLeft(grand);
}
}
static void test1() {
Integer data[] = new Integer[] {
55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50
};
RBTree<Integer> rb = new RBTree<>();
for (int i = 0; i < data.length; i++) {
rb.add(data[I]);
System.out.println("【" + data[i] + "】");
BinaryTrees.println(rb);
System.out.println("---------------------------------------");
}
}
刪除
? B樹中械念，最后真正被刪除的元素都在葉子節(jié)點中
刪除 – RED節(jié)點
? 直接刪除，不用作任何調(diào)整
刪除 – BLACK節(jié)點
?有 3 種情況
擁有 2 個 RED 子節(jié)點的 BLACK 節(jié)點
? 不可能被直接刪除运悲，因為會找它的子節(jié)點替代刪除
? 因此不用考慮這種情況
擁有 1 個 RED 子節(jié)點的 BLACK 節(jié)點
BLACK 葉子節(jié)點
刪除 – 擁有1個RED子節(jié)點的BLACK節(jié)點
? 判定條件:用以替代的子節(jié)點是 RED
?將替代的子節(jié)點染成BLACK 即可保持紅黑樹性質(zhì)
刪除 – BLACK葉子節(jié)點 – sibling為BLACK
?BLACK 葉子節(jié)點被刪除后龄减，會導(dǎo)致B樹節(jié)點下溢(比如刪除88)
? 如果 sibling 至少有 1 個 RED 子節(jié)點
進行旋轉(zhuǎn)操作
旋轉(zhuǎn)之后的中心節(jié)點繼承 parent 的顏色
旋轉(zhuǎn)之后的左右節(jié)點染為 BLACK
? 判定條件:sibling 沒有 1 個 RED 子節(jié)點
? 將 sibling 染成 RED、parent 染成 BLACK 即可修復(fù)紅黑樹性質(zhì)
? 如果 parent 是 BLACK
會導(dǎo)致parent 也下溢
這時只需要把 parent 當做被刪除的節(jié)點處理即可
刪除 – BLACK葉子節(jié)點 – sibling為RED
? 如果 sibling 是 RED
sibling 染成 BLACK班眯，parent 染成 RED希停，進行旋轉(zhuǎn)
于是又回到 sibling 是 BLACK 的情況
@Override
protected void afterRemove(Node<E> node) {
// 如果刪除的節(jié)點是紅色
// 或者 用以取代刪除節(jié)點的子節(jié)點是紅色
if (isRed(node)) {
black(node);
return;
}
Node<E> parent = node.parent;
// 刪除的是根節(jié)點
if (parent == null) return;
// 刪除的是黑色葉子節(jié)點【下溢】
// 判斷被刪除的node是左還是右
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
if (left) { // 被刪除的節(jié)點在左邊，兄弟節(jié)點在右邊
if (isRed(sibling)) { // 兄弟節(jié)點是紅色
black(sibling);
red(parent);
rotateLeft(parent);
// 更換兄弟
sibling = parent.right;
}
// 兄弟節(jié)點必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟節(jié)點沒有1個紅色子節(jié)點鳖敷，父節(jié)點要向下跟兄弟節(jié)點合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else { // 兄弟節(jié)點至少有1個紅色子節(jié)點脖苏，向兄弟節(jié)點借元素
// 兄弟節(jié)點的左邊是黑色，兄弟要先旋轉(zhuǎn)
if (isBlack(sibling.right)) {
rotateRight(sibling);
sibling = parent.right;
}
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
} else { // 被刪除的節(jié)點在右邊定踱，兄弟節(jié)點在左邊
if (isRed(sibling)) { // 兄弟節(jié)點是紅色
black(sibling);
red(parent);
rotateRight(parent);
// 更換兄弟
sibling = parent.left;
}
// 兄弟節(jié)點必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟節(jié)點沒有1個紅色子節(jié)點棍潘，父節(jié)點要向下跟兄弟節(jié)點合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else { // 兄弟節(jié)點至少有1個紅色子節(jié)點，向兄弟節(jié)點借元素
// 兄弟節(jié)點的左邊是黑色崖媚，兄弟要先旋轉(zhuǎn)
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
static void test() {
Integer data[] = new Integer[] {
55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50
};
System.out.println("--------------------------------------- 紅黑樹 - 添加");
RBTree<Integer> rb = new RBTree<>();
for (int i = 0; i < data.length; i++) {
rb.add(data[i]);// 添加
}
BinaryTrees.println(rb);
for (int i = 0; i < data.length; i++) {
rb.remove(data[i]);// 刪除
System.out.println("--------------------------------------- 紅黑樹 - 刪除");
System.out.println("【" + data[i] + "】");
BinaryTrees.println(rb);
}
}
驗證：http://520it.com/binarytrees/
紅黑樹的平衡
? 最初遺留的困惑：為何那5條性質(zhì)亦歉，就能保證紅黑樹是平衡的?
那5條性質(zhì)，可以保證 紅黑樹 等價于 4階B樹
? 相比AVL樹畅哑，紅黑樹的平衡標準比較寬松：沒有一條路徑會大于其他路徑的2倍
? 是一種弱平衡肴楷、黑高度平衡
? 紅黑樹的最大高度是 2 ? log2(n + 1) ，依然是 O(logn) 級別
平均時間復(fù)雜度
? 搜索:O(logn)
?添加:O(logn)荠呐，O(1) 次的旋轉(zhuǎn)操作
?刪除:O(logn)赛蔫，O(1) 次的旋轉(zhuǎn)操作
AVL樹 vs 紅黑樹
?AVL樹
平衡標準比較嚴格:每個左右子樹的高度差不超過1
最大高度是 1.44 ? log2 n + 2 ? 1.328(100W個節(jié)點砂客，AVL樹最大樹高28)
搜索、添加呵恢、刪除都是 O(logn) 復(fù)雜度鞠值，其中添加僅需 O(1) 次旋轉(zhuǎn)調(diào)整、刪除最多需要 O(logn) 次旋轉(zhuǎn)調(diào)整
? 紅黑樹
平衡標準比較寬松:沒有一條路徑會大于其他路徑的2倍
最大高度是 2 ? log2(n + 1)( 100W個節(jié)點渗钉，紅黑樹最大樹高40)
搜索彤恶、添加、刪除都是 O(logn) 復(fù)雜度鳄橘，其中添加声离、刪除都僅需 O(1) 次旋轉(zhuǎn)調(diào)整
? 搜索的次數(shù)遠遠大于插入和刪除，選擇AVL樹;搜索瘫怜、插入术徊、刪除次數(shù)幾乎差不多，選擇紅黑樹
? 相對于AVL樹來說宝磨，紅黑樹犧牲了部分平衡性以換取插入/刪除操作時少量的旋轉(zhuǎn)操作弧关，整體來說性能要優(yōu)于AVL樹
? 紅黑樹的平均統(tǒng)計性能優(yōu)于AVL樹，實際應(yīng)用中更多選擇使用紅黑樹
BST vs AVL Tree vs Red Black Tree
10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96
