学习算法导论-红黑树之摘录
1.如果搜索樹的高度較低時，這些集合操作會執行得較快。然而，如果樹的高度較高時，這些集合可能并不比在鏈表上執行得快。紅黑樹(red-black tree)是許多"平衡"搜索樹的一種，可以保證在最壞情況下基本動態集合操作的時間復雜度為O(lgn)。
二、紅黑樹的性質
? ? ?紅黑樹是一棵二叉搜索樹，它在每個節點上增加了一個存儲位來表示節點的顏色，可以是RED或BLACK。通過對任何一條從根到葉子的簡單路徑上各個節點的顏色進行約束，紅黑樹確保沒有一條路徑會比其他路徑長出2倍，因為是近似于平衡的。
? ? ?2.1 樹中每個節點包含5個屬性:color、key、left、right和p。如果一個節點沒有子節點或父節點，則該節點相應指針屬性的值為NIL。我們可以把這些NIL視為指向二叉搜索樹的葉節點(外部節點)的指針，而把帶關鍵字的節點視為樹的內部節點。
? ?一棵紅黑樹是滿足下面紅黑性質的二叉搜索樹:
? ? 1.每個節點或是紅色的，或是黑色的。
? ? 2.根節點是黑色的。
? ? 3.每個葉節點(NIL)是黑色的。
? ? 4.如果一個節點時紅色的，則它的兩個子節點都是黑色的。
? ? 5.對每個節點，從該節點到其所有后代葉節點的簡單路徑上，均包含相同數目的黑色節點。
? ? 下圖(a)顯示了一個紅黑樹的例子:
? ?
? ? ?下圖(b)所有指向NIL的指針都用指向哨兵T.nil的指針替換:
? ? ? ??
? ? ? ? 我們通常將注意力放在紅黑樹的內部節點上，因為它們存儲了關鍵字的值。在本章的后面部分,所畫的紅黑樹都忽略了葉節點，下圖(c)所示:
? ? ? ?
? ? 2.2 旋轉
? ? ? ? ? 搜索樹操作TREE-INSERT和TREE-DELETE在含n個關鍵字的紅黑樹上，運行花費時間為O(lgn)。由于這兩個操作對樹進行了修改，結果可能違反紅黑性質，為了維護這些性質，必須要改變樹中某些節點的顏色以及指針結構。
? ? ? ? ? ?指針結構的修改是通過旋轉(ratation)來完成的，這是一種能保持二叉搜索樹性質的搜索樹局部操作。下圖中給出了兩種旋轉：左旋和右旋。
? ? ? ? ? ?在LEFT-ROTATE的偽代碼中，假設x.right不等于T.nil且根節點的父節點為T.nil。
? ? ? ??
? ? ? ? ? ? ? ?在旋轉操作中只有指針改變，其他所有屬性都保持不變.
? ? ? ? ??
? ? ? ? ? 2.3 插入
? ? ? ? ? ? ?我們可以在O(lgn)時間內完成向一棵含n個節點的紅黑樹中插入一個新節點。為了做到這一點，利用TREE-INSERT過程的一個略作修改的版本來將節點z插入樹T內，就好像T是一棵普通的二叉搜索樹一樣，然后將z著為紅色。為保證紅黑性質能繼續保持，我們調用一個輔助程序RB-INSERT-FIXUP來對節點重新著色并旋轉。調用RB-INSERT(T,z)在紅黑樹T內插入節點z,假設z的key屬性已被事先賦值。
? ? ? ? ?
? ? ? ? ?過程TREE-INSERT和RB-INSERT之間有4處不同。第一，TREE-INSERT內的所有NIL都被T.nil代替。第二，RB-INSERT的第14-15行置z.left和z.right為T.nil,以保持合理的樹結構。第三，在第16行將z著為紅色。第四，因為將z著為紅色可能違反其中的一條紅黑性質，所以在RB-INSERT的第17行中調用RB-INSERT-FIXUP(T,z)來保持紅黑性質。
? ? ? ? 為了理解RB-INSERT-FIXUP過程如何工作，把代碼分為三個主要的步驟。首先，要確定當節點z被插入并著為紅色后，紅黑性質中有哪些不能繼續保持，其次，應分析第1-15行中while循環的總目標。最后，要分析while循環體中的三種情況，看看它們是如何完成目標的。圖13-4給出一個范例，顯示在一棵紅黑樹上RB-INSERT-FIXUP如何操作。
? ? ??
? ? ? ?
? ?2.4 刪除
? ? ? ?與n個節點的紅黑樹上的其他基本操作一樣，刪除一個節點要花費O(lgn)時間。與插入操作相比，刪除操作要稍微復雜些。
? ? ? ? 從一棵紅黑樹中刪除節點的過程是基于TREE-DELETE過程而來的。首先，需要特別設計一個供TREE-DELETE調用的子過程TRANSPLANT,并將其應用到紅黑樹上:
? ??
? ? 過程RB-TRANSPLANT與TRANSPLANT有兩點不同。首先，第一行引用哨兵T.nil而不是NIL。其次，第6行對v.p的賦值是無條件執行:即使v指向哨兵，也要對v.p賦值。實際上，當v=T.nil時，也能給v.p賦值。
? ?
? ? ? ? ?
? ? ? ? ? ??
總結
以上是生活随笔為你收集整理的学习算法导论-红黑树之摘录的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 学习quot;平衡二叉树quot;之摘录
- 下一篇： “ModSecurity2”源码分析