Goal: get a search tree data structure that we can insert, delete and search in O(log n). That means we want a tree that's guaranteed to be O(log(n)) in height.
Examples:
- AVL trees
- 2-3 trees
- 2-3-4 trees
- B-trees
- Red-black trees ------------------ today
- Skip lists
- Treaps
Red-black trees
BST data structure with an extra color field for each node satisfying Read-black properties.
- Every node is either red or black.
- The root & leaves (nil's) are black
- Every red node has a black parent.
- All simple paths from a node x to a descendant leaf of x have same #black nodes = black-height(x).
black-height(x) does not count x itself.
The first thing we would do is to prove that these properties imply that the tree has to have height O(log(n)). 這樣就可以保證搜索是在log(n) time 解決的了赤赊。
Then, the hard part will be to make sure these properties stay true if they initially held true. 也就是說英岭，當(dāng)我們insert或者delete的時候要在O(log(n))里完成對數(shù)據(jù)的修改，并保持這些properties.
Height of red-black tree:
Red-black tree with n keys has height h 2lg(n+1) = O(lg(n))
Proof sketch
merge each read node into it's black parent 然后就得到 2-3-4 tree
除了leaves之外锅必，每個2-3-4 tree 的Node都有2個，3個或者4個子節(jié)點(diǎn)醋粟。
由于紅黑樹的第四個property 這個2-3-4 tree 的 all leaves have the same depth.
設(shè)原來紅黑樹的高為h凤价，由紅黑樹轉(zhuǎn)換成的2-3-4 tree的高為h'
n為紅黑樹中的internal node的數(shù)量
# leaves = n+1 （由于紅黑樹是一個binary tree 并且每個internal node有2個子節(jié)點(diǎn) 可用induction證）
in a 2-3-4 tree 2h' # leaves
4h'
2h' n+1
h' lg(n+1)
h 2h'
h 2lg(n+1)
Corollary
Queries(Search, Min, Max, Successor, Predecessor run in O(lg n))time in a red-black tree)
Updates
Insert & Delete
- BST operation
- color changes
- restructuring of links via rotaions.
RB-Insert(x): 以在之前的紅黑樹insert數(shù)字15為例
首先是做一個tree insert. Insert 的時候選擇紅色褥蚯。
如果之前做tree insert的時候insert 到了一個黑色node的下面凿滤，就很舒服妈橄。然而如果不是的話，我們就打破了紅黑樹的第三條property翁脆。于是我們首先考慮使用這種方法眷蚓，對上方的node重新上色。
設(shè)A,B為兩個紅色node,且A,B為唯一一對連起來的紅色node,B為A的子節(jié)點(diǎn)反番，當(dāng)A的同parente node 為紅色時一般可使用這種方法沙热。使用這種方法后可能消除問題叉钥，也可能導(dǎo)致問題向上傳遞。而且篙贸，當(dāng)A的parent為root時應(yīng)該不能使用這種方法處理沼侣。
在這種情況下，剛才那種方法不能用歉秫，我們考慮先使用right rotation(18)
rotate之后這個樹更加不平衡了，但是不急养铸，這不是我們最終的目的雁芙。
rotate之后我們得到的紅黑樹沒有打破第四條property，這是因為進(jìn)行rotate的兩個節(jié)點(diǎn)都是紅色的钞螟。
接下來我們使用left rotation(7)
由于7和10一黑一紅兔甘，簡單地rotate之后大破了第四條和第二條property。但是在rotation 完成之后將7和10的顏色換過來之后鳞滨，我們可以得到一個符合4條標(biāo)準(zhǔn)的黑紅樹洞焙。這個黑紅樹看起來就非常平衡。
在這里也可以理解剛才為什么要先進(jìn)行right rotation了拯啦。如果不進(jìn)行right rotation澡匪，直接進(jìn)行l(wèi)eft rotation，18會變成root褒链，10變成7的子節(jié)點(diǎn)唁情。然后18和7換顏色之后，10和7就成了兩個連在一起的一對甫匹。一定要讓兩個連著的紅色node在同一側(cè)然后再進(jìn)行第二次rotate甸鸟。
這個例子看到這里我基本已經(jīng)知道各種情況怎么做了，但對于一種情況有疑問兵迅，就是如果第一種辦法可以一直用到頂端怎么處理抢韭。
看了書發(fā)現(xiàn)解決方法是，在最后恍箭，無論如何刻恭，都將root設(shè)為黑色。（即insert有可能使黑色node層數(shù)加一季惯，合情合理吠各。）
Insert 代碼
具體代碼在英文版算法導(dǎo)論的315,316 頁。
delete 代碼
因為delete部分是自己看書的所以暫時就沒有例子了
RB-TRANSPLANT(T, u, v)
if u.p = T.nil
T.root = v
elseif u == u.p.left
u.p.left = v
else u.p.right = v
v.p = u.p
這個TRANSPLANT和之前普通的BST的TRANSPLANT有所不同勉抓。本來最后一行v.p = u.p之前是有一行if的贾漏。說是，如果v不是T.nil的話v.p = u.p藕筋。這樣改的原因應(yīng)該是纵散，紅黑樹里面的nil不是不同的nil,是key value 為nil的記錄了數(shù)個variable的object。
RB-DELETE(T, z)
y = z
y-original-color = y.color
if z.left == T.nil
x = z.right
RB-TRANSPLANT(T, z, z.left)
elseif z.right == T.nil
x = z.left
RB-TRANSPLANT(T, z, z.right)
else y = TREE-MINIMUM(z.right)
y-original-color = y.color
x = y.right
if y.p == z
x.p = y
else RB-TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.p = y
RB-TRANSPLANT(T, z, y)
y.left = z.left
y.left.p = y
y.color = z.color
if y-original-color == BLACK
RB- DELETE-FIXUP(T, x)
第一個if和elseif中先把需要刪除的node左側(cè)為空和右側(cè)為空的情況討論清楚了。但是其實(shí)存在問題伍掀。如果需要刪除的node本為紅色掰茶，那這樣刪除之后，我們依然可以得到一個符合4條規(guī)矩的紅黑樹蜜笤。但是濒蒋，如果我們刪除的是一個黑色node，那property 4大概率被打破（如果刪的不是root）把兔，property 3可能被打破（如果p為紅沪伙，且子節(jié)點(diǎn)中帶紅），property 2可能被打破（如果刪除root）县好。感覺最后修復(fù)起來围橡，可以先按是不是root分類，但還是很復(fù)雜缕贡。
在這前兩種情況下翁授，y-original-color是需要刪除的節(jié)點(diǎn)的初始顏色，x是頂替位置的節(jié)點(diǎn)晾咪。
在最后一個else里面收擦，y-original-color是頂替位置的節(jié)點(diǎn)（右側(cè)最小的節(jié)點(diǎn)）的初始顏色，x是y右側(cè)的子節(jié)點(diǎn)禀酱。整個流程大致和tree-delete是一致的炬守，只是x.p = y一行讓我覺得是沒有意義的。比較有意思的是最終頂替節(jié)點(diǎn)的顏色變成和原節(jié)點(diǎn)一致剂跟。也就是說减途，如果y本來的顏色是紅色，根據(jù)property 4曹洽，y本來下面只能跟兩個nil鳍置，這樣一番操作之后，得到的是一個沒有任何問題的紅黑樹送淆。如果y本來是黑色税产，那右側(cè)可以跟一個紅色node（有可能打破3，一定會打破4偷崩，但是容易修復(fù)辟拷，只要把這個紅色node最后變成黑色就好），也可以跟一個nil（這種情況一定且僅僅會打破4阐斜，不知道怎么修復(fù)）衫冻。
前兩種情況（刪除黑節(jié)點(diǎn)時）：
如果刪的是root，且頂替節(jié)點(diǎn)為紅谒出，只需將頂替節(jié)點(diǎn)變黑就好隅俘。如果頂替節(jié)點(diǎn)為黑邻奠，不用作任何改變。
如果刪的不是root为居，且頂替節(jié)點(diǎn)為紅碌宴，只需將頂替節(jié)點(diǎn)變黑就好。如果頂替節(jié)點(diǎn)為黑蒙畴，頂替的一定是nil贰镣。等同說其中一條枝干缺了一個黑色node，不知道如何處理膳凝。
最后一種情況（刪除黑節(jié)點(diǎn)時）：
和前兩種情況幾乎一致八孝，只是修改顏色的node變成了頂替y位置的節(jié)點(diǎn)。上面已經(jīng)分析過了鸠项，同樣也是有一種十分棘手的情況。
RB-DELETE-FIXUP(T, x)
while x ≠ T.root and x.color == BLACK
if x == x.p.left
w = x.p.right
if w.color == RED
w.color = BLACK //case 1
x.p.color = RED //case 1
LEFT-ROTATE(T, x.p) //case 1
w = x.p.right //case 1
if w.left.color == BLACK and w.right.color == BLACK
w.color = RED //case 2
x = x.p //case 2
else
if w.right.color == BLACK
w.left.color = BLACK //case 3
w.color = RED //case 3
RIGHT-TOTATE(T, w) //case 3
w = w.p.right //case 3
w.color = x.p.color //case 4
x.p.color = BLACK //case 4
w.right.color = BLACK //case 4
LEFT-ROTATE(T, x.p) //case 4
x = T.root //case 4
else(same as then clause with "right" and "left" exchanged)
x.color = BLACK
在這個fixup里面沒有把之前的兩種情況分出來子姜，而是將它看成一個問題解決了祟绊。其實(shí)也很有道理，因為出問題的總是左邊為nil哥捕，用右邊node頂替的地方牧抽。那要出一個general的解法，那一定是先看看有沒有問題（被頂替位置不是root就一定有問題遥赚，是root的話也要分情況）扬舒，有問題的話看看能不能靠換顏色解決，如果不能那要解決的問題就變成了以x為末枝的那一條少了一個黑色的node凫佛。
看過代碼之后發(fā)現(xiàn)讲坎，沒有問題的情況和有情況但簡單換顏色能解決的情況不會進(jìn)入while loop。十分簡單的解決了愧薛。后面使用loop和4種case都是為了解決x為黑色（nil）,且x這一條少了一個黑色node的問題晨炕。
對想出紅黑樹的人表示服氣。大方向好好想想也不是不能想到毫炉，但能在知道大方向的前提下找到一種切實(shí)可行的方法瓮栗，實(shí)在是厲害。
