目錄

• 0.樹
  0.1 一般樹的定義
  0.2 二叉樹的定義
• 1.查找樹ADT
• 2.查找樹的實現(xiàn)
  2.1 二叉查找樹
  2.2 AVL樹
  2.3 伸展樹
  2.3-1 自頂向下伸展樹
  2.4 B樹
  2.4-1 B+樹
  2.4-2 B*樹
  2.5 紅黑樹
  2.6 跳躍表
  2.7 trie樹

0 樹

0.1 一般樹的定義

為什么引入樹令花？
因為表的線性訪問時間太慢。
1）定義
遞歸的方式定義：
一棵樹是一些結(jié)點的集合凉倚。這個集合可以是空兼都；若非空，則一棵樹由稱作根的結(jié)點r以及0個或多個非空的（子）樹T1稽寒，T2扮碧，...，Tk組成杏糙，這些子樹中每一棵的根都被來自根r的一條有向的邊連接芬萍。

父親、兒子：每一棵子樹的根叫做根r的兒子搔啊，而r是每棵子樹的根的父親柬祠。
樹葉：沒有兒子的結(jié)點稱為樹葉；
兄弟：具有相同父節(jié)點為兄弟(silbing)负芋；
路徑：從結(jié)點n1到nk的路徑定義為結(jié)點n1, n2, ..., nk的一個序列漫蛔，使得1 <= i < k，結(jié)點ni是ni+1的路徑旧蛾。一棵樹中從根到每個結(jié)點恰好存在一條路徑莽龟。
路徑長：該路徑上邊的條數(shù)，n1到nk位k-1.
深度：對任意結(jié)點ni锨天，ni的深度為從根到ni的唯一路徑的長
高：是從ni到一片樹葉的最長路徑的長
祖先毯盈、后裔：如果存在從n1到n2的一條路徑，那么n1是n2的一位祖先病袄，而n2是n1的后裔搂赋；如果n1不等于n2，則各為真祖先益缠、真后裔脑奠。

2）實現(xiàn)
樹的結(jié)點聲明：

一棵樹的表示和實現(xiàn)：

3）樹的遍歷及應(yīng)用
a.先序遍歷：對結(jié)點的處理工作是在它的諸兒子結(jié)點被處理前進行的。

0.2 二叉樹的定義

二叉樹的每個結(jié)點都不能有多于兩個兒子酸休。

二叉樹結(jié)點的聲明：

二叉樹在編譯器領(lǐng)域的應(yīng)用：

1）中序遍歷：遞歸產(chǎn)生一個帶括號的左表達式，然后打印出根處的運算符祷杈，再遞歸地產(chǎn)生一個帶括號的右表達式斑司，得到一個中綴表達式
2）后序遍歷：遞歸打印出左子樹、右子樹吠式，然后打印運算符（后綴表達式）
3）前序遍歷：先打印出運算符陡厘，然后遞歸打印出左子樹和右子樹

將后綴表達式轉(zhuǎn)變成表達式樹：
step1.一次一個符號地讀入表達式
step2.如果符號是操作數(shù)，那么就建立一個單節(jié)點樹并將一個指向它的指針推入棧中特占；如果符號是操作符糙置，那么我們就從棧中彈出指向兩棵樹T1和T2的那兩個指針（T1先彈出）并形成一棵新的樹。

a b + c d e + * *后綴表達式轉(zhuǎn)換成表達式樹的過程：

1 查找樹ADT

支持SEARCH(Find)是目、MINIMUM(FindMin)谤饭、MAXIMUM(Find Max)、PREDECESSOR懊纳、SUCCESSOR揉抵、INSERT和DELETE等集合操作。
查找樹既可以作為一個字典（字典的實現(xiàn)嗤疯，作為一個專題冤今？）又可以作為一個優(yōu)先隊列。

2 查找樹的實現(xiàn)

2.1 二叉查找樹

1）結(jié)構(gòu)
一棵二叉查找樹是以一棵二叉樹來組織的茂缚。

2）操作
a.查找

b.最值

c.前驅(qū)和后繼

證明：考慮一棵二叉搜索樹T戏罢，其關(guān)鍵字互不相同。如果T中的一個結(jié)點x的右子樹為空脚囊，且x有一個后繼y龟糕，那么y一定是x的最底層祖先，并且其左孩子也是x的祖先悔耘。（每個結(jié)點都是它自己的祖先讲岁。）

如上圖：
4的后繼是6
9的后繼是13
13的后繼是15

step1.從結(jié)點x向上搜索，從右邊一路向上衬以，這些結(jié)點的key都要小于x
step2.直到找到一個結(jié)點缓艳，從左邊向上，這是第一個大于所有左邊結(jié)點的結(jié)點y
這里的關(guān)鍵是：結(jié)點是x是結(jié)點y的左子樹最大者泄鹏，因此x的后繼是y

d.插入

e.刪除
刪除分為如下三種情況：

