前言
紅黑樹是一種二叉查找樹，二叉查找樹就不再贅述，分析性能時需要研究最差性能，一般的二叉查找樹有時會退化成線性表，比如順序插入時。那么就需要保證二叉查找樹的平衡性，比如AVL樹，但是要嚴(yán)格保證這種平衡需要的代價太高了，由此我們先引出2-3查找樹。
2-3查找樹
定義：
- 2-結(jié)點， 含有一個鍵（及對應(yīng)的值）和兩條鏈接，左鏈接指向的2-3子樹中的鍵都小于該結(jié)點，右鏈接相反。
- 3-結(jié)點，含有兩個鍵（以及對應(yīng)的值）和三條鏈接，指向的子樹與2-結(jié)點類似。
2-3樹的查找就不用多說了，敘述一下如何插入。
2-3查找樹的插入
插入總是在葉子結(jié)點發(fā)生，包括兩種情況，插入的結(jié)點為2-結(jié)點或者3-結(jié)點，如果是前者，直接插入即可，如果為后者，先暫時形成4-結(jié)點，然后轉(zhuǎn)換為3個2-結(jié)點。
此時又分兩種情況，插入結(jié)點的父節(jié)點為2-結(jié)點或者3-結(jié)點，如果是前者，將轉(zhuǎn)換形成的父結(jié)點插入之前的父結(jié)點。
如果父結(jié)點為3-結(jié)點，重復(fù)結(jié)點為2-結(jié)點的過程，那么父結(jié)點就會形成4結(jié)點，轉(zhuǎn)換為3-結(jié)點，重復(fù)已上過程，直到不再形成4-結(jié)點，若直到根結(jié)點還是4-結(jié)點，將之轉(zhuǎn)換為3個2-結(jié)點，此時樹高加一。
將一個4-結(jié)點分解為2-3樹可能有6中情況，此處不再贅述，可參考書中P273。
全局性質(zhì)：
- 局部變換不會影響全局有序性和平衡性：任意空鏈接到根結(jié)點的路徑長度都是相等的。
- 2-3查找樹的增長是自下向上的。
紅黑樹
前文所述的2-3查找樹實現(xiàn)起來需要維護兩種不同類型的結(jié)點，實現(xiàn)操作并不統(tǒng)一，情況太多，比較麻煩。為此，我們需要“紅黑二叉查找樹”的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)它。
基本思想
用標(biāo)準(zhǔn)的二叉查找樹（完全由2-結(jié)點構(gòu)成）和一些額外的信息（替換3-結(jié)點）來表示2-3樹。我們講樹中的鏈接分為兩種類型：紅鏈接將兩個2-結(jié)點連接起來構(gòu)成一個3-結(jié)點，黑鏈接則是2-3樹中的普通鏈接。確切的說，我們講3-結(jié)點表示為由一條左斜的紅色鏈接相連的兩個2-結(jié)點。
- 紅鏈接均為左連接
- 沒有任何一個結(jié)點同時和兩條紅鏈接相連
- 該樹是完美黑色平衡的
Node定義
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
Key key; //鍵
Value val; //值
Node left, right; //左右鏈接
int N; //這顆子樹中的結(jié)點總數(shù)
boolean color; //由父結(jié)點指向它的鏈接的顏色
public Node(Key key, Value val, int N, boolean color) {
this.key = key;
this.val = val;
this.N = N;
this.color = color;
}
}
private boolean isRed(Node x) {
if (x == null) return false;
return x.color == RED;
}
轉(zhuǎn)換操作
我們需要這些操作來保持紅黑樹的兩個重要性質(zhì)， 不存在兩條連續(xù)的紅鏈接和紅色的右鏈接。
2-結(jié)點插入
我們向2-3樹中插入新鍵時，總是插入到已經(jīng)存在的葉子結(jié)點，或者是2-結(jié)點，或者是3-結(jié)點，所以在紅黑樹中新插入的結(jié)點總是紅色的。
對于2-結(jié)點的插入直接形成3-結(jié)點，新鍵對于原有鍵或左邊或右邊。對應(yīng)于紅黑樹，新鍵成為3-結(jié)點中原有鍵的左子樹或者右子樹，其中右子樹的情況需要調(diào)整，因為我們規(guī)定只存在左斜的紅色鏈接，用上文轉(zhuǎn)換操作中的rotateLeft(Node h)即可
3-結(jié)點插入
3-結(jié)點的插入有3中情況，左中右。對應(yīng)于紅黑樹中，會有一下這幾種情況：
插入實現(xiàn)
public class RedBlackBST<Key extends Comparable<Key>, Value> {
private Node root;
private class Node //見前文
private boolean isRed(Node h) //見前文
private Node rotateLeft(Node h)
private Node rotateRight(Node h)
private void flipColors(Node h)
private int size() {
return size(root);
}
private int size(Node h) {
if (h == null) return 0;
return h.N;
}
public void put(Key key, Value val) {
//查找key, 找到則更新其值，否則為它新建一個結(jié)點
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val) {
if (h == null) {
//沒找到，新鍵結(jié)點，注意color為RED
return new Node(key, val, 1, RED);
}
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
}
//2-結(jié)點右插入以及3-結(jié)點中插入的調(diào)整
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
//3-結(jié)點左插入的調(diào)整
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
//3-結(jié)點右插入以及3-結(jié)點左插入調(diào)整后的
if (isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.left) + size(h.right) + 1;
return h;
}
紅黑樹的刪除
首先，需要說明的是，2-3樹是完美平衡的，即就是說，非葉子結(jié)點不存在空鏈接。
我們先來看看怎么實現(xiàn)deleteMin()：
剛才說過非葉子結(jié)點不存在空鏈接，如果我們刪除的2-結(jié)點，那么就麻煩了，不能直接刪除，為什么？因為2-3樹中最小的點是在左下角，如果這個結(jié)點是2-結(jié)點，直接刪除的話，它的父結(jié)點會出現(xiàn)空鏈接，破壞了2-3樹的完美平衡性。那么該怎么辦？如果這個結(jié)點是3-結(jié)點，那么我直接刪除就好了，所以我們可不可能把2-結(jié)點轉(zhuǎn)換為3-結(jié)點？所以，在沿著左連接向下的過程中：
- 如果當(dāng)前結(jié)點的左子結(jié)點不是2-結(jié)點，完成；
- 如果當(dāng)前結(jié)點的左子結(jié)點是2-結(jié)點而它的親兄弟結(jié)點不是2-結(jié)點，將左子結(jié)點的兄弟結(jié)點中的一個鍵移動到左子結(jié)點中（其實是將它移動到父親節(jié)點，而父親結(jié)點的鍵移動到左子結(jié)點）；
- 如果當(dāng)前結(jié)點的左子結(jié)點和它的親兄弟結(jié)點都是2-結(jié)點，將它們?nèi)齻€合并為一個臨時的4-結(jié)點，使父結(jié)點由3-結(jié)點變成2-結(jié)點或者由4-結(jié)點變成3-結(jié)點。（由上向下的過程我們允許臨時生成4-結(jié)點，因為隨后的由下向上的過程會分解）
deleteMin()實現(xiàn)
public Node deleteMin() {
if (!isRed(root.left) && !isRed(root.right)) {
root.color = RED;
}
root = deleteMin(root)
if (!isEmpty()) root.color = BLACK;
}
private Node deleteMin(Node h) {
if (h.left == null)
return null; //找到了最小的，刪除
//如果當(dāng)前結(jié)點不是3-結(jié)點并且它的左孩子不是一個3-結(jié)點，需要調(diào)整
if (!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);
//遞歸刪除
h.left = deleteMin(h.left);
//借鍵以及融合過程中產(chǎn)生連續(xù)的以及右斜的紅鏈接需要調(diào)整
return balance(h);
}
private Node moveRedLeft(Node h) {
//融合當(dāng)前結(jié)點，左孩子，右孩子為新的4-結(jié)點
flipColors(h);
//如果右孩子是3-結(jié)點，這個時候需要上述的借鍵給左孩子
if (isRed(h.right.left)) {
h.right = rotateRight(h.right);
h.rotateLeft(h);
}
return h;
}
private Node balance(Node h) {
//右斜紅鏈接調(diào)整
if (isRed(h.right)) h = rotateLeft(h);
//連續(xù)的紅鏈接調(diào)整
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h)
//4-結(jié)點調(diào)整
if ()isRed(h.left && isRed(h.right)) flipColors(h);
return h;
}
deleteMax()實現(xiàn)
刪除最大鍵的過程與刪除最小鍵的過程類似，但有一點需要注意，樹中紅色鏈接都是左斜的。如果最大鍵在3-結(jié)點，不能直接刪除，rotateRight(h)處理一下。我們可以在自上向下的過程中將根結(jié)點右子樹的紅鏈接右斜，然后遞歸返回時自下向上的修正即可。
public void deleteMax() {
if (!isRed(root.left) && !isRed(root.right)) {
root.color = RED;
}
root = deleteMax(root);
if (!isEmpty()) root.color = BLACK;
}
private Node deleteMax(Node h) {
//h的紅鏈接右斜
if (isRed(h.left))
h = rotateRight(h);
if (h.right == null)
return null;
//h的紅鏈接右斜，右孩子的紅鏈接還是左斜的（如果有）
if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);
h.right = deleteMax(h.right);
return balance(h);
}
private Node moveRedRight(Node h) {
flipColors(h);
if (!isRed(h.left.left))
h = rotateRight(h);
return h;
}
delete()實現(xiàn)
在查找路徑上進行與刪除最小鍵相同的變換可以保證在查找過程中任意當(dāng)前結(jié)點均不是2-結(jié)點。如果被查找的鍵在樹的底部，可以直接刪除。如果不在，需要將它與它的后繼結(jié)點（即它的右子樹的最小鍵）交換，因為是遞歸調(diào)用，刪除之后回溯分解產(chǎn)生的不合法的紅色鏈接。
public void delete(Key key) {
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = delete(root, key);
if (!isEmpty()) root.color = BLACK;
}
public Node delete(Node h, Key key) {
if (key,compareTo(h.key) < 0) {
if (!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);
h.left = delete(h.left, key);
} else {
//保證鏈接右斜，因為刪除鍵在3-結(jié)點中的右邊時需要調(diào)整
if (isRed(h.left))
h = rotateRight(h);
//找到了，并且在葉子結(jié)點可以直接刪除，在向下查找的過程中，已經(jīng)保證了結(jié)點不可能是2-結(jié)點
//只需要檢查右孩子即可，因為如果左孩子非空，右孩子空只可能是3-結(jié)點，然而3-結(jié)點的紅鏈接已經(jīng)右斜了
if (key.compareTo(h.key) == 0 && (h.right == null))
return null;
//右子樹遍歷時保證結(jié)點非2-結(jié)點
if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRIght(h);
//找到了，將結(jié)點替換為后繼結(jié)點
if (key.compareTo(h.key) == 0) {
Node x = min(h.right);
h.key = x.key;
h.val = x.val;
h.right = deleteMin(h.right);
}
沒找到，繼續(xù)在右子樹找
else h.right = delete(h.right, key);
}
//處理非法紅色鏈接
return balance(h);
}
private Node min(Node h) {
if (h == null) return h;
else return min(h.left);
}
性能
紅黑樹的查找，插入均在log(n)級別
