本文的實現(xiàn)都來自《算法導論》
所有的東西都是根據(jù)書中的思路來的晴弃，加上我自己的理解掩幢。（推薦配合書本來閱讀）。但是上鞠，這篇文章粒蜈，我不會像《算法導論》一樣逐個逐個情況地分析，我會捉住關鍵思想旗国。其實枯怖，我覺得，如果你想非常嚴謹?shù)乜疾旒t黑樹的插入能曾、刪除修復度硝，沒有什么會比《算法導論》更加好。
本文中寿冕，我假設你已經(jīng)熟悉普通二叉樹的插入蕊程、刪除算法。
修復的總體思想
-
自底向上:
1.2 對于刪除，我們會看到玫恳，它的修復一定也是從最底部開始辨赐。所有刪除情況都可以轉(zhuǎn)換成在這兩種：
1.1 對于插入驼唱，新插入的結(jié)點一定在最底部藻茂，所以修復一定從最底部開始
如果能局部（i.e. 在當前樹內(nèi)）通過旋轉(zhuǎn)或改變顏色完成修復，那么就修復它京办，并結(jié)束掀序。比如上圖，如果我們能在當前樹（i.e. 以"z"為根的樹）內(nèi)解決問題惭婿，那么我們就可以結(jié)束了不恭。
如果不能叶雹，我們改變當前樹某些結(jié)點的顏色，然后向上傳遞换吧。
從這里折晦，我們就可以看出，為什么紅黑樹在插入沾瓦、刪除頻繁的場景下比AVL樹優(yōu)满着。因為對于插入的修復，紅黑樹會一直向上傳遞暴拄，然后在適當?shù)牡胤綀?zhí)行最多兩次旋轉(zhuǎn)，然后結(jié)束编饺。對于刪除的修復乖篷，紅黑樹會一直向上傳遞，然后在適當?shù)牡胤綀?zhí)行最多三次旋轉(zhuǎn)透且，然后結(jié)束撕蔼。而AVL樹，它的插入修復策略也是一直向上傳遞秽誊，然后在適當?shù)牡胤綀?zhí)行旋轉(zhuǎn)鲸沮，然后結(jié)束；但是它的刪除修復策略是一邊向上傳遞锅论，一邊旋轉(zhuǎn)讼溺，直至到達根。
更深一步
有必要強調(diào)這個事實：
未做修改前最易，樹是滿足所有紅黑性質(zhì)的
- 刪除"z"結(jié)點后：
"z"結(jié)點的所有組先都不滿足性質(zhì)五怒坯。亦即，我們的修復有可能要涉及"z"一直到根節(jié)點這條路徑藻懒，而且剔猿，也只會涉及這條路徑。 - 插入”x"結(jié)點后：
”x"結(jié)點位于最底部嬉荆，樹中只有”x"結(jié)點這一處可能破壞了紅黑性質(zhì)归敬，然后我們向上傳遞直至能局部修復。任意時刻鄙早，我們保證樹中只有一處地方破壞了一個紅黑性質(zhì)，或是性質(zhì)四限番，或是性質(zhì)二陆爽。（這個證明在《算法導論中》，最好看一看） - 紅黑性質(zhì)對每一個結(jié)點都有約束扳缕，比如性質(zhì)五：任一個結(jié)點到它的后代葉子結(jié)點的路徑上的黑結(jié)點數(shù)量都相同慌闭。在向上傳遞時别威，很重要的一件事就是：我們必須先把當前樹的所有紅黑性質(zhì)都修復好，然后再向上傳遞驴剔。然后去到上一層后省古，我們就不再需要關心下面的樹了。這是一個回溯算法的思想丧失。只不過我們用parent來回溯豺妓。
實現(xiàn)紅黑樹的順序：
-
leftRotate(Node x) 和 rightRotate(Node y) 平衡二叉樹的左旋和右旋操作。這兩個操作在實現(xiàn)AVL樹也要用到布讹。寫代碼時琳拭，只需要把x和y當成平衡二叉樹的結(jié)點就可以了。實現(xiàn)時描验，可以參考書中的圖白嘁，非常清晰：
isValidBST()驗證是否為平衡二叉樹（這個代碼通過LeetCode測試的，應該無問題）膘流，每次調(diào)用 leftRotate() 和 rightRotate()后就驗證一次絮缅。
isValidRBT()根據(jù)紅黑樹的五個性質(zhì)逐一驗證。直接看代碼就可以了呼股，個人認為比較清晰耕魄。
insert() 找到要插入的位置，執(zhí)行插入彭谁，然后調(diào)用isValidBST()驗證是否仍為平衡二叉樹吸奴，然后調(diào)用fixAfterInsertion()，之后再調(diào)用isValidRBT()驗證是否紅黑樹缠局。
package datastru;
import java.util.Random;
//3.5 has bug
//int version
public class RedBlackTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
/**
* sentimal, used as parent of root and leaf-node
*/
private Node NIL = new Node(0, null, null, null, BLACK);
private Node root = NIL; //root of red black tree
private static class Node {
int key;
Node left;
Node right;
Node parent;
boolean color;
public Node(int key, Node left, Node right, Node parent, boolean color) {
this.key = key;
this.left = left;
this.right = right;
this.parent = parent;
this.color = color;
}
}
public void insert(int keyToInsert) {
insert(new Node(keyToInsert, NIL, NIL, NIL, RED));
}
private void insert(Node z) {
//x is used to traverse, and y is always the parent of x
Node y = NIL;
Node x = root;
while(x != NIL) {
y = x;
if(z.key < x.key)
x = x.left;
else if(z.key > x.key)
x = x.right;
else
return;
}
//let z become y's children
z.parent = y;
if(y == NIL)
/* by the way, this indicates:
This is an empty red-black-tree(i.e a tree that just contains a NIL) */
root = z;
else if(z.key < y.key)
y.left = z;
else
y.right = z;
assert isValidBST();
fixAfterInsertion(z);
assert isValidBST();
assert isRBT();
}
private void fixAfterInsertion(Node z) {
/* 紅黑樹有5個性質(zhì)
一奄抽、每個結(jié)點非紅即黑
二、根節(jié)點是黑色
三甩鳄、葉子結(jié)點是黑色
四逞度、紅結(jié)點的兩個子節(jié)點都是黑節(jié)點
五、對每個結(jié)點妙啃，從它到它的后代葉子結(jié)點的所有簡單路徑上档泽，黑節(jié)點的數(shù)量都相同
*/
/*
z為新插入的結(jié)點，它是紅色的揖赴，它的兩個孩子都是葉子節(jié)點(NIL)
所以馆匿，如果此時紅黑樹性質(zhì)被破壞，只有兩種可能：
1. z就是根節(jié)點燥滑，這破壞了性質(zhì)二
2. z和z.parent都是紅色渐北，這破壞了性質(zhì)四
*/
/*
z在這個函數(shù)中的語義：
就像下面的invariants(3)提到的，整個修復過程铭拧，紅黑樹只有一處違反了紅黑性質(zhì)
且這一處赃蛛，要么違反的是性質(zhì)二恃锉，要么違反的是性質(zhì)四。（如果你迷糊了呕臂，只要這樣想：
未插入之前破托，這是一顆紅黑樹，插入時在最底部進行的歧蒋，那么當然此時只可能在一處違反紅黑性質(zhì)土砂，
然后，我們的修復策略每次都會將這一處修復谜洽，然后向上傳遞萝映，直至能夠在某個地方完全修復，
或一直傳遞到頂部）
所以我們只需關注：z, z.parent, z的uncle
*/
/* How fix strategy works?
在情況一中：為什么能夠只通過更換顏色來修復 "z和z.parent都是紅色"
在情況二和情況三中：我們?yōu)槭裁茨軌蛲ㄟ^旋轉(zhuǎn)來修復 "z和z.parent都是紅色"
the shared answer:
對于z的兩個子樹阐虚、z.parent的一個子樹序臂、uncle的兩個子樹，
它們的根都是黑色敌呈，而且它們都具有相同的黑高
*/
/*
如果進入了循環(huán)（也就是 z.parent.color == RED 為true）贸宏，
那么我們在循環(huán)體中修復 "z和z.parent都是紅色" 造寝，
a)如果是通過情況二或情況三修復的磕洪，那么直接退出循環(huán)。
b)如果是通過情況一修復的诫龙，將z上移兩層析显。新的z將會是紅色，
那么我們在下一次循環(huán)就看下：新的z和它的父親是否都是紅色签赃，
是就繼續(xù)執(zhí)行修復谷异，否就退出循環(huán)。(i.e. 向上傳遞锦聊。歹嘹。。)
invariants:
1. z是紅色的
2. 如果z.parent為根節(jié)點孔庭，那么z.parent是黑色的（也就是性質(zhì)二沒有被破壞)
3. 如果有任何紅黑性質(zhì)被破壞尺上，則至多只有一條被破壞，或是性質(zhì)二圆到，或是性質(zhì)四怎抛。
3.1如果是性質(zhì)二，那么就是：z.parent為根節(jié)點芽淡，且z.parent是紅色的马绝，出現(xiàn)這種情況的原因是
經(jīng)過一次或多次向上傳遞(i.e. 執(zhí)行一次或多次循環(huán)體的情況一)，z從紅黑樹的底部傳到最頂部了
3.2如果是性質(zhì)四挣菲，那么就是：z和z.parent都是紅色的富稻，這正正就是while循環(huán)體要修復的
這三個invariants在：
第一次循環(huán)開始之前都成立掷邦、（初始）
在循環(huán)的每次迭代后(i.e. 每次循環(huán)體執(zhí)行完畢后)成立、（保持）
在循環(huán)終止后也成立（終止） 這能推導出一個有用的性質(zhì)
/
/
\/
invariants(3)指出要么是性質(zhì)二不成立唉窃，要么是性質(zhì)四不成立耙饰，
現(xiàn)在z的父親為黑色，那么性質(zhì)四肯定成立纹份，性質(zhì)二有可能不成立
具體場景看最后一行代碼
*/
while(z.parent.color == RED) {
//當在循環(huán)體中引用z的爺爺時苟跪，由invariants(2)可知，z的爺爺必定存在(i.e. 不為NIL)
if(z.parent == z.parent.parent.left) {
Node uncle = z.parent.parent.right;
if(uncle.color == RED) { //case 1
uncle.color = z.parent.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent; //向上傳遞
//case 1結(jié)束后有可能退出循環(huán)蔓涧，也有可能繼續(xù)循環(huán)
}
else {
if(z == z.parent.right) { //case 2件已，轉(zhuǎn)變?yōu)閏ase3
z = z.parent;
leftRotate(z);
}
//case 3:
z.parent.color = BLACK;
z.parent.parent.color = RED;
rightRotate(z.parent.parent);
//case 3結(jié)束后必定退出循環(huán)
assert z.parent.color == BLACK;
}
}
else { //與上面代碼基本一樣，對稱
if(z.parent == z.parent.parent.right) {
Node uncle = z.parent.parent.left;
if(uncle.color == RED) {
uncle.color = z.parent.color = BLACK;
z.parent.parent.color = RED;
z = z.parent.parent;
}
else {
if(z == z.parent.left) {
z = z.parent;
rightRotate(z);
}
z.parent.parent.color = RED;
z.parent.color = BLACK;
leftRotate(z.parent.parent);
assert z.parent.color == BLACK;
}
}
}
}
/*
經(jīng)過若干次迭代后元暴，如果z是根節(jié)點篷扩，且它是紅色，
那么z的父親(i.e. NIL)就是黑色茉盏，循環(huán)終止鉴未。此時性質(zhì)二不成立。
現(xiàn)在修復它：
*/
root.color = BLACK;
}
public void delete(int keyToDelete) {
Node x = root;
while(x != NIL) {
if(x.key < keyToDelete)
x = x.right;
else if(x.key > keyToDelete)
x = x.left;
else {
delete(x);
break;
}
}
}
private Node successor(Node t) {
if(t.left == NIL)
return t;
return successor(t.left);
}
private void delete(Node z) {
assert z != NIL;
if(z.left != NIL && z.right != NIL) {
Node successor = successor(z.right);
z.key = successor.key;
//not recursion, just an way to turn if-case to else-case
//and more importantly, highlight the semantic
delete(successor);
}
else {
Node x = (z.left != NIL) ? z.left : z.right; //NOTE that, x may be NIL
boolean needToFixUp = z.color == BLACK;
//make the subTree rooted at 'x' be the child of z.parent
x.parent = z.parent;
if(z.parent == NIL)
root = x;
else {
if(z.parent.left == z)
z.parent.left = x;
else
z.parent.right = x;
}
//now, x is replacement of the deleted Node
if(needToFixUp)
fixAfterDeletion(x);
}
}
private void fixAfterDeletion(Node x) {
/*
只考慮x為左孩子的情況鸠姨，x是右孩子的情況對稱铜秆。。讶迁。
*/
}
//treat x as a binary-search-tree node, left rotate it
private void leftRotate(Node x) {
assert x.right != NIL;
Node y = x.right;
Node subTree = y.left;
x.right = subTree;
if(subTree != NIL)
subTree.parent = x;
Node p = x.parent;
y.parent = p;
if(p == NIL)
root = y;
else if(p.left == x)
p.left = y;
else
p.right = y;
x.parent = y;
y.left = x;
assert isValidBST();
}
//treat y as a binary-search-tree node, right rotate it
private void rightRotate(Node y) {
assert y.left != NIL;
Node x = y.left;
Node subTree = x.right;
y.left = subTree;
if(subTree != NIL)
subTree.parent = y;
Node p = y.parent;
x.parent = p;
if(p == NIL)
root = x;
else if(p.left == y)
p.left = x;
else
p.right = x;
x.right = y;
y.parent = x;
assert isValidBST();
}
/* Debug methods: */
private boolean isRBT() {
if(root == NIL) //empty
return true;
return root.color == BLACK && isRBT(root);
}
private boolean isRBT(Node t) {
Node tp = t.parent, tl = t.left, tr = t.right;
if (tp != NIL && t != tp.left && t != tp.right)
return false;
if (tl != NIL && (tl.parent != t || tl.key > t.key))
return false;
if (tr != NIL && (tr.parent != t || tr.key < t.key))
return false;
if (t.color == RED && tl != NIL && tl.color == RED)
return false;
if (t.color == RED && tr != NIL && tr.color == RED)
return false;
if(!hasSameNumberOfBlackNodeInAllPaths(t))
return false;
//recursive check
if (tl != NIL && !isRBT(tl))
return false;
if (tr != NIL && !isRBT(tr))
return false;
return true;
}
private int expectedBlackNodeCount;
private boolean hasSameNumberOfBlackNodeInAllPaths(Node t) {
//for convenience, when computing how many black node in a path:
//root(t) is included
//leaf(NIL) is included
expectedBlackNodeCount = 1; //there must be a leaf node in any path
Node x = t;
while(x != NIL) {
if(x.color == BLACK)
expectedBlackNodeCount ++;
x = x.left;
}
return backTrack(t, 0);
}
private boolean backTrack(Node t, int count) {
if(t == NIL)
return count + 1 == expectedBlackNodeCount;
if(t.color == BLACK)
count ++;
return backTrack(t.left, count) &&
backTrack(t.right, count);
}
private boolean isValidBST(Node root, Integer lowerBound, Integer uppperBound) {
if(root == NIL)
return true;
boolean isRootInRange = (lowerBound == null || root.key > lowerBound) &&
(uppperBound == null || root.key < uppperBound);
if(!isRootInRange)
return false;
return isValidBST(root.left, lowerBound, root.key) &&
isValidBST(root.right, root.key, uppperBound);
}
private boolean isValidBST() {
return isValidBST(root, null, null);
}
/*some tests*/
private static void insertAscendly() {
RedBlackTree rbt = new RedBlackTree();
for(int i = 1; i < 1000; i ++)
rbt.insert(i);
}
private static void insertDescendly() {
RedBlackTree rbt = new RedBlackTree();
for(int i = 1000; i >= 0; i --)
rbt.insert(i);
}
private static void insertRandomly() {
RedBlackTree rbt = new RedBlackTree();
Random ra =new Random();
for (int i = 0 ;i < 1000; i++) {
rbt.insert(ra.nextInt(10000000));
}
}
private static void testDeleteWithoutFixUp() {
RedBlackTree rbt = new RedBlackTree();
Random ra =new Random();
int[] keys = new int[1000];
for (int i = 0 ;i < 1000; i++) {
keys[i] = ra.nextInt(10000000);
rbt.insert(keys[i]);
}
for(int i = 0; i < 100; i ++) {
rbt.delete(keys[i]);
}
assert rbt.isValidBST();
rbt = new RedBlackTree();
for(int i = 1000; i >= 0; i --)
rbt.insert(i);
for(int i = 1000; i >= 0; i --)
rbt.delete(i);
assert rbt.isValidBST();
rbt = new RedBlackTree();
for(int i = 0; i < 1000; i ++)
rbt.insert(i);
for(int i = 0; i < 1000; i ++)
rbt.delete(i);
assert rbt.isValidBST();
}
public static void main(String[] args) {
insertAscendly();
insertDescendly();
insertRandomly();
}
}