另外一種劃分：
e-1.如果z沒有左孩子郎任，那么用其右孩子來代替z，這個右孩子可以是NIL备籽，也可以不是。

e-2.如果z僅有一個孩子且是其左孩子，用左孩子來代替z

e-3.否則车猬，z既有一個左孩子又有一個右孩子霉猛。我們要查找z的后繼y，這個后繼位于z的右子樹中并且沒有左孩子≈槿颍現(xiàn)在需要將y移出原來的位置進行拼接惜浅，并替換樹中的z
如果y是z的右孩子，那么用y替換z伏嗜，并僅留下y的右孩子坛悉。

否則，y位于z的右子樹中但并不是z的右孩子承绸。此時先用y的右孩子替換y裸影，然后再用y替換z。

這里涉及到一個證明：
如果一棵二叉搜索樹中的一個結(jié)點有兩個孩子军熏，那么它的后繼沒有左孩子轩猩，它的前驅(qū)沒有右孩子。
因為：結(jié)點有兩個孩子荡澎，那么它的后繼一定在右子樹中均践，沿著左路徑一直向下；如果這個后繼還有左孩子摩幔，那么后繼是這個孩子彤委。
前驅(qū)同理。

TRANSPLANT用一棵以v為根的子樹來替換一棵以u為根的子樹：

3）二叉搜索樹的平均情形性能——隨機構(gòu)建二叉搜索樹
當(dāng)一棵二叉搜索樹同時由插入和刪除操作生成時或衡，我們對這棵樹的平均高度了解甚少焦影。
當(dāng)樹由插入操作單獨生成時，分析就會容易得多薇宠。

定義n個關(guān)鍵字的一棵隨機構(gòu)建二叉搜索樹為按隨機次序插入這些關(guān)鍵字到一棵初始的空樹中而生成的偷办，這里的n!個排列中的每個都是等可能地出現(xiàn)。

證明：說明含有n個關(guān)鍵字的隨機選擇二叉搜索樹的概念澄港，這里每一棵n個結(jié)點的二叉搜索樹是等可能地被選擇椒涯，不同于本節(jié)中給出的隨機構(gòu)建二叉搜索樹的概念。

從上圖中可以看出回梧，一棵二叉搜索樹可能對應(yīng)多個排列废岂。因此，不同于本節(jié)中給出的隨機構(gòu)建二叉搜索樹的概念狱意。

證明：一棵有n個不同關(guān)鍵字的隨機構(gòu)建二叉搜索樹的期望高度為O(lgn)湖苞。

該證明中涉及到的證明：
1）組合數(shù)的證明

2）證明：f(x) = 2的x次方是凸函數(shù)。

3）關(guān)于e的x次冪 >= 1+x

4）關(guān)于Jensen不等式（是凸函數(shù)定義的推廣）

2.2 AVL樹

1）結(jié)構(gòu)
AVL（Adelson-Velskii和Landis）樹是帶有平衡條件的二叉查找樹。
這個平衡條件必須容易保持，而且它必須保證樹的深度是O(logn)知押。
a.最簡單的方法是：要求左右子樹具有相同的高度诽偷。（太松）
b.要求每個結(jié)點都必須要有相同高度的左子樹和右子樹求豫。（太嚴(yán)）
一棵AVL樹是其每個結(jié)點的左子樹和右子樹的高度最多差1的二叉查找樹辖所。（空樹的高度定義為-1）

在高度為h的AVL樹中透且，最少節(jié)點數(shù)S(h)由S(h) = S(h-1) + S(h-2) + 1給出（g(h) = S(h) + 1）性誉。
對于h = 0, S(h) = 1捌臊；h = 1, S(h) = 2杨蛋。函數(shù)S(h)與斐波那契數(shù)密切相關(guān)。
由此可以推出：n >= S(h)理澎，可以得到h的高度最高不超過1.44log(n + 2) - 1.328逞力，也即O(lgn)。

2）操作

Height

重點研究插入：
將關(guān)鍵字X的一個新結(jié)點插入到一棵AVL樹T中糠爬，遞歸地將X插入到T的相應(yīng)的子樹（Tlr）寇荧。
如果Tlr的高度不變，那么插入完成秩铆。
否則砚亭，如果在T中出現(xiàn)高度不平衡，那么我們根據(jù)X以及T和Tlr中的關(guān)鍵做適當(dāng)?shù)膯涡D(zhuǎn)或雙旋轉(zhuǎn)殴玛，更新這些高度（并做好與樹的其余部分的連接）捅膘，從而完成插入。

插入后滚粟，只有那些從插入點到根節(jié)點的路徑上的結(jié)點的平衡可能被改變寻仗，因為只有這些結(jié)點的子樹發(fā)生變換。
對第一個破壞了AVL條件的結(jié)點（即最深的結(jié)點）進行平衡凡壤，這一重新平衡保證整個樹滿足AVL特性署尤。
該結(jié)點為α，由于任意結(jié)點最多有兩個兒子亚侠，因此高度不平衡時曹体，α點兩棵子樹的高度差2.這種不平衡可能出現(xiàn)下面四種情況：

