rbt(紅黑樹)

圖解紅黑樹：http://www.itdecent.cn/p/0eaea4cc5619
數(shù)據(jù)結(jié)構(gòu)可視化網(wǎng)站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
demo：https://github.com/lilingyan/take-TreeMap-apart

AVL插入時(shí)平衡次數(shù)較多，RBT是AVL的折中方法(放寬平衡冗余，減少插入后平衡次數(shù))，插入刪除效率略高于AVL，查詢效率略低于AVL

• 插入調(diào)整時(shí)(最壞的情況(需要回溯到頂))
  • avl是一層一層向上(logN)
  • rbt是兩層兩層向上(logN/2)
• 插入調(diào)整時(shí)(最壞的情況(需要回溯到頂))
  • rbt在回溯的時(shí)候，只要碰到紅色就結(jié)束了，所以略好于avl
• 查詢時(shí)(rbt最壞情況是左右子樹差一倍高度)

rbt必定是bst
rbt任意黑節(jié)點(diǎn)為根的子樹必定是rbt(遞歸)

紅黑樹的5個(gè)性質(zhì)

1. 節(jié)點(diǎn)必須是紅色或者黑色(所有葉子節(jié)點(diǎn)是NIL節(jié)點(diǎn))。
2. 根節(jié)點(diǎn)必須是黑色。
3. 葉節(jié)點(diǎn)(NIL)是黑色的。（NIL節(jié)點(diǎn)無數(shù)據(jù)，是空節(jié)點(diǎn)）
4. 紅色節(jié)點(diǎn)必須有兩個(gè)黑色兒子節(jié)點(diǎn) (所以父節(jié)點(diǎn)必定也是黑色)。
5. 從任一節(jié)點(diǎn)出發(fā)到其每個(gè)葉子節(jié)點(diǎn)的路徑，黑色節(jié)點(diǎn)的數(shù)量是相等的(黑高 BlackHeight bh 實(shí)際應(yīng)用中，可以忽略NIL節(jié)點(diǎn)，所以黑高少1)。

以上條件能保證任意同級(jí)子樹高度差不超過2倍

• BH(left)==BH(right)
• 若H(left)>=H(right) 則H(left)<=2*H(right)+1
• 若H(left)<=H(right) 則H(right)<=2*H(left)+1

定理:n個(gè)節(jié)點(diǎn)的RBT,最大高度是2log(n+1)

插入節(jié)點(diǎn)都默認(rèn)紅色(因?yàn)椴迦牒谏潜囟ê诟卟黄胶?，就必須要調(diào)整了，就和avl一樣了。所以插入紅色，有部分幾率不需要調(diào)整)

調(diào)整
自底向上，一層一層的調(diào)整，直到父節(jié)點(diǎn)為黑色的時(shí)候，或者到根。

• 插入后情況
  • 不需要調(diào)整(父節(jié)點(diǎn)為黑色;或者插入的是根節(jié)點(diǎn))
    1. 父節(jié)點(diǎn)是黑色的情況：
       因?yàn)閞bt基于bst，所以插入的新節(jié)點(diǎn)只可能是葉子節(jié)點(diǎn)
       所以插入的節(jié)點(diǎn)如果父節(jié)點(diǎn)是黑色，就滿足rbt5條性質(zhì)，不需要調(diào)整
    2. 如果是根節(jié)點(diǎn)，直接把該節(jié)點(diǎn)設(shè)置為黑色
  • 需要調(diào)整(父節(jié)點(diǎn)為紅色)
    (由于性質(zhì)4，祖父節(jié)點(diǎn)必定是黑色)
    叔叔節(jié)點(diǎn)(當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn))
    1. ·父節(jié)點(diǎn)·為·祖父節(jié)點(diǎn)·的左孩子的情況
       • case1:·叔叔節(jié)點(diǎn)·是紅色。(把父層同時(shí)置黑，試滿足第4性質(zhì)，然后祖父可能又有沖突(沖突向上拋)，所以繼續(xù)遞歸)
         1. 將·父節(jié)點(diǎn)·和·叔叔節(jié)點(diǎn)·設(shè)為黑色
         2. 將·祖父節(jié)點(diǎn)·設(shè)為紅色
         3. 從·祖父節(jié)點(diǎn)·進(jìn)行遞歸調(diào)整
       • case2:叔叔節(jié)點(diǎn)是黑色。且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右孩子。(舊父節(jié)點(diǎn)的樹一直滿足5條性質(zhì)，把不滿足的當(dāng)前節(jié)點(diǎn)繼續(xù)遞歸(沖突向上拋))
         1. 將·父節(jié)點(diǎn)·左旋
         2. 從·新父節(jié)點(diǎn)·執(zhí)行case3
       • case3:叔叔節(jié)點(diǎn)是黑色。且當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子。(因?yàn)楦腹?jié)點(diǎn)和叔叔節(jié)點(diǎn)都是黑色，所以右旋后，祖父節(jié)點(diǎn)必定是黑色，已經(jīng)滿足所有性質(zhì)，不需要遞歸了)
         1. 將·父節(jié)點(diǎn)·設(shè)為黑色
         2. 將·祖父節(jié)點(diǎn)·設(shè)為紅色
         3. 將·祖父節(jié)點(diǎn)·右旋
         4. 從·新當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)·繼續(xù)進(jìn)行遞歸調(diào)整(其實(shí)到這里就結(jié)束了！)
    2. ·父節(jié)點(diǎn)·為·祖父節(jié)點(diǎn)·的右孩子的情況
       與上同理(鏡像)
