文章目錄

• • 紅黑樹的由來
  • 紅黑樹需要遵守的五大規(guī)則
  • 紅黑樹與4階B樹的相互轉換！！
  • 紅黑樹的插入（12種情況）
  • 紅黑樹的刪除（3大類情況）
  • 紅黑樹的平衡 以及與AVL樹的性能比較

紅黑樹的由來

紅黑樹：紅黑樹是近似平衡的二叉搜索樹。
比如二叉搜索樹是為了優(yōu)化線性表的搜索，把時間復雜度On優(yōu)化為Olog2n和On之間（退化為鏈表）。
再比如AVL樹為完全自平衡的二叉搜索樹，優(yōu)化了二叉搜索樹，能夠確保二叉搜索樹不會退化為鏈表，做到時間復雜度更加貼近Olog2n，由于每一次出現(xiàn)不平衡都要旋轉，加入了大量的旋轉操作。

而紅黑樹是近似平衡的二叉搜索樹，優(yōu)化了AVL樹大量的旋轉操作，在綜合性能上比AVL樹更優(yōu)秀

紅黑樹需要遵守的五大規(guī)則

無論是添加還是刪除，只需要遵守這五大原則，紅黑樹就是平衡的，如果添加或刪除打破了規(guī)則，那么就需要進行調整
第一點第二點第三點都是白給的，后面兩點比較重要

紅黑樹與4階B樹的相互轉換！！

紅黑樹的插入刪除有多種情況，轉化為B樹結構后更好理解，紅黑樹所有操作完全等價于四階B樹
每一個黑結點與其兩個紅色的子結點組合起來，就是一個4階B樹的結點
從B樹的角度去理解紅黑樹，推薦回看網課戀上數(shù)據(jù)結構與算法，個人認為從轉換為B樹后再理解插入刪除的不同情況，確實比較好理解，所以建議回顧戀上數(shù)據(jù)結構的視頻或PPT

紅黑樹的插入（12種情況）

插入刪除原則：就是插入刪除后依然符合紅黑樹五大原則，不然就調整
插入主要會打破性質四（默認插入結點為紅色）

插入共有12種可能性

不用管種：其中4種不用管

旋轉種：剩下8種中2種LL或RR，兩種LR或RL，這四種可以通過旋轉和重新染色,操作過程與AVL樹的旋轉類似（但是記得染色，B樹結點中間那個元素是黑的）

上溢種：剩下4種，在插入前轉化成B樹那個結點已經有了紅黑紅三個結點了，此時插入結點會造成B樹結點的上溢，此時操作和B樹中上溢的操作一樣，中間結點向上合并（可能造成連上溢），兩邊結點分裂成兩個新的B樹結點，合并操作看成新的對上面的插入操作（并把那個中間結點染成紅色），然后再按照規(guī)則染色即可

注意下面的uncle指的是叔父結點，也就是父結點的兄弟結點
此外，看起來有些結點沒有兄弟結點，也就沒有uncle結點，但是不要忽視紅黑樹的null結點也算結點而且是黑色的

紅黑樹的刪除（3大類情況）

• 刪除的是紅色節(jié)點——不用調整，刪完不影響紅黑樹的五條性質
  - 刪除的是黑色結點：
• 1.刪除的黑色結點度為2（紅黑樹種其實只有度為2和葉子結點（null結點），但是這里為了方便，就省略了null結點的存在，即有兩個紅色子結點）
• 聯(lián)想二叉樹中度為二的結點的刪除，會找結點的前驅或后繼結點刪除，且最后刪除的一定是葉子結點，因此紅黑樹中刪除度為二的黑色結點，往往最后刪除的是替代它的紅色結點，因此也不用任何平衡
• 2.刪除的黑色結點度為1（有一個紅色子結點）
• 同二叉樹度為1結點的刪除，用子結點替代，但是需要重新染色
• 3.刪除的黑色結點度為0（沒有紅色子結點），比較復雜建議看ppt，關鍵在于轉化為B樹結構并聯(lián)想上溢下溢的操作
• 同四階B樹中只有一個元素的結點的刪除，會造成下溢，同B樹操作，轉化成B樹結構，看兄弟結點能不能借，能就旋轉兄弟上去，父結點下來；不能就父結點中間那個下來合并，可以見B樹筆記（2種）。
• 另外一種是轉化為B樹結構中的父結點只有一個結點，這時會造成連續(xù)下溢。

紅黑樹的平衡 以及與AVL樹的性能比較

AVL樹的平衡：通過平衡因子，保證每個結點的兩個子樹高度相差1以內
紅黑樹的平衡：通過維護五條性質，使紅黑樹等價于四階B樹, 其平衡為近似平衡，不像AVL樹那樣完全平衡，也不會像普通二叉搜索樹那樣會退化成為鏈表，但整體性能優(yōu)于AVL樹。
平衡標準：沒有一條路徑會大于其他路徑的兩倍（最短全黑路徑，最長一黑一紅）
也可以理解為黑高度平衡，所有子樹的黑結點高度是平衡的

AVL樹和紅黑樹的最大區(qū)別：添加刪除所需的旋轉時間復雜度，添加都是
O（1），刪除AVL樹可能需要Ologn而紅黑樹依舊是O（1）
單論搜索其實還是AVL樹占優(yōu)，畢竟樹高低，但是涉及添加刪除就一般是紅黑樹占優(yōu)了

總結

以上是生活随笔為你收集整理的2021-10-15 红黑树 概念和平衡操作理解以及与AVL对比分析 恋上数据结构笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。