• 情況1：對α的左兒子的左子樹進行一次插入
• 情況2：對α的左兒子的右子樹進行一次插入
• 情況3：對α的右兒子的左子樹進行一次插入
• 情況4：對α的右兒子的右子樹進行一次插入

情況1和情況4關(guān)于α點鏡像對稱，2和3關(guān)于α點鏡像堆成硝烂。

2-1）情況1和情況4——單旋轉(zhuǎn)
針對情況1：
插入之前k2滿足AVL特性箕别，插入后結(jié)點k2不滿足AVL平衡特性，因為它的左子樹（X已經(jīng)長出一層）比右子樹深2層（看虛線）滞谢。因此串稀，有
a.Y不可能與新X在同一水平上，因為那樣k2在插入之前就不平衡了
b.Y也不可能和Z在同一層狮杨，因為那樣k1就是平衡被破壞的第一個結(jié)點

為了恢復(fù)平衡母截，把X上移一層，并把Z下移一層橄教。調(diào)整后清寇，整個樹的新高度與插入前原樹的高度相同喘漏。

情況4類似：

2-2）情況2和情況3——雙旋轉(zhuǎn)
針對情況2：
恰好B或C中有一棵比D深兩層，但是不確定是哪一棵颗管，因此畫成比D低1.5層陷遮。

2.3 伸展樹

2.3.1 結(jié)構(gòu)

保證從空樹開始任意連續(xù)M次對數(shù)的操作最多花費O(MlogN)垦江。雖然這種保證不排除任意一次操作花費O(N)時間。一棵伸展樹每次操作的攤還代價是O(logN)搅方。

伸展樹是基于這樣的事實：對于二叉查找樹比吭，每次操作最壞情形時間O(N)并不壞，只要它相對不常發(fā)生即可姨涡。
因此：當(dāng)一個結(jié)點被訪問后衩藤，它就要經(jīng)過一系列AVL樹的旋轉(zhuǎn)被放到根上。（因為許多應(yīng)用中涛漂，當(dāng)一個結(jié)點被訪問赏表，它就很可能不久再次被訪問到，如果碰到O(N)的結(jié)點匈仗，沒有被移動瓢剿，那么很難得到O(lgN)攤還時間）

伸展樹不要求保留高度或平衡信息。

2.3.2 操作

1）一個簡單的想法——執(zhí)行單旋轉(zhuǎn)
如下是對樹中k1進行一次訪問后發(fā)生的情況：

2）展開
X是訪問路徑上的一個非根結(jié)點。
a. X的父節(jié)點是樹根火架，只要旋轉(zhuǎn)X和樹根
b. X有父親P和祖父G
b-1. zig-zag情形

b-2. zig-zig情形

考慮之前的例子：

考慮下面這個例子：

（是否可以證明鉴象？）展開操作的效果：不僅將訪問的結(jié)點移到根處，而且還把訪問路徑上的大部分結(jié)點的深度大致減少一半的效果（某些淺的結(jié)點最多向下推后兩個層次）

3）刪除
step1.訪問該節(jié)點（移到根處）
step2.刪除根節(jié)點（得到Tl和Tr）
step3.將Tl中的最大元素作為根何鸡，并且將Tr接到根的右邊纺弊，作為右兒子

2.3-1 自頂向下伸展樹

基本的伸展樹展開操作：
直接實現(xiàn)需要從根沿樹往下的一次遍歷，以及而后的從底向上的一次遍歷骡男。
通過保存一些父指針來完成淆游，或者通過將訪問路徑存儲到一個棧中來完成。開銷較大洞翩。

自頂向下伸展樹的改進：
自頂向下展開在初始訪問路徑上施行一些旋轉(zhuǎn)稽犁，結(jié)果得到在實踐中更快的過程，只用O(1)的額外空間骚亿，但卻保持了O(logN)的攤還時間界已亥。

聲明和初始化

step1.自頂向下展開旋轉(zhuǎn)

單旋轉(zhuǎn)

之字形旋轉(zhuǎn)簡化成單旋轉(zhuǎn)

一字型旋轉(zhuǎn)

自頂向下的展開過程

這個伸展過程不能處理在伸展樹中不存在的元素，正確的做法如下：

自頂向下的展開過程為什么是正確的来屠？

• 1.對于左邊：總是將X放到左邊虑椎，然后將X = X->Right震鹉；因此，左邊的總是小于中間的X
• 2.對于右邊捆姜，同理传趾，總是將X放到右邊，然后將X = X->Left泥技，因此浆兰，右邊總是大于中間的X
• 3.最后合并的時候：
  LeftTreeMax->Right（左邊最大） = X->Left（中間最小）
  RightTreeMin->Left（右邊最猩罕） = X->Right（中間最大）
  剩下的X大于左邊最大簸呈，小于右邊最小，正好居中
