紅黑樹的概念？什么是紅黑樹？
紅黑樹是一種含有紅黑節(jié)點(diǎn)并能自平衡的二叉查找樹。區(qū)別于avl樹, avl樹是完美平衡二叉樹, 紅黑樹是弱平衡二叉樹回怜。
紅黑樹的五大性質(zhì)（最核心）
1.每個(gè)節(jié)點(diǎn)要么是黑色, 要么是紅色。
2.根節(jié)點(diǎn)是黑色。 ---> 硬性規(guī)定, 無法推導(dǎo)出這個(gè)結(jié)論玉雾。
3.每個(gè)葉子節(jié)點(diǎn)(Nil)是黑色翔试。 ---> 葉子節(jié)點(diǎn)都是黑色虛節(jié)點(diǎn)(color=black;value=None)
4.每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)一定都是黑色(父節(jié)點(diǎn)也是黑色)。
5.任意一個(gè)節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑節(jié)點(diǎn)复旬。 (紅黑樹不是完美平衡, 但是黑色完美平衡)
紅黑樹的規(guī)律（由五大性質(zhì)推導(dǎo)出）
結(jié)論：性質(zhì)4 5作為約束可以保證任意節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)路徑最長不會(huì)超過最短路徑的2倍
原因：最極端情況下：出現(xiàn)最短路徑時(shí), 這條路徑必然都是黑節(jié)點(diǎn); 出現(xiàn)最長路徑時(shí), 這條路徑必然是紅黑節(jié)點(diǎn)相間構(gòu)成, 此時(shí)路徑上紅節(jié)點(diǎn)數(shù)量=黑節(jié)點(diǎn)數(shù)量; 再結(jié)合性質(zhì)5, 極端情況下最長路徑也僅僅是最短路徑的兩倍垦缅。
紅黑樹的操作
紅黑樹自平衡的原子操作：變色, 旋轉(zhuǎn)(圓心, 方向)
紅黑樹的插入操作
思路：每次插入之后要操作保持紅黑樹的性質(zhì)。1. 查找插入的位置 2.插入后自平衡
自平衡的4種情況：(設(shè)curr為當(dāng)前節(jié)點(diǎn))
紅黑樹的刪除操作
思路：如果被刪除節(jié)點(diǎn)沒有孩子驹碍，直接刪除即可壁涎。如果刪除節(jié)點(diǎn)只有一個(gè)孩子：1.刪除節(jié)點(diǎn)為紅色時(shí), 直接拿孩子補(bǔ)位即可; 2.刪除節(jié)點(diǎn)為黑色時(shí), 2.1.孩子為紅色, 直接拿孩子替換并將孩子染成黑色; 2.2.孩子為黑色則復(fù)雜得多。如有兩個(gè)孩子, 則先要找到該節(jié)點(diǎn)前驅(qū)(左子樹最大)或者后繼(右子樹最小), 習(xí)慣上一般選擇后繼, 這里我們用后繼志秃。然后前驅(qū)或后繼的值復(fù)制到要?jiǎng)h除的節(jié)點(diǎn), 最后刪除前驅(qū)或后繼怔球。由于前驅(qū)和后繼不可能有兩個(gè)孩子, 刪除前驅(qū)后繼=刪除只有一個(gè)孩子或沒有孩子的節(jié)點(diǎn)。
復(fù)雜度分析
毫無疑問浮还，紅黑樹和avl樹沒有理用額外空間竟坛，所以他們空間復(fù)雜度都為O(1)
avl樹和紅黑樹查詢時(shí)間復(fù)雜度均為O(logn)平均查詢時(shí)間紅黑樹稍微慢一點(diǎn)但是沒慢多少。雖然對(duì)于插入和刪除節(jié)點(diǎn), avl樹和紅黑樹最壞情況下時(shí)間復(fù)雜度均為O(logn), 但在自平衡的時(shí)候, 紅黑樹由于有黑色節(jié)點(diǎn)的存在(上文中自平衡的情況2), 每次parent為黑色時(shí)復(fù)雜度降為O(1)钧舌。根據(jù)性質(zhì)4 5 得出紅黑樹的每條路徑上黑節(jié)點(diǎn)數(shù)量 大于等于 紅節(jié)點(diǎn)數(shù)量, 所以至少50%的概率parent為黑色担汤。所以紅黑樹自平衡的平均時(shí)間復(fù)雜度 小于等于 avl樹平均時(shí)間復(fù)雜度的一半。
本文轉(zhuǎn)自我知乎原文:?紅黑樹超全講解純干貨帶流程圖方便收藏
歡迎關(guān)注我的知乎賬號(hào)：進(jìn)擊的steve