• 刪除后情況
  • 不需要調(diào)整(刪除的是紅色節(jié)點(diǎn)，上下都是黑色節(jié)點(diǎn)，黑高平衡)
    1. 回溯時(shí)，如果·當(dāng)前節(jié)點(diǎn)·是·根節(jié)點(diǎn)·或者是·紅色節(jié)點(diǎn)·，直接置黑
  • 需要調(diào)整(刪除的是黑色節(jié)點(diǎn)，黑高不平衡)
    兄弟節(jié)點(diǎn)(sib,sibling 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn))
    左右侄子(nephew,ln,rn 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)的左右子節(jié)點(diǎn))
    1. 刪除節(jié)點(diǎn)為·父節(jié)點(diǎn)·的左孩子情況(左黑高低)
       • case1:·兄弟節(jié)點(diǎn)·為紅色。(右樹的根節(jié)點(diǎn)為紅色，所以它下面的兩個(gè)子樹黑高一定平衡。把它父節(jié)點(diǎn)左旋，不影響它黑高平衡)(最終右黑高還是比做黑高大)
         1. 將·兄弟節(jié)點(diǎn)·設(shè)為黑色
         2. 將·父節(jié)點(diǎn)·設(shè)為紅色
         3. 將·父節(jié)點(diǎn)·左旋
       • case2:·兄弟節(jié)點(diǎn)·為黑色;·左右侄子節(jié)點(diǎn)·為黑色
         1. 將·兄弟節(jié)點(diǎn)·設(shè)為紅色
         2. 從·父節(jié)點(diǎn)·進(jìn)行遞歸調(diào)整。
       • case3:·兄弟節(jié)點(diǎn)·為黑色;·左侄子節(jié)點(diǎn)·為紅色;·右侄子節(jié)點(diǎn)·為黑色。(兄弟子樹的黑高被減，然后把多的黑高向上拋)(必定兄弟節(jié)點(diǎn)為黑色，右侄子節(jié)點(diǎn)為紅色，后一步必定是case4)
         1. 將·左侄子節(jié)點(diǎn)·設(shè)為黑色
         2. 將·兄弟節(jié)點(diǎn)·設(shè)為紅色
         3. 將·兄弟節(jié)點(diǎn)·右旋
       • case4:·兄弟節(jié)點(diǎn)·為黑色;·右侄子節(jié)點(diǎn)·為紅色。
         (如果父節(jié)點(diǎn)為黑色，左旋的時(shí)候，帶走了左侄子節(jié)點(diǎn)，然后右侄子節(jié)點(diǎn)又被置為了黑色(黑高加一，又因?yàn)楦腹?jié)點(diǎn)被左旋，黑高減一，所以不動(dòng))而原來黑高少的左子樹因?yàn)楸患恿艘粋€(gè)黑色的父節(jié)點(diǎn)，所以黑高和右子樹一樣了；
         如果父節(jié)點(diǎn)是紅色，左旋同時(shí)設(shè)置兄弟節(jié)點(diǎn)為紅色(新父節(jié)點(diǎn)還是紅色)，右子樹黑高被減一，左侄子節(jié)點(diǎn)被帶到左子樹(同樣掛到黑節(jié)點(diǎn)下，黑高不變)，左子樹上方則加了一個(gè)黑色節(jié)點(diǎn)，最終左右平衡)
         1. 將·兄弟節(jié)點(diǎn)·設(shè)為·父節(jié)點(diǎn)·的顏色
         2. 將·父節(jié)點(diǎn)·設(shè)為黑色
         3. 將·右侄子節(jié)點(diǎn)·設(shè)為黑色
         4. 將·父節(jié)點(diǎn)·左旋
         5. 結(jié)束(因?yàn)樵緶p去的黑高又被加回來了，所以沒必要再繼續(xù)調(diào)整了)
            執(zhí)行意義{
            case2執(zhí)行完后，如果執(zhí)行case1，并且最后·父節(jié)點(diǎn)·是黑色(現(xiàn)在左右黑高已經(jīng)相等，但是·父節(jié)點(diǎn)·是黑色，所以不能保證·父節(jié)點(diǎn)·還平衡，需要遞歸調(diào)整)
            case2執(zhí)行完后，如果執(zhí)行case2，并且最后·父節(jié)點(diǎn)·是紅色(直接把·父節(jié)點(diǎn)·置黑，剛好補(bǔ)全了因?yàn)閯h除和·兄弟節(jié)點(diǎn)·置紅而降低的黑高，結(jié)束)
            }
    2. 刪除節(jié)點(diǎn)為·父節(jié)點(diǎn)·的右孩子情況
       • 與上同理(鏡像)