• 而對于查找店茶，跟普通查找的本質(zhì)是一樣的蜕便，小于根則往根的左邊走，大于根則往根的右邊走

證明：自頂向下的展開過程的攤還界為O(lgN)

step2.最后一步：處理L贩幻、R和中間樹以形成一棵樹

示例如下

插入

該伸展樹插入19：

• step1.先按19自頂向下展開

• step2.然后將19插入

  
  

刪除

該伸展樹刪除18：

• step1.先按18自頂向下展開
• step2.刪除18轿腺，然后將18的左子樹按18自頂向下展開（因為左子樹都小于18，所以最后的根上面沒有右子樹）

• step3.將根的右子樹賦值為18的右子樹

  
  

2.4 B樹

B樹是為磁盤或其他直接存取的輔助存儲設(shè)備而設(shè)計的一種平衡搜索樹丛楚。B樹類似于紅黑樹族壳。但它們在降低磁盤I/O操作數(shù)方面要好些。許多數(shù)據(jù)庫系統(tǒng)使用B樹或者B樹的變種來存儲信息鸯檬。
用以下偽代碼對磁盤操作進行建模：

在大多數(shù)系統(tǒng)中决侈，一個B樹算法的運行時間主要由它所執(zhí)行的DISK-READ和DISK-WRITE操作的次數(shù)決定，所以希望這些操作能夠讀喧务、寫盡可能多的信息赖歌。一個B樹結(jié)點通常和一個完整磁盤頁一樣大，并且磁盤頁的大小限制了一個B樹可以含有的孩子的個數(shù)功茴。

2.4.1 結(jié)構(gòu)

任何和關(guān)鍵字相聯(lián)系的“衛(wèi)星數(shù)據(jù)”將于關(guān)鍵字一樣存放在同一個結(jié)點中（指針）庐冯。
B樹的結(jié)點可以有很多孩子。B樹以一種自然的方式推廣了二叉搜索樹坎穿。
如果B樹的一個內(nèi)部結(jié)點x包含x.n個關(guān)鍵字展父，那么結(jié)點x就有x.n+1個子域。結(jié)點x中的關(guān)鍵字就是分割點玲昧，它把結(jié)點x中所處理的關(guān)鍵字的屬性分割成x.n+1一個子域栖茉，每一個子域由x的一個孩子處理。

一棵B樹的定義如下：

B樹的高度：

2.4.2 操作

采用兩個約定：

• B樹的根節(jié)點始終在主存中孵延，無需對根做DISK-READ操作吕漂；然而，當(dāng)根節(jié)點被改動后尘应，需要對根節(jié)點做一次DISK-WRITE操作
• 任何被當(dāng)做參數(shù)的結(jié)點在傳遞之前惶凝，都要對它們先做一次DISK-READ操作吼虎。
  1）搜索——B-TREE-SEARCH
  對每個內(nèi)部結(jié)點x，做的是一個（x.n+1）路的分支選擇苍鲜。
  
  
  性能分析（兩個指標(biāo)）：訪問磁盤頁面數(shù)思灰、CPU時間
  

2）創(chuàng)建——B-TREE-CREATE

3）插入——B-TREE-INSERT
在B樹中，不能簡答地創(chuàng)建一個新的葉節(jié)點混滔，然后將其插入洒疚，因為這樣得到的樹將不再是合法的B樹。（為什么遍坟？因為一個非根結(jié)點至少還有t-1個關(guān)鍵字拳亿。）

正確的做法：
將新的關(guān)鍵字插入一個已經(jīng)存在的葉節(jié)點上。將關(guān)鍵字插入滿的葉節(jié)點時愿伴，會引起分裂。2t-1個關(guān)鍵字的滿結(jié)點y电湘，按照中間關(guān)鍵字分裂為兩個各含t-1個關(guān)鍵字的結(jié)點隔节。中間關(guān)鍵字被提升到y(tǒng)的父節(jié)點。如果y的父節(jié)點是滿的寂呛，分裂會沿著樹向上傳播怎诫。

處理根節(jié)點r滿的情況：原來的根節(jié)點被分裂，一個新的結(jié)點s（有兩個孩子）成為根贷痪，對根進行分裂是增加B樹高度的唯一途徑幻妓。（B樹高度的增加發(fā)生在頂部而不是底部）

1-9行創(chuàng)建結(jié)點z妹沙，并將y的t-1娥關(guān)鍵字以及相應(yīng)的t個孩子給它。
10行調(diào)整y的關(guān)鍵字個數(shù)
11-17行將z插入為x的一個孩子熟吏，并提升y的中間關(guān)鍵字到x來分割y和z

將關(guān)鍵字k插入以非滿的根節(jié)點為根的樹中：
B-TREE-INSERT-NOFULL完成將關(guān)鍵字k插入到以非滿的根節(jié)點為根的樹中距糖。在需要時沿樹向下遞歸，在必要時通過調(diào)研B-TREE-SPLIT-CHILD來保證任何時刻它所遞歸處理的結(jié)點都是非滿的牵寺。

