平衡搜索樹（BST），所有操作的Θ(lgn)
（平衡樹有可能不是二叉樹，這一節(jié)只討論二叉樹的情況）
有多重平衡樹結(jié)構(gòu)
- AVL trees
- 2-3 trees
- 2-3-4 trees
- B trees
- Red-black trees
- Skip lists
- Treaps
紅黑樹 Red-black trees
BST的一種
- 每個(gè)結(jié)點(diǎn)有一個(gè)色域，要么為黑結(jié)點(diǎn)，要么為紅結(jié)點(diǎn)
- 根節(jié)點(diǎn)和葉子結(jié)點(diǎn)都為黑結(jié)點(diǎn)
- 每個(gè)紅結(jié)點(diǎn)的父親都為黑結(jié)點(diǎn)，即不可能出現(xiàn)兩個(gè)紅色結(jié)點(diǎn)相連的情況
- 從根節(jié)點(diǎn)到任意葉節(jié)點(diǎn)的路徑中的黑色結(jié)點(diǎn)數(shù)目相等，這個(gè)數(shù)目也稱為黑高度
由以上性質(zhì)，可以保證紅黑樹的高度為O(lgn)
Example.
證明
將紅黑樹的所有紅結(jié)點(diǎn)，都與其父節(jié)點(diǎn)（黑）合并，可以得到一顆2-3-4 tree（即每個(gè)結(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目為2~4個(gè)）
并且所有節(jié)點(diǎn)的高度都是黑節(jié)點(diǎn)的高度，也就是所有葉子節(jié)點(diǎn)有相同的深度，意味著樹是平衡的
假設(shè)整棵樹高度為h，那么葉子結(jié)點(diǎn)數(shù)應(yīng)為h2~h4
原紅黑樹的葉子結(jié)點(diǎn)個(gè)數(shù)為帶鍵值結(jié)點(diǎn)個(gè)數(shù)n+1（平衡樹葉子節(jié)點(diǎn)的數(shù)量總是內(nèi)部節(jié)點(diǎn)的數(shù)量加1）
leaf = n+1 | n是key的數(shù)量
=> h'2 <= n+1 <= h'4
=> h' <= lg n+1
樹最高情況是紅黑相間的時(shí)候，因此其高度最高只有h <= 2h' <= 2lg n+1
樹的高度為O(lgn)
樹操作
紅黑樹的查詢操作和普通BST一樣，刪除和插入操作則相對(duì)復(fù)雜
我們要保證紅黑樹的性質(zhì)，因?yàn)檫@些性質(zhì)是紅黑樹為平衡樹的保證，能夠保證紅黑樹的高度為Olgn，這樣紅黑樹的基本操作都可以保證在O(lgn)的時(shí)間復(fù)雜度內(nèi)完成
為了保持紅黑性需要三種操作
- BST操作
- 改變節(jié)點(diǎn)顏色
- 利用旋轉(zhuǎn)改變節(jié)點(diǎn)關(guān)系
旋轉(zhuǎn)
保持二叉搜索樹的性質(zhì)，并且只需要常數(shù)時(shí)間
LEFT_ROTATE(T,x)
y = right[x] //獲取右孩子
rihgt[x] = left[y] //設(shè)置x的右孩子為y的左孩子
if left[y] != NIL
then parent[left[x]] = x
parent[y] = parent[x] //設(shè)置y的父節(jié)點(diǎn)為x的父節(jié)點(diǎn)
if parent[x] == NIL
then root[T] = y
else if x==left[parent[x]
then left[parent[x]] = y
else right[[parent[x]] = y
left[y] = x //設(shè)置y的左孩子為x
parent[x] =y
插入
插入一個(gè)新結(jié)點(diǎn)的過程是在二叉查找樹插入過程的基礎(chǔ)上改進(jìn)的，先按照二叉排序的插入過程插入到紅黑樹中，然后將新插入的結(jié)點(diǎn)標(biāo)記為紅色（插入黑色會(huì)影響樹的深度，很容易破壞紅黑性質(zhì)，標(biāo)記紅色只可能影響性質(zhì)3）。然后調(diào)整結(jié)點(diǎn)并重新著色，使得滿足紅黑樹的性質(zhì)。
如果每次插入新的結(jié)點(diǎn)z導(dǎo)致紅黑樹性質(zhì)被破壞，最多只有一個(gè)性質(zhì)被破壞，并且不是性質(zhì)2就是性質(zhì)4。違反性質(zhì)2是因?yàn)閦是根且為紅色，只需要改變跟節(jié)點(diǎn)的顏色，違反性質(zhì)4是因?yàn)閦和其父節(jié)點(diǎn)parent[z]都是紅色的。
以下分析的大前提是z的父結(jié)點(diǎn)是紅色，建立在z的父結(jié)點(diǎn)是左孩子基礎(chǔ)上（相反情況類似，不做分析）
插入后有多種情況
情況1：z的叔叔結(jié)點(diǎn)y是紅色的
此時(shí)父節(jié)點(diǎn)parent[z] A和叔叔節(jié)點(diǎn)y D都是紅色的，解決辦法是將z的父節(jié)點(diǎn)parent[z] A和叔叔結(jié)點(diǎn)y D都變?yōu)楹谏?，將z的祖父結(jié)點(diǎn)parent[parent[z]] C變?yōu)榧t色，然后從祖父結(jié)點(diǎn)parent[parent[z]] C繼續(xù)向上判斷是否破壞紅黑樹的性質(zhì)
情況2：z的叔叔y是黑色的，而且z是右孩子
情況3：z的叔叔y是黑色的，而且z是左孩子
情況2和情況3中叔叔節(jié)點(diǎn)y D都是黑色的，通過z是左孩子還是右孩子進(jìn)行區(qū)分的。可以將情況2通過旋轉(zhuǎn)為情況3。情況2中z是右孩子，旋轉(zhuǎn)后成為情況3，使得z變?yōu)樽蠛⒆?，可以在parent[z]結(jié)點(diǎn)出使用一次左旋轉(zhuǎn)來完成。
無論是間接還是直接的通過情況2進(jìn)入到情況3，z的叔叔y總是黑色的。在情況3中，將父節(jié)點(diǎn)parent[z] B著為黑色，祖父節(jié)點(diǎn)parent[parent[z]] C著為紅色，然后從祖父節(jié)點(diǎn)parent[parent[z]] C處進(jìn)行一次右旋轉(zhuǎn)。
RB_INSERT(T,z)
y = NIL
x =root(T)
while x != NIL
do y=x
if key[z]<key[x]
then x=left[x]
else x=right[x]
parent[z] = y
if y =NIL
then root =z
else if key[z] < key[y]
then left[y] =z
else right[y] =z
left[z] = NIL
right[z] =NIL
color[z] = RED //新插入結(jié)點(diǎn)標(biāo)記為紅色
RB_INSERT_FIXUP(T,z) //進(jìn)行調(diào)整，使得滿足紅黑樹性質(zhì)
RB_INSERT_FIXUP(T,z)
while color[parent[z]] = RED
do if parent[z] == left[parent[parent[z]]]
then y = right[parent[parent[z]]]
if color[y] == RED //情況1，z的叔叔為紅色
then color[parent[z]] = BLACK
color[y] = BLACK
color[parent[parent[z]]=RED
z= parent[parent[z]]
else if z == right[parent[z]] //情況2，z的叔叔為黑色，z為右孩子
then z = parent[z]
LEFT_ROTATE(T,z)
color[parent[z]]=BLACK //情況3，z的叔叔為黑色，z為左孩子
color[parent[parent[z]] = RED
RIGHT_ROTATE(T, parent[parent[z]])
else (same as then clause with “right” and “l(fā)eft” exchanged)
color(root(T)) = BLACK; //將根結(jié)點(diǎn)設(shè)置為黑色
