平衡二叉查找樹
? ? 平衡二叉樹中任意一個節(jié)點的左右子樹的高度相差不能大于1
? ??????完全二叉樹、滿二叉樹都是平衡二叉樹，但非完全二叉樹也有可能是平衡二叉樹
????平衡二叉查找樹滿足上面平衡二叉樹的定義，還滿足二叉查找樹的特點
? ??平衡二叉查找樹為了解決普通二叉查找樹頻繁插入、刪除等動態(tài)更新導(dǎo)致時間復(fù)雜度退化? ??
? ??平衡二叉查找樹中“平衡”:?
? ??????“平衡”可以等價為性能不退化
? ? ? ? 讓整棵樹左右子樹高度比較“平衡”，相應(yīng)的插入、刪除、查找等操作的效率高一些
? ??如設(shè)計一個平衡二叉查找樹，只要樹高度不比logn大很多，盡管不符合定義仍然可以算合格
紅黑樹(Red-Black Tree)
? ? 是一種不嚴(yán)格的平衡二叉查找樹，屬于最常用平衡二叉查找樹
? ? 滿足紅黑樹前提條件
? ? ? ? 所有節(jié)點只有黑色和紅色
? ??????根節(jié)點是黑色
? ??????每個葉子節(jié)點都是黑色的空節(jié)點(NIL) (主要為了簡化代碼實現(xiàn)而設(shè)置)
? ? ? ? ? ? 添加黑色的空葉子節(jié)點，可以在具體實現(xiàn)的時候公用一個空節(jié)點，不會太浪費(fèi)空間
? ??????任何相鄰的節(jié)點都不能同時為紅色
????????每個節(jié)點從該節(jié)點到達(dá)其可達(dá)葉子節(jié)點的所有路徑，都包含相同數(shù)目的黑色節(jié)點
? ??紅黑樹是“近似平衡”
? ??????“平衡”可以等價為性能不退化，而“近似平衡”等價為性能不會退化的太嚴(yán)重
? ??????二叉查找樹操作的性能都跟樹的高度成正比，極其平衡的二叉樹高度大約為logn
? ? 特點
? ??????只要按照這些固定的調(diào)整規(guī)則來操作，就能將一個非平衡的紅黑樹調(diào)整成平衡
? ??????左旋(rotate left):?圍繞某個節(jié)點的左旋
????????右旋(rotate right): 圍繞某個節(jié)點的右旋
? ??????紅黑樹的插入、刪除操作會破壞紅黑樹的平衡，如何調(diào)整平衡
? ? ? ? 名詞介紹
????????????叔叔節(jié)點: 父節(jié)點的兄弟節(jié)點，
????????????祖父節(jié)點:?父節(jié)點的父節(jié)點
? ??????????關(guān)注節(jié)點:?正在處理的節(jié)點
? ? ? ? ? ? 前驅(qū)節(jié)點: 中序遍歷的序列中，當(dāng)前節(jié)點上一個節(jié)點
? ? ? ? ? ? 后繼節(jié)點: 中序遍歷的序列中，當(dāng)前節(jié)點下一個節(jié)點
? ??????插入操作的平衡調(diào)整
????????????紅黑樹定義: 插入的節(jié)點必須是紅色，而且樹中新插入的節(jié)點都放在葉子節(jié)點上
????????????具體情況如下:
????????????????如果插入節(jié)點的父節(jié)點是黑色，那不需要任何調(diào)整，它仍然滿足紅黑樹的定義
????????????????如果插入的節(jié)點是根節(jié)點，那直接改變它的顏色，把它變成黑色就可以了
? ? ? ? ? ? ? ? 其他情況都會違背紅黑樹的定義，需要進(jìn)行兩種基礎(chǔ)的操作: 左右旋轉(zhuǎn)和改變顏色
? ? ? ? ? ? 實現(xiàn)過程
????????????????紅黑樹的平衡調(diào)整過程是一個迭代的過程，
????????????????關(guān)注節(jié)點隨著不停地迭代處理，而不斷發(fā)生變化。最開始的關(guān)注節(jié)點是新插入的節(jié)點
? ??????????????新節(jié)點插入后，如果紅黑樹的平衡被打破，一般會有下面三種情況 & 如何實現(xiàn)再平衡
? ? ? ? ? ? ? ? Case 1.如果關(guān)注節(jié)點是a，它的叔叔節(jié)點d是紅色，依次執(zhí)行
? ??????????????????將關(guān)注節(jié)點a的父節(jié)點b、叔叔節(jié)點d的顏色都設(shè)置成黑色
? ??????????????????將關(guān)注節(jié)點a的祖父節(jié)點c的顏色設(shè)置成紅色
? ??????????????????關(guān)注節(jié)點變成a的祖父節(jié)點c
? ??????????????????跳到CASE 2 或 CASE 3
? ? ? ? ? ? ? ? Case?2.如果關(guān)注節(jié)點是a，叔叔節(jié)點d是黑色，關(guān)注節(jié)點a是其父節(jié)點b的右子節(jié)點
? ??????????????????關(guān)注節(jié)點變成節(jié)點a的父節(jié)點b；
? ??????????????????圍繞新的關(guān)注節(jié)點b左旋；
? ??????????????????跳到 CASE 3
? ? ? ? ? ? ? ? Case?3.如果關(guān)注節(jié)點是a，叔叔節(jié)點d是黑色，關(guān)注節(jié)點a是其父節(jié)點b的左子節(jié)點
? ??????????????????圍繞關(guān)注節(jié)點a的祖父節(jié)點c右旋；
? ??????????????????將關(guān)注節(jié)點a的父節(jié)點b、兄弟節(jié)點c的顏色互換。
? ? ? ? 刪除操作的平衡調(diào)整
? ? ? ? ? ? 實現(xiàn)過程
? ? ? ? ? ? ? ? 1.針對刪除節(jié)點初步調(diào)整
? ??????????????????紅黑樹定義中“只包含紅色節(jié)點和黑色節(jié)點”，經(jīng)過初步調(diào)整之后，
????????????????????為了保證這一條要求，有些節(jié)點會被標(biāo)記成兩種顏色，“紅-黑”或者“黑-黑”。
????????????????????如果一個節(jié)點被標(biāo)記為“黑-黑”，那在計算黑色節(jié)點個數(shù)的時候，要算成兩個黑色節(jié)
? ??????????????????如果一個節(jié)點既可以是紅色，也可以是黑色，在下圖用一半紅色一半黑色來表示
????????????????????如果一個節(jié)點是“紅-黑”或者“黑-黑”，我會用左上?的一個小黑點來表示額外的黑色
? ? ? ? ? ? ? ? ? ? Case 1:如果要刪除的節(jié)點是a，它只有一個子節(jié)點b
????????????????????????刪除節(jié)點a，并且把節(jié)點b替換到節(jié)點a的位置
? ??????????????????????節(jié)點a只能是黑色，節(jié)點b也只能是紅色，不符合紅黑樹定義，把節(jié)點b改為黑色
????????????????Case 2:如果要刪除的節(jié)點a有兩個非空子節(jié)點，且后繼節(jié)點是節(jié)點a的右子節(jié)點c
? ??????????????????如果節(jié)點a后繼節(jié)點是右子節(jié)點c，把節(jié)點a刪除且將節(jié)點c替換到節(jié)點a的位置
? ??????????????????然后把節(jié)點c的顏色設(shè)置為跟節(jié)點a相同的顏色
? ??????????????????如果節(jié)點c是黑色，給節(jié)點c右子節(jié)點d多加一個黑色，則節(jié)點d變成“紅-黑”或“黑-黑”
????????????????????這時關(guān)注節(jié)點變成了節(jié)點d，第二步的調(diào)整操作就會針對關(guān)注節(jié)點d來做
? ? ? ? ? ? ? ? ? ? Case 3:如果要刪除是節(jié)點a有兩個非空子節(jié)點，且節(jié)點a后繼節(jié)點不是右子節(jié)點
? ??????????????????????找到后繼節(jié)點d，并將它刪除，刪除后繼節(jié)點d的過程參照CASE 1
? ??????????????????????將節(jié)點a替換成后繼節(jié)點d
? ??????????????????????把節(jié)點d的顏色設(shè)置為跟節(jié)點a相同的顏色
? ??????????????????????如果節(jié)點d是黑色，給節(jié)點d右子節(jié)c多加一個黑色，則節(jié)點c就成“紅-黑”或“黑-黑”
? ??????????????????????這時關(guān)注節(jié)點變成節(jié)點c，第二步的調(diào)整操作就會針對關(guān)注節(jié)點c來做
????????????????2.針對關(guān)注節(jié)點進(jìn)行二次調(diào)整
? ??????????????????經(jīng)過初步調(diào)整之后，關(guān)注節(jié)點變成“紅-黑”或“黑-黑”節(jié)點
? ??????????????????二次調(diào)整是為了讓紅黑樹中不存在相鄰的紅色節(jié)點
? ??????????????????針對這個關(guān)注節(jié)點，我們再分四種情況來進(jìn)行二次調(diào)整
? ? ? ? ? ? ? ? ? ? Case 1:?如果關(guān)注節(jié)點是a，它的兄弟節(jié)點c是紅色的
? ??????????????????????圍繞關(guān)注節(jié)點a的父節(jié)點b左旋
? ??????????????????????關(guān)注節(jié)點a的父節(jié)點b和祖父節(jié)點c交換顏色
? ??????????????????????關(guān)注節(jié)點不變
? ??????????????????????繼續(xù)從四種情況中選擇適合的規(guī)則來調(diào)整
? ? ? ? ? ? ? ? ? ? Case 2:?如果關(guān)注節(jié)點是a，兄弟節(jié)點c是黑色，且節(jié)點c左右子節(jié)點d、e都是黑色
? ??????????????????????將關(guān)注節(jié)點a的兄弟節(jié)點c的顏色變成紅色
? ??????????????????????從關(guān)注節(jié)點a中去掉一個黑色，這個時候節(jié)點a就是單純的紅色或者黑色
? ??????????????????????給關(guān)注節(jié)點a的父節(jié)點b添加一個黑色，這時節(jié)點b就變成了“紅-黑”或者“黑黑”
? ??????????????????????關(guān)注節(jié)點從a變成其父節(jié)點b
? ??????????????????????繼續(xù)從四種情況中選擇符合的規(guī)則來調(diào)整
????????????????????Case 3:?如果關(guān)注節(jié)點是a，兄弟節(jié)點c是黑色，c左子節(jié)點d紅色，c右子節(jié)點e黑色
????????????????????????圍繞關(guān)注節(jié)點a的兄弟節(jié)點c右旋
????????????????????????節(jié)點c和節(jié)點d交換顏色
????????????????????????關(guān)注節(jié)點不變跳轉(zhuǎn)到Case 4，繼續(xù)調(diào)整
????????????????????Case 4:?如果關(guān)注節(jié)點a的兄弟節(jié)點c是黑色的，并且c的右子節(jié)點是紅色的
? ??????????????????????圍繞關(guān)注節(jié)點a的父節(jié)點b左旋
????????????????????????將關(guān)注節(jié)點a的兄弟節(jié)點c的顏色，跟關(guān)注節(jié)點a的父節(jié)點b設(shè)置成相同的顏色；
????????????????????????將關(guān)注節(jié)點a的父節(jié)點b的顏色設(shè)置為黑色；
????????????????????????從關(guān)注節(jié)點a中去掉一個黑色，節(jié)點a就變成了單純的紅色或者黑色；
????????????????????????將關(guān)注節(jié)點a的叔叔節(jié)點e設(shè)置為黑色；
????????????????????????調(diào)整結(jié)束。
? ? 總結(jié)操作過程
? ??????第一點，把紅黑樹的平衡調(diào)整的過程比作魔方復(fù)原，不要過于深究這個算法的正確性
? ??????????只要按照固定的操作步驟，保持插入、刪除的過程，不破壞平衡樹的定義即可
? ??????第二點，找準(zhǔn)關(guān)注節(jié)點，不要搞丟、搞錯關(guān)注節(jié)點
? ??????????每種操作規(guī)則，都是基于關(guān)注節(jié)點來做的
? ??????????在迭代的調(diào)整過程中，關(guān)注節(jié)點在不停地改變
? ??????第三點，插入操作的平衡調(diào)整比較簡單，但是刪除操作就比較復(fù)雜
? ??????????針對刪除操作，我們有兩次調(diào)整，
????????????第一次針對要刪除的節(jié)點做初步調(diào)整，讓調(diào)整后的紅黑樹繼續(xù)滿足第四條定義
????????????????“每個節(jié)點到可達(dá)葉子節(jié)點的路徑都包含相同個數(shù)的黑色節(jié)點”
????????????????但是不滿足第三條定義，有可能會存在兩個紅色節(jié)點相鄰的情況
????????????第二次調(diào)整就是解決讓紅黑樹不存在相鄰的紅色節(jié)點的問題
????幾種平衡二叉查找樹對比
? ? ? ? Treap(樹堆)
? ??????????Treap是二叉搜索樹和堆合并構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點數(shù)據(jù)域包含2個值
? ??????????????key值: 滿足左子樹<根節(jié)點<右子樹 (滿足二叉搜索樹特性)
? ? ? ? ? ? ????weight值:小于等于(或大于等于)左右子節(jié)點 (滿足堆特性)
? ? ? ? ? ? 利用weight值作為隨機(jī)因子來調(diào)整二叉樹形狀，所以在大部分情況下更平衡，性能更高
? ? ? ? ? ? 但無法避免極端情況下時間復(fù)雜度的退化，不適用對于操作時間非常敏感場景
? ??????Splay Tree(伸展樹)
? ??????????是一種能夠自我平衡的二叉查找樹
? ??????????每次查找后對樹進(jìn)行調(diào)整，把被查找的條目搬移到離根節(jié)點近一些的地方
? ??????????它會沿著從某個節(jié)點到根節(jié)點之間的路徑，通過一系列的旋轉(zhuǎn)把這個節(jié)點搬移到根節(jié)點
? ? ? ? ? ? 良好的的性能，同時存儲所需的內(nèi)存少
????????????但無法避免極端情況下時間復(fù)雜度的退化(特別在多線程環(huán)境)? ? ? ? ? ??
? ??????AVL樹
????????????一種高度平衡的二叉樹，查找的效率非常高;?
????????????但是AVL樹為了維持高度的平衡，每次插入、刪除等操作都要調(diào)整，就比較復(fù)雜、耗時;?
? ? ? ? ? ? 對于有頻繁的插入、刪除操作的數(shù)據(jù)集合，使用AVL樹的代價就有點高
????????紅黑樹
? ??????????紅黑樹的插入、刪除、查找等操作性能都比較穩(wěn)定
? ? ? ? ? ? 因近似平衡，在維護(hù)平衡的成本上，要比AVL樹要低
? ? ? ? 綜合對比
? ? ? ? ? ? 為了支撐這種工業(yè)級的應(yīng)用，我們更傾向于這種性能穩(wěn)定的平衡二叉查找樹