3-8處理x是葉節(jié)點的情況
9-17處理非葉節(jié)點
? ? 9-11決定向x的哪個子節(jié)點遞歸下降
? ? 13-16 處理一個滿結(jié)點
? ? ? ? 14 分裂為兩個非滿的子節(jié)點
? ? ? ? 15-16確定向兩個孩子中哪一個下降是正確的
? ? 17 遞歸至一個非滿結(jié)點

時間分析：

4）刪除——B-TREE-DELETE
B-TREE-DELETE從以x為根的子樹中刪除關(guān)鍵字k悍引。必須保證何時，結(jié)點x遞歸調(diào)用自身是帽氓，x中關(guān)鍵字至少為最小度數(shù)t （這個條件比B樹中的最少關(guān)鍵字個數(shù)多1個以上）趣斤。這個條件允許在一趟下降過程中，就可以將一個關(guān)鍵字從書中刪除杏节，無需“向上回溯”（有一個例外）唬渗。

如果根x成為一個不含任何關(guān)鍵字的內(nèi)部結(jié)點典阵，那么x就要被刪除，x的唯一孩子x.c1就成為樹的新根镊逝，從而樹的高度降低1壮啊，同時也維持了樹根必須包含至少一個關(guān)鍵字的性質(zhì)（除非樹是空的）。

 B-TREE-DELETE(T,k)
 1  r ← root[T]
 2  if n[r] = 1
 3    then DISK_READ(c1[r])
 4       DISK_READ(c2[r])
 5       y ←c1[r]
 6       z ←c2[r]
 7       if n[y] = n[z] = t-1                    Cases 2c or 3b
 8         then  B-TREE-MERGE-CHILD(r, 1, y, z) 
 9            root[T] ← y
 10           FREE-NODE(r)
 11           B-TREE-DELETE-NONONE(y, k)
 12      else B-TREE-DELETE-NONONE (r, k)
 13 else B-TREE-DELETE-NONONE (r, k)

考慮到根結(jié)點的特殊性撑蒜，對根結(jié)點為1歹啼，并且兩個子結(jié)點都是t-1的情況進行了特殊的處理：
先對兩個子結(jié)點進行合并，然后把原來的根刪除座菠，把樹根指向合并后的子結(jié)點y狸眼。
這樣B樹的高度就減少了1。這也是B樹高度唯一會減少的情況浴滴。 
除了這種情況以外拓萌，就直接調(diào)用子過程B-TREE-DELETE-NONONE (x, k)。

B樹的結(jié)點的合并基于如下情況調(diào)用：
內(nèi)結(jié)點x的第i個子結(jié)點y和第i+1個子結(jié)點z的關(guān)鍵字?jǐn)?shù)都是t-1升略，
此時需要把內(nèi)結(jié)點x的第i個關(guān)鍵字下移與y和z的合并微王，形成一個結(jié)點y。

2.4-1 B+樹

把所有的衛(wèi)星數(shù)據(jù)都存儲在葉節(jié)點中品嚣，內(nèi)部結(jié)點只存放關(guān)鍵字和孩子指針炕倘，因此最大化了內(nèi)部結(jié)點的分支因子。

2.4-2 B*樹

2.5 紅黑樹

紅黑樹是許多“平衡”搜索樹中的一種翰撑，可以保證在最壞情況下基本動態(tài)集合操作的時間復(fù)雜度為O(lgn).

2.5.1 結(jié)構(gòu)

紅黑樹是一顆二叉搜索樹罩旋，它在每個結(jié)點上增加了一個存儲位來表示結(jié)點的顏色，可以是red或black眶诈。
通過對任何一條從根到葉子的簡單路徑上各個結(jié)點的顏色進行約束涨醋，紅黑樹確保沒有一條路徑會比其他路徑長處2倍，因而近似于平衡的册养。

結(jié)點屬性：color key left right p
可以把NIL視為二叉搜索樹的葉節(jié)點的指針东帅，而把帶關(guān)鍵字的結(jié)點視為樹的內(nèi)部結(jié)點。

一棵紅黑樹是滿足下面紅黑性質(zhì)的二叉搜索樹：

• 1.每個結(jié)點或是紅色的球拦，或是黑色的
• 2.根節(jié)點是黑色的
• 3.每個葉節(jié)點NIL時黑色的（這條性質(zhì)可去掉）
• 4.如果一個結(jié)點是紅色的靠闭，則它的兩個子節(jié)點都是黑色的
• 5.對每個結(jié)點，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上坎炼，均包含相同數(shù)目的黑色結(jié)點

黑高：從某個節(jié)點x出發(fā)（不含該節(jié)點）到達一個葉節(jié)點的任意一條簡單路徑上的黑色結(jié)點個數(shù)稱為該節(jié)點的黑高愧膀，記為bh(x)。

2.5.2 操作

