rbt(紅黑樹)

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

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

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

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

紅黑樹的5個性質

1. 節(jié)點必須是紅色或者黑色(所有葉子節(jié)點是NIL節(jié)點)捕仔。
2. 根節(jié)點必須是黑色。
3. 葉節(jié)點(NIL)是黑色的歧杏。（NIL節(jié)點無數(shù)據(jù)，是空節(jié)點）
4. 紅色節(jié)點必須有兩個黑色兒子節(jié)點 (所以父節(jié)點必定也是黑色)迷守。
5. 從任一節(jié)點出發(fā)到其每個葉子節(jié)點的路徑，黑色節(jié)點的數(shù)量是相等的(黑高 BlackHeight bh 實際應用中旺入，可以忽略NIL節(jié)點兑凿，所以黑高少1)。

以上條件能保證任意同級子樹高度差不超過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個節(jié)點的RBT,最大高度是2log(n+1)

插入節(jié)點都默認紅色(因為插入黑色茵瘾，那必定黑高不平衡礼华，就必須要調(diào)整了，就和avl一樣了拗秘。所以插入紅色圣絮，有部分幾率不需要調(diào)整)

調(diào)整
自底向上，一層一層的調(diào)整雕旨，直到父節(jié)點為黑色的時候扮匠，或者到根捧请。

• 插入后情況
  • 不需要調(diào)整(父節(jié)點為黑色;或者插入的是根節(jié)點)
    1. 父節(jié)點是黑色的情況：
       因為rbt基于bst，所以插入的新節(jié)點只可能是葉子節(jié)點
       所以插入的節(jié)點如果父節(jié)點是黑色棒搜，就滿足rbt5條性質疹蛉，不需要調(diào)整
    2. 如果是根節(jié)點，直接把該節(jié)點設置為黑色
  • 需要調(diào)整(父節(jié)點為紅色)
    (由于性質4力麸，祖父節(jié)點必定是黑色)
    叔叔節(jié)點(當前節(jié)點的祖父節(jié)點的另一個子節(jié)點)
    1. ·父節(jié)點·為·祖父節(jié)點·的左孩子的情況
       • case1:·叔叔節(jié)點·是紅色可款。(把父層同時置黑，試滿足第4性質克蚂，然后祖父可能又有沖突(沖突向上拋)闺鲸，所以繼續(xù)遞歸)
         1. 將·父節(jié)點·和·叔叔節(jié)點·設為黑色
         2. 將·祖父節(jié)點·設為紅色
         3. 從·祖父節(jié)點·進行遞歸調(diào)整
       • case2:叔叔節(jié)點是黑色。且當前節(jié)點是其父節(jié)點的右孩子埃叭。(舊父節(jié)點的樹一直滿足5條性質摸恍，把不滿足的當前節(jié)點繼續(xù)遞歸(沖突向上拋))
         1. 將·父節(jié)點·左旋
         2. 從·新父節(jié)點·執(zhí)行case3
       • case3:叔叔節(jié)點是黑色。且當前節(jié)點是其父節(jié)點的左孩子游盲。(因為父節(jié)點和叔叔節(jié)點都是黑色误墓，所以右旋后，祖父節(jié)點必定是黑色益缎，已經(jīng)滿足所有性質谜慌，不需要遞歸了)
         1. 將·父節(jié)點·設為黑色
         2. 將·祖父節(jié)點·設為紅色
         3. 將·祖父節(jié)點·右旋
         4. 從·新當前節(jié)點的右節(jié)點·繼續(xù)進行遞歸調(diào)整(其實到這里就結束了！)
    2. ·父節(jié)點·為·祖父節(jié)點·的右孩子的情況
       與上同理(鏡像)
• 刪除后情況
  • 不需要調(diào)整(刪除的是紅色節(jié)點莺奔，上下都是黑色節(jié)點欣范，黑高平衡)
    1. 回溯時，如果·當前節(jié)點·是·根節(jié)點·或者是·紅色節(jié)點·令哟，直接置黑
  • 需要調(diào)整(刪除的是黑色節(jié)點恼琼，黑高不平衡)
    兄弟節(jié)點(sib,sibling 當前節(jié)點的父節(jié)點的另一個子節(jié)點)
    左右侄子(nephew,ln,rn 當前節(jié)點的父節(jié)點的另一個子節(jié)點的左右子節(jié)點)
    1. 刪除節(jié)點為·父節(jié)點·的左孩子情況(左黑高低)
       • case1:·兄弟節(jié)點·為紅色。(右樹的根節(jié)點為紅色屏富，所以它下面的兩個子樹黑高一定平衡晴竞。把它父節(jié)點左旋，不影響它黑高平衡)(最終右黑高還是比做黑高大)
         1. 將·兄弟節(jié)點·設為黑色
         2. 將·父節(jié)點·設為紅色
         3. 將·父節(jié)點·左旋
       • case2:·兄弟節(jié)點·為黑色;·左右侄子節(jié)點·為黑色
         1. 將·兄弟節(jié)點·設為紅色
         2. 從·父節(jié)點·進行遞歸調(diào)整狠半。
       • case3:·兄弟節(jié)點·為黑色;·左侄子節(jié)點·為紅色;·右侄子節(jié)點·為黑色噩死。(兄弟子樹的黑高被減，然后把多的黑高向上拋)(必定兄弟節(jié)點為黑色神年，右侄子節(jié)點為紅色已维，后一步必定是case4)
         1. 將·左侄子節(jié)點·設為黑色
         2. 將·兄弟節(jié)點·設為紅色
         3. 將·兄弟節(jié)點·右旋
       • case4:·兄弟節(jié)點·為黑色;·右侄子節(jié)點·為紅色。
         (如果父節(jié)點為黑色已日，左旋的時候垛耳，帶走了左侄子節(jié)點，然后右侄子節(jié)點又被置為了黑色(黑高加一，又因為父節(jié)點被左旋堂鲜，黑高減一栈雳，所以不動)而原來黑高少的左子樹因為被加了一個黑色的父節(jié)點，所以黑高和右子樹一樣了泡嘴；
         如果父節(jié)點是紅色甫恩，左旋同時設置兄弟節(jié)點為紅色(新父節(jié)點還是紅色)，右子樹黑高被減一酌予，左侄子節(jié)點被帶到左子樹(同樣掛到黑節(jié)點下磺箕，黑高不變)，左子樹上方則加了一個黑色節(jié)點抛虫，最終左右平衡)
         1. 將·兄弟節(jié)點·設為·父節(jié)點·的顏色
         2. 將·父節(jié)點·設為黑色
         3. 將·右侄子節(jié)點·設為黑色
         4. 將·父節(jié)點·左旋
         5. 結束(因為原本減去的黑高又被加回來了松靡，所以沒必要再繼續(xù)調(diào)整了)
            執(zhí)行意義{
            case2執(zhí)行完后，如果執(zhí)行case1建椰，并且最后·父節(jié)點·是黑色(現(xiàn)在左右黑高已經(jīng)相等雕欺，但是·父節(jié)點·是黑色，所以不能保證·父節(jié)點·還平衡棉姐，需要遞歸調(diào)整)
            case2執(zhí)行完后屠列，如果執(zhí)行case2，并且最后·父節(jié)點·是紅色(直接把·父節(jié)點·置黑伞矩，剛好補全了因為刪除和·兄弟節(jié)點·置紅而降低的黑高笛洛，結束)
            }
    2. 刪除節(jié)點為·父節(jié)點·的右孩子情況
       • 與上同理(鏡像)