紅黑樹
- 紅黑樹也是一種自平衡的二叉搜索樹贾虽；
- 紅黑樹以前也叫做平衡二叉B樹；
如下圖所示：
Snip20210511_15.png
紅黑樹的5條性質(zhì)：
- 節(jié)點(diǎn)是RED或者BLACK叙凡；
- 根節(jié)點(diǎn)是BLACK正驻；
- 葉子節(jié)點(diǎn)(空節(jié)點(diǎn))都是BLACK；
- RED節(jié)點(diǎn)的子節(jié)點(diǎn)都是BLACK牵辣；
4.1 RED節(jié)點(diǎn)的parent都是BLACK摔癣；
4.2 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑上不能有2個(gè)連續(xù)的RED節(jié)點(diǎn)； - 從任意節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的BLACK節(jié)點(diǎn)纬向；
B樹
- B樹是一種平衡的多路搜索樹择浊，多用于文件系統(tǒng)，數(shù)據(jù)庫(kù)的實(shí)現(xiàn)逾条；
- 一個(gè)節(jié)點(diǎn)可以存儲(chǔ)超過2個(gè)元素近她，可以擁有超過2個(gè)字節(jié)點(diǎn)；
- 擁有二叉搜索樹的性質(zhì)膳帕；
- 平衡粘捎，每個(gè)節(jié)點(diǎn)的所有子樹高度一致；
- 比較矮危彩；
m階B樹的性質(zhì)(m>=2)
- m階B樹是指一個(gè)節(jié)點(diǎn)最多擁有m個(gè)子節(jié)點(diǎn)攒磨；
Snip20210511_16.png
Snip20210511_17.png
- 假設(shè)一個(gè)節(jié)點(diǎn)存儲(chǔ)的元素個(gè)數(shù)為x
- 根節(jié)點(diǎn)： 1 <= x <= m - 1
- 非根節(jié)點(diǎn)： ceil(m/2) - 1 <= x <= m -1
- 如果有子節(jié)點(diǎn)，子節(jié)點(diǎn)的個(gè)數(shù) y = x + 1汤徽；
- 根節(jié)點(diǎn)的子節(jié)點(diǎn)：2 <= y <= m
- 非根節(jié)點(diǎn)的子節(jié)點(diǎn)： ceil(m/2) <= y <= m
以m=3娩缰，即3階B樹為例：
根節(jié)點(diǎn)的元素個(gè)數(shù) 1<= x <= 2，即1或者2谒府，不會(huì)有3個(gè)元素拼坎；
非根節(jié)點(diǎn)的元素個(gè)數(shù) 1<= x <= 2浮毯，即1或者2，不會(huì)有3個(gè)元素泰鸡；
根節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù) 2 <= y <= 3
非根節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù) 2 <= y <= 3
B樹與二叉搜索樹债蓝，在邏輯上等價(jià)的；
多代節(jié)點(diǎn)合并盛龄，可以獲得一個(gè)超級(jí)節(jié)點(diǎn)饰迹；
2代合并的超級(jí)節(jié)點(diǎn)，最多擁有4個(gè)子節(jié)點(diǎn)余舶，至少是4階B樹啊鸭；
3代合并的超級(jí)節(jié)點(diǎn)，最多擁有8個(gè)子節(jié)點(diǎn)匿值，至少是8階B樹赠制；
n代合并的超級(jí)節(jié)點(diǎn)，最多擁有 2^n 個(gè)子節(jié)點(diǎn)挟憔，至少是 2^n 階B樹钟些；
m階B樹，最多需要log2 m帶合并曲楚；
搜索指定節(jié)點(diǎn)
- 從根節(jié)點(diǎn)開始厘唾；
- 先在節(jié)點(diǎn)內(nèi)部從小到大開始搜索元素；
- 如果命中龙誊，搜索結(jié)束抚垃；
- 如果未命中，再去對(duì)應(yīng)的子節(jié)點(diǎn)中搜索元素鹤树，重復(fù)步驟1；
添加
- 新添加的元素必定是添加到葉子節(jié)點(diǎn)逊朽；
添加導(dǎo)致上溢
- 上溢節(jié)點(diǎn)的元素個(gè)數(shù)必然等于m罕伯；
- 假設(shè)上溢節(jié)點(diǎn)最中間的元素的位置為k追他；
- 將k位置的元素向上與父節(jié)點(diǎn)合并邑狸；
- 將[0，k-1]和[k+1硅堆，m-1]位置的元素分裂成2個(gè)子節(jié)點(diǎn)，這兩個(gè)子節(jié)點(diǎn)的元素個(gè)數(shù)助赞，必然都不會(huì)低于最低限制ceil(m/2)-1群叶；
- 一次分裂完成后舶衬，有可能導(dǎo)致父節(jié)點(diǎn)上溢虽画，依然按照上述的方法解決；
- 最極端的情況，有可能一直分裂到根節(jié)點(diǎn)；
如下所示：4階B樹，添加元素98
Snip20210511_18.png
Snip20210511_19.png
- 添加元素98，由于是4階B樹涡扼，節(jié)點(diǎn)元素個(gè)數(shù)最大為3红淡，則導(dǎo)致上溢在旱；需進(jìn)行一次分裂結(jié)果如下：
Snip20210511_20.png
刪除葉子節(jié)點(diǎn)
- 需要?jiǎng)h除的元素在葉子節(jié)點(diǎn)中，那么直接刪除即可；
如下所示：刪除元素55
Snip20210511_18.png
- 刪除元素55之后：
Snip20210511_21.png
刪除非葉子節(jié)點(diǎn)
- 先找到其前驅(qū)或者后繼元素被饿，覆蓋所需刪除元素的值哎垦；
- 再把前驅(qū)或后繼元素刪除蛙奖；
如下所示：刪除元素60
Snip20210511_22.png
Snip20210511_23.png
- 真正被刪除的元素是前繼元素55昂拂，
- 真正被刪除的元素都是在葉子節(jié)點(diǎn)中。
刪除導(dǎo)致下溢
原理如下所示：
Snip20210517_2.png
看一個(gè)例子：5階B樹刪除元素22
Snip20210511_24.png
- 刪除元素22，由上面的結(jié)論我們知道非根節(jié)點(diǎn)的元素?cái)?shù)量 ceil(5/2)-1<= x <= 4恐似，即至少有兩個(gè)元素，現(xiàn)在刪除22嘶摊，導(dǎo)致當(dāng)前節(jié)點(diǎn)的元素為1蔗喂，即導(dǎo)致下溢；
- 下溢節(jié)點(diǎn)的元素?cái)?shù)量必然等于ceil(m/2) - 2
- 如果下溢節(jié)點(diǎn)臨近的兄弟節(jié)點(diǎn)至少有ceil(m/2)個(gè)元素椅棺，可以向其借一個(gè)元素；
- 將父節(jié)點(diǎn)的元素b插入到下溢節(jié)點(diǎn)的最小位置缎脾；
- 用兄弟節(jié)點(diǎn)的元素a(最大元素)替代父節(jié)點(diǎn)的元素b友多；
- 上述操作的本質(zhì)就是：旋轉(zhuǎn)蜈抓，操作結(jié)果如下所示：
Snip20210517_1.png
- 如果下溢節(jié)點(diǎn)的臨近兄弟節(jié)點(diǎn)，只有ceil(m/2)-1個(gè)元素；
- 將父節(jié)點(diǎn)的元素b挪下來(lái)與左右子節(jié)點(diǎn)進(jìn)行合并睁枕；
- 合并之后的節(jié)點(diǎn)元素個(gè)數(shù)為ceil(m/2)+ceil(m/2)-2，不會(huì)超過m-1泣棋；原理如下圖所示：
Snip20210517_3.png
- 此操作可能會(huì)導(dǎo)致父節(jié)點(diǎn)下溢寄摆，依然按照上述的方法解決，下溢現(xiàn)象可能會(huì)一直向上傳播椎椰；
紅黑樹的等價(jià)變換
- 紅黑樹與4階B樹具有等價(jià)性塔猾；
- BLACK節(jié)點(diǎn)與它的RED子節(jié)點(diǎn)融合在一起睦擂，形成一個(gè)B樹節(jié)點(diǎn)摆马；
- 紅黑樹的BLACK節(jié)點(diǎn)個(gè)數(shù)與4階B樹的節(jié)點(diǎn)總個(gè)數(shù)相等斑唬；
Snip20210519_17.png
紅黑樹的添加
- 新元素的必定是添加到葉子節(jié)點(diǎn)中蓄喇；
- 4階B樹所有節(jié)點(diǎn)的元素個(gè)數(shù)x都滿足 【1，3】肮蛹；
- 建議新添加的節(jié)點(diǎn)默認(rèn)為紅色RED；
- 如果添加的是根節(jié)點(diǎn)，染成黑色BLACK即可蜂绎；
以上面的紅黑樹為例子栅表，進(jìn)行闡述添加的所有情況：
- 當(dāng)添加的節(jié)點(diǎn)的父節(jié)點(diǎn)parent為黑色BLACK，如下圖所示：
Snip20210519_18.png
- 具體有4種情況师枣，見圖中被添加的粉色節(jié)點(diǎn)怪瓶；
- 能同時(shí)滿足紅黑樹的五條性質(zhì)，因此不用做任何額外的處理践美；
- 當(dāng)添加的節(jié)點(diǎn)的父節(jié)點(diǎn)parent為紅色RED洗贰，如下圖所示：
Snip20210519_19.png
- 具體有8種情況，見圖中被添加的粉色節(jié)點(diǎn)陨倡；
- 不滿足紅黑樹的第4條性質(zhì)：RED節(jié)點(diǎn)的子節(jié)點(diǎn)都是BLACK敛滋；