1）常規(guī)操作
SEARCH谣光、MINIMUM檩淋、MAXIMUM、SUCCESSOR、PREDECESSOR可以在紅黑樹上在O(lgn)時間內(nèi)執(zhí)行蟀悦。（這些操作跟二叉搜索樹一樣）

2）插入

step1.插入新結(jié)點z后媚朦，哪些紅黑性質(zhì)不能保持？

• 1.每個結(jié)點或是紅色的日戈，或是黑色的（成立）
• 2.根節(jié)點是黑色的（z為根節(jié)點询张，則不成立）
• 3.每個葉節(jié)點NIL時黑色的（成立）
• 4.如果一個結(jié)點是紅色的，則它的兩個子節(jié)點都是黑色的（如果z的父節(jié)點為紅結(jié)點浙炼，則不成立）
• 5.對每個結(jié)點份氧，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上，均包含相同數(shù)目的黑色結(jié)點（成立）

step2.RB-INSERT-FIXUP的1~15行中while循環(huán)的目標(biāo)
三個循環(huán)不變式：

• a.結(jié)點z是紅結(jié)點
• b.如果z.p是根節(jié)點弯屈，則z.p是黑結(jié)點
• c.如果有任何紅黑性質(zhì)被破壞蜗帜，則至多只有一條被破壞，或是2资厉，或是4.如果是性質(zhì)2被破壞厅缺，則z是根節(jié)點且是紅結(jié)點；如果是性質(zhì)4被破壞酌住，則z和z.p都是紅結(jié)點

證明三個循環(huán)不變式是成立的店归，step2證明初始化和終止部分，step3證明保持部分酪我。

初始化：
在循環(huán)的第一次迭代之前，從一顆正常的紅黑樹開始且叁，并新增一個紅結(jié)點z都哭。在RB-INSERT-FIXUP調(diào)用前：
a.結(jié)點z是新增的紅結(jié)點
b.若z.p是根，則z.p是黑色的
c.五條性質(zhì)的成立情況

• 1.每個結(jié)點或是紅色的逞带，或是黑色的（成立）
• 2.根節(jié)點是黑色的（如果違反了2欺矫，則根節(jié)點是z，且是唯一的結(jié)點展氓，此時沒有違反性質(zhì)4）
• 3.每個葉節(jié)點NIL時黑色的（成立）
• 4.如果一個結(jié)點是紅色的穆趴，則它的兩個子節(jié)點都是黑色的（如果違反了性質(zhì)4，因為加入之前沒有違反其他性質(zhì)（根節(jié)點是黑色的遇汞，不會違反性質(zhì)2）未妹，加入之后只可能是其父節(jié)點z.p為紅色）
• 5.對每個結(jié)點，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上空入，均包含相同數(shù)目的黑色結(jié)點（成立）

終止：
循環(huán)終止時因為z.p是黑色的络它。（如果z是根節(jié)點，那么z.p是T.nil黑色的歪赢。）因此沒有違反性質(zhì)4化戳。因此唯一可能不成立的是性質(zhì)2.
第16行恢復(fù)了這個性質(zhì)。

因此可知埋凯，RB-INSERT-FIXUP的作用如下：
1）while循環(huán)的作用主要是修復(fù)性質(zhì)4
2）最后一行16行主要是修復(fù)性質(zhì)2

step3.分析while循環(huán)體中的三種情況
保持：

• a.結(jié)點z是紅結(jié)點
• b.如果z.p是根節(jié)點点楼，則z.p是黑結(jié)點
• c.如果有任何紅黑性質(zhì)被破壞扫尖，則至多只有一條被破壞，或是2掠廓，或是4.如果是性質(zhì)2被破壞换怖，則z是根節(jié)點且是紅結(jié)點；如果是性質(zhì)4被破壞却盘，則z和z.p都是紅結(jié)點

需要分析while循環(huán)中的6種情況狰域，其中三種與另外三種是對稱的。這里給出z.p是z.p.p左孩子的情況黄橘。
根據(jù)b兆览，可知結(jié)點z.p.p存在。因為只有z.p為紅色才進入一次循環(huán)塞关，所以z.p不可能是根節(jié)點抬探，因此z.p.p存在。

情況1：z的叔結(jié)點y是紅色
此時z.p和y都是紅色帆赢，z.p.p是黑色小压，將z.p和與都著為黑色，z.p.p著為紅色椰于，z上移兩層怠益。

z'=z.p.p在下一次循環(huán)迭代開始會保持這個循環(huán)不表示：

• a.結(jié)點z是紅結(jié)點（z'=z.p.p被著為了紅色）
• b.如果z.p是根節(jié)點，則z.p是黑結(jié)點（z'.p是z.p.p.p結(jié)點的顏色不會改變瘾婿，若是根節(jié)點蜻牢，則依然為黑色）
• c.如果有任何紅黑性質(zhì)被破壞，則至多只有一條被破壞偏陪，或是2抢呆，或是4.如果是性質(zhì)2被破壞，則z是根節(jié)點且是紅結(jié)點笛谦；如果是性質(zhì)4被破壞抱虐，則z和z.p都是紅結(jié)點（保持1/3/5性質(zhì)成立；如果z'是根節(jié)點饥脑，且已經(jīng)修正了性質(zhì)4恳邀，所以只有性質(zhì)2被壞；如果z'不是根節(jié)點好啰，則性質(zhì)2依然保持轩娶，此時z'為紅色，z'.p顏色不變框往，可能為紅色鳄抒，因此只可能破壞性質(zhì)4）

情況2：z的叔結(jié)點y是黑色的且z是一個右孩子
通過左旋將情況2變成情況3
因為z和z.p都是紅色，所以該旋轉(zhuǎn)對結(jié)點的黑高和性質(zhì)5都無影響。

• 1.每個結(jié)點或是紅色的许溅，或是黑色的
• 2.根節(jié)點是黑色的
• 3.每個葉節(jié)點NIL時黑色的
• 4.如果一個結(jié)點是紅色的瓤鼻，則它的兩個子節(jié)點都是黑色的（如果違反了性質(zhì)4，因為加入之前沒有違反其他性質(zhì)
• 5.對每個結(jié)點贤重，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上茬祷，均包含相同數(shù)目的黑色結(jié)點

情況3：z的叔結(jié)點y是黑色的且z是一個左孩子

情況改變顏色后，需要通過右旋來保持性質(zhì)5.
因為情況2和情況3的z.p已經(jīng)為黑色并蝗，因此不需要再執(zhí)行while循環(huán)祭犯。

情況2和情況3保持循環(huán)不變式：

• a.結(jié)點z是紅結(jié)點（進入3后，z的顏色不變）
• b.如果z.p是根節(jié)點滚停，則z.p是黑結(jié)點（3將z.p著成黑色沃粗，如果是根節(jié)點，則是黑色）
• c.如果有任何紅黑性質(zhì)被破壞键畴，則至多只有一條被破壞最盅，或是2，或是4.如果是性質(zhì)2被破壞起惕，則z是根節(jié)點且是紅結(jié)點涡贱；如果是性質(zhì)4被破壞，則z和z.p都是紅結(jié)點（性質(zhì)135在這兩種情況得以保持惹想，而且這兩種情況對性質(zhì)4起了修復(fù)作用问词，不會違反性質(zhì)2）

時間分析：

插入和刪除可能違反紅黑樹性質(zhì)，必須通過改變樹中某些結(jié)點的顏色和指針結(jié)構(gòu)來維持嘀粱。其中結(jié)構(gòu)的修改通過旋轉(zhuǎn)來完成戏售。

在LEFT-ROTATE的偽代碼中，假設(shè)x.right ≠ T.nil且根節(jié)點的父節(jié)點為T.nil草穆。

證明1.為什么選擇將結(jié)點z著為紅色，而不是黑色搓译？
因為一定會違反性質(zhì)5悲柱。因為插入之前，根到各個葉子點上的黑色結(jié)點都相等些己。插入黑色結(jié)點后豌鸡，是一定要調(diào)整的。
而插入紅色結(jié)點段标，有可能是滿足要求的（插入到黑色結(jié)點下面）涯冠。這樣就只有違反性質(zhì)4或者性質(zhì)2的才需要調(diào)整，需要調(diào)整的情況比較少逼庞。

3）刪除
3-1）普通二叉搜索樹的刪除
刪除分為如下三種情況：

e-2.如果z僅有一個孩子且是其左孩子砸逊，用左孩子來代替z

e-3.否則，z既有一個左孩子又有一個右孩子掌逛。我們要查找z的后繼y师逸，這個后繼位于z的右子樹中并且沒有左孩子。現(xiàn)在需要將y移出原來的位置進行拼接豆混，并替換樹中的z
如果y是z的右孩子篓像，那么用y替換z，并僅留下y的右孩子皿伺。

否則员辩，y位于z的右子樹中但并不是z的右孩子沐祷。此時先用y的右孩子替換y袖外，然后再用y替換z。

這里涉及到一個證明：
如果一棵二叉搜索樹中的一個結(jié)點有兩個孩子屏富，那么它的后繼沒有左孩子脂男，它的前驅(qū)沒有右孩子养叛。
因為：結(jié)點有兩個孩子，那么它的后繼一定在右子樹中宰翅，沿著左路徑一直向下弃甥；如果這個后繼還有左孩子，那么后繼是這個孩子汁讼。
前驅(qū)同理淆攻。

TRANSPLANT用一棵以v為根的子樹來替換一棵以u為根的子樹：

3-2）紅黑樹的刪除

紅黑樹的刪除與二叉搜索樹的刪除結(jié)構(gòu)是一致的，只不過多了對y和x的記錄嘿架，y和x有可能導(dǎo)致紅黑樹性質(zhì)的破壞瓶珊。

• a. 結(jié)點y：當(dāng)z的子節(jié)點少于2個時，y指向z耸彪，并被刪除伞芹；當(dāng)z有兩個子節(jié)點，將y指向z的后繼蝉娜，y被移動到z的位置
• b. y-original-color存儲了發(fā)生改變前y的顏色唱较。如果是黑色，那么刪除或移動y會引起紅黑性質(zhì)的破壞
• c. 結(jié)點x會移至y的原始位置
• d. 當(dāng)z是y的原始父節(jié)點（z有兩個孩子召川，且y是z的右孩子時）南缓，使x.p指向y；其他情況荧呐，x.p總是設(shè)置指向y父節(jié)點的原始位置汉形。
• e. 如果結(jié)點y是黑色的纸镊，就有可能已經(jīng)引入了一個或多個紅黑性質(zhì)被破壞。如果y是紅色获雕，當(dāng)y被刪除或移動時薄腻，紅黑性質(zhì)仍然保持，原因：
  1）樹中的黑高沒有變化
  2）不存在兩個相鄰的紅結(jié)點：y的新位置（無論是z還是z的后繼）都不可能有兩個新紅結(jié)點（因為y占據(jù)了z的位置届案，并且是z的顏色庵楷，無論是z還是z的后繼都成立）；另外楣颠，如果y不是z的孩子尽纽，則y的原右孩子x代替y。如果y是紅色童漩，則x是黑色弄贿，所以x處也不可能是兩個紅結(jié)點相鄰。
  3）如果y是紅色矫膨，就不可能是根節(jié)點差凹，所以根節(jié)點仍然是黑色的

如果y是黑色的，則會產(chǎn)生三個問題：

• 若y是原來的根節(jié)點侧馅，而y的一個紅色的孩子成為了新的根節(jié)點危尿，違反性質(zhì)2（此時RB-DELETE-FIXUP最后一行將x.color置位BLACK，且黑高是恢復(fù)的馁痴；其余情況都不會違反性質(zhì)2）
• 若x和x.p是紅色谊娇，則違反了性質(zhì)4（此時RB-DELETE-FIXUP最后一行將x.color置位BLACK，恢復(fù)了性質(zhì)4罗晕，且黑高是恢復(fù)的）
• 在樹中移動y將導(dǎo)致先前包含y的任何簡單路徑上黑結(jié)點個數(shù)少1.因此y的任何祖先都不滿足性質(zhì)5.（將占有y原來位置的結(jié)點x視為還有一重額外的黑色：則x可能既不是紅色济欢，又不是黑色，違反了性質(zhì)1）

因此RB-DELETE-FIXUP的1-22行主要處理性質(zhì)1的情況小渊，23行處理性質(zhì)2和4的情況法褥。
while循環(huán)的目的是將額外的黑色沿樹上移，直到：

• x指向紅黑結(jié)點酬屉，此時23行將x著色為（單個）黑色
• x指向根節(jié)點挖胃，此時可以簡單地“移除”額外的黑色
• 執(zhí)行適當(dāng)?shù)男D(zhuǎn)和重新著色，退出循環(huán)

在while循環(huán)中梆惯，x總是指向一個具有雙重黑色的非根節(jié)點。因此w不可能是T.nil吗垮，否則垛吗，從x.p至葉子w（T.nil為單黑色）的簡單路徑上的黑結(jié)點個數(shù)就會小于從x.p到x的簡單路徑上的黑色結(jié)點樹（雙重黑色）。
關(guān)鍵思想是在每種情況中烁登，從子樹的根（包括根）到每棵子樹αβγδεζ之間的黑結(jié)點個數(shù)（包括x的額外黑色）并不被變換改變怯屉。

• 情況1：x的兄弟節(jié)點是紅色
  此時蔚舀，各個子樹的黑結(jié)點并未變換；且通過修改顏色和左旋轉(zhuǎn)換為情況2锨络、3赌躺、4
• 情況2：x的兄弟節(jié)點w是黑色的，而且w的兩個子節(jié)點都是黑色的
  將x和w上去掉一重黑色羡儿，x只有一重黑色而w為紅色礼患。并在x.p上新增一重額外的黑色，將x.p作為新的x來重復(fù)while循環(huán)掠归。
  如果是情況1進入到情況2缅叠，因為x.p是紅色，則新x是紅黑色虏冻，循環(huán)直接終止肤粱，將新x著為（單一）黑色。
• 情況3：x的兄弟節(jié)點w是黑色厨相，w的左孩子是紅色领曼，w的右孩子時黑色
  通過交換w和w.left的顏色，對w進行右旋蛮穿，將情況3轉(zhuǎn)換成了情況4
• 情況4：x的兄弟w是黑色庶骄，且w的右孩子是紅色的
  此種情況可以去掉x的額外的黑色（無論x.p的顏色是黑色還是紅色，都成立）

時間分析：

2.6 跳躍表

參考http://www.reibang.com/p/4ea55495e365

2.7 trie樹