紅黑樹：個人理解與Python實現
【基本事實1】
紅黑樹是一種平衡的二叉查找樹，無論插入還是刪除操作都可以在O(lg n)內實現，而一般的二叉查找樹則在極端情況下會退化為線性結構。
紅黑樹之所以是平衡的二叉查找樹，是因為每個節點都有表示其顏色的域值：紅或黑，在插入和刪除操作的時候依據節點的顏色向平衡的方向調整。根本原因當然是由紅黑樹定義所決定的：
如果一個二叉查找樹滿足如下條件，那么它就稱作紅黑樹：
1.每個節點要么是紅色，要么是黑色
2.根結點是黑色
3.每個葉節點(NIL)為黑色
4.如果一個節點是紅色，其兒子節點一定是黑色
5.對于每個節點，從該節點到其子孫節點的所有路徑上包含相同數目的黑節點
【個人理解1】
紅黑樹的定義中，我認為有這些地方要注意：
1.每個節點只有一種顏色（后面刪除節點的操作時引入的“額外一重黑色”則不滿足此條件，所以一直要性質1調整）
2.定義中的葉節點是指NIL，它們都是黑色，而且沒有子節點。根結點的父節點也是NIL。比如只有一個根節點的紅黑樹，它有兩個葉節點。NIL是沒有值的，只是一種存在。（我在Python的實現中，把NIL值都設定為None）
3.如果一個節點是紅色的，它一定不是根結點，而且一定有父節點（父節點也一定是黑色的）；如果它有兒子節點則一定是黑色兒子節點（每個節點如果左右兒子都是NIL，我認為它沒有兒子）
4.性質5說的就是黑高度了
【基本事實2】
紅黑樹的旋轉
紅黑樹在INSERT和DELETE的過程中，會使用到旋轉操作。紅黑樹有兩種旋轉：左旋和右旋
左旋x：從右圖到左圖的過程
右旋y：從左圖到右圖的過程
【個人理解2】
1.并非每個節點在INSERT或DELETE的過程中都需要旋轉操作
2.左旋就是右兒子y取代父節點x，x作為y的做兒子，y原來的左兒子b成為x現在的右兒子
3.右旋就是左旋的逆向過程
【基本事實3】
紅黑樹的插入
INSERT一個值的過程，就是在二叉查找樹的INSERT操作基礎上，根據紅黑樹性質做必要的調整，比如顏色變化，比如旋轉，也就是INSERT_FIXUP的過程
插入的節點一般設定為紅色然后再調整
【個人理解3】
假設要插入的節點為z，INSERT操作就是把z放到樹的最底層，然后用INSERT_FIXUP區調整。INSERT_FIXUP中要注意的是：
1.如果z的父節點是NIL（即：插入節點z之前紅黑樹為空），那么把z涂黑，并成為根結點（完成插入）
2.如果z的父節點是黑色的，不用調整（完成插入）
3.如果z的父節點是紅色的：
3-0：如果z沒有叔叔節點，那么：
3-0-0：如果z為右兒子，且z的父節點p為左兒子，則左旋z的父節點，成為3-0-1；如果z為左兒子，且z的父節點p為右兒子，則右旋z的父節點p，成為3-0-1；
3-0-1：如果z為左兒子，則“父涂黑，爺涂紅”，然后如果父節點是左兒子，則“爺右旋”，否則“爺左旋”（完成插入）
3-1：如果z的叔叔節點為黑色，那么：
3-1-0：如果z是右兒子，且z的父節點p為左兒子，則左旋z的父節點，成為3-1-1；如果z為左兒子，且z的父節點p為右兒子，則右旋z的父節點p，成為3-1-1；
3-1-1：如果z是左兒子，那么“父涂黑，爺涂紅”，然后如果父節點是左兒子，則“爺右旋”，否則“爺左旋”（完成插入）
3-2：如果z的叔叔節點為紅色，那么“父涂黑，叔涂黑，爺涂紅”，并對爺爺節點g調用INSERT_FIXUP過程
以上序號和《算法導論》中的對應關系：3-2對應case1，3-1-0對應case2，3-1-1對應case3
【基本事實4】
1.紅黑樹刪除一個節點的操作比較復雜，但也是在二叉查查找樹的基礎上，調用DELETE_FIXUP過程來調整
2.如果要刪除的節點z，它有兩個兒子，那么讓z的值設定為z的后繼節點y的值，然后刪除y
3.如果要刪除的節點z只有一個兒子x，那就讓z的節點p和x成為“父子”。如果z原來是紅色的，則不必調用DELETE_FIXUP過程，否則要調用
4.如果要刪除的節點z沒有兒子：那就直接刪除z好了
5.刪除節點時引入了“額外的一層黑色”，《算法導論》中文第二版P173這樣說：
“在RB—DELETE中，如果被刪除的節點y是黑色的，則會產生三個問題。首先，如果y原來是根結點，而y的一個紅色的孩子成為了新的根，這就問犯了性質2）。其次，如果x和p[y]（現在也是p[x]）都是紅的，就違反了性質4）。第三，刪除y將導致先前包含y的任何路徑上黑節點個數少1。因此，性質5）被y的一個祖先破壞了。不久者惡問題的一個辦法就是把結點x視為還有額外的一重黑色。也就是說，如果將人以包含結點x的路徑上黑節點個數加1，則在這種假設下，性質5）成立。當將黑節點y刪除時，將其黑色“下推”至其子節點。現在為題變為結點x可能既不是紅，又不是黑，從而違反了性質1）。結點x是雙重黑色或紅黑，這就分別給包含x的路徑上黑結點個數貢獻2個或1個。x的color屬性仍然是RED（如果x是紅黑的）或BLACK（如果x是雙重黑色）。換言之，一個結點額外的黑色反映在x指向它，而不是它的color屬性。”
【個人理解4】
1.當你想舉反例推翻某個“結論”時，請注意，你的反例中的紅黑樹可能并不是紅黑樹；或者，它滿足紅黑樹的定義，但無法判斷是否能通過“每次插入一個節點”的方式生成。
2.因為有“額外一重黑色”的存在，《算法導論》中關于紅黑樹刪除的case1中，調整前后的兩幅圖雖然“看上去是鏡面對稱”，但前者不滿足性質5，調整后滿足性質5
3.《算法導論》中關于紅黑樹刪除的case2中，x現在為黑色，且有額外的一重黑色（就像是背負著子孫們的希望。。。），此時將x和w都去掉一個黑色，然后使p（x）增加額外的一層黑色。由于w原本為黑色，則現在令w為紅色即可。此時令new_x=p(x)，若new_x原本為紅色，置黑即可結束；否則，對new_x調用DELETE_FIXUP過程
4.DELETE_FIXUP過程，調整的是DELETE(z)過程中z的左/右兒子(當z只有一個兒子時)，或者z的后繼的右兒子
#coding:utf8
#author:HaxtraZ
#description:紅黑樹，python實現
from random import randint
RED = 'red'
BLACK = 'black'
class RBT:
def __init__(self):
# self.items = []
self.root = None
self.zlist = []
def LEFT_ROTATE(self, x):
# x是一個RBTnode
y = x.right
if y is None:
# 右節點為空，不旋轉
return
else:
beta = y.left
x.right = beta
if beta is not None:
beta.parent = x
p = x.parent
y.parent = p
if p is None:
# x原來是root
self.root = y
elif x == p.left:
p.left = y
else:
p.right = y
y.left = x
x.parent = y
def RIGHT_ROTATE(self, y):
# y是一個節點
x = y.left
if x is None:
# 右節點為空，不旋轉
return
else:
beta = x.right
y.left = beta
if beta is not None:
beta.parent = y
p = y.parent
x.parent = p
if p is None:
# y原來是root
self.root = x
elif y == p.left:
p.left = x
else:
p.right = x
x.right = y
y.parent = x
def INSERT(self, val):
z = RBTnode(val)
y = None
x = self.root
while x is not None:
y = x
if z.val < x.val:
x = x.left
else:
x = x.right
z.PAINT(RED)
z.parent = y
if y is None:
# 插入z之前為空的RBT
self.root = z
self.INSERT_FIXUP(z)
return
if z.val < y.val:
y.left = z
else:
y.right = z
if y.color == RED:
# z的父節點y為紅色，需要fixup。
# 如果z的父節點y為黑色，則不用調整
self.INSERT_FIXUP(z)
else:
return
def INSERT_FIXUP(self, z):
# case 1:z為root節點
if z.parent is None:
z.PAINT(BLACK)
self.root = z
return
# case 2:z的父節點為黑色
if z.parent.color == BLACK:
# 包括了z處于第二層的情況
# 這里感覺不必要啊。。似乎z.parent為黑色則不會進入fixup階段
return
# 下面的幾種情況，都是z.parent.color == RED:
# 節點y為z的uncle
p = z.parent
g = p.parent # g為x的grandpa
if g is None:
return
# return 這里不能return的。。。
if g.right == p:
y = g.left
else:
y = g.right
# case 3-0:z沒有叔叔。即：y為NIL節點
# 注意，此時z的父節點一定是RED
if y == None:
if z == p.right and p == p.parent.left:
# 3-0-0:z為右兒子,且p為左兒子，則把p左旋
# 轉化為3-0-1或3-0-2的情況
self.LEFT_ROTATE(p)
p, z = z, p
g = p.parent
elif z == p.left and p == p.parent.right:
self.RIGHT_ROTATE(p)
p, z = z, p
g.PAINT(RED)
p.PAINT(BLACK)
if p == g.left:
# 3-0-1:p為g的左兒子
self.RIGHT_ROTATE(g)
else:
# 3-0-2:p為g的右兒子
self.LEFT_ROTATE(g)
return
# case 3-1:z有黑叔
elif y.color == BLACK:
if p.right == z and p.parent.left == p:
# 3-1-0:z為右兒子,且p為左兒子,則左旋p
# 轉化為3-1-1或3-1-2
self.LEFT_ROTATE(p)
p, z = z, p
elif p.left == z and p.parent.right == p:
self.RIGHT_ROTATE(p)
p, z = z, p
p = z.parent
g = p.parent
p.PAINT(BLACK)
g.PAINT(RED)
if p == g.left:
# 3-1-1:p為g的左兒子，則右旋g
self.RIGHT_ROTATE(g)
else:
# 3-1-2:p為g的右兒子，則左旋g
self.LEFT_ROTATE(g)
return
# case 3-2:z有紅叔
# 則涂黑父和叔，涂紅爺，g作為新的z，遞歸調用
else:
y.PAINT(BLACK)
p.PAINT(BLACK)
g.PAINT(RED)
new_z = g
self.INSERT_FIXUP(new_z)
def DELETE(self, val):
curNode = self.root
while curNode is not None:
if val < curNode.val:
curNode = curNode.left
elif val > curNode.val:
curNode = curNode.right
else:
# 找到了值為val的元素,正式開始刪除
if curNode.left is None and curNode.right is None:
# case1:curNode為葉子節點：直接刪除即可
if curNode == self.root:
self.root = None
else:
p = curNode.parent
if curNode == p.left:
p.left = None
else:
p.right = None
elif curNode.left is not None and curNode.right is not None:
sucNode = self.SUCCESOR(curNode)
curNode.val, sucNode.val = sucNode.val, curNode.val
self.DELETE(sucNode.val)
else:
p = curNode.parent
if curNode.left is None:
x = curNode.right
else:
x = curNode.left
if curNode == p.left:
p.left = x
else:
p.right = x
x.parent = p
if curNode.color == BLACK:
self.DELETE_FIXUP(x)
curNode = None
return False
def DELETE_FIXUP(self, x):
p = x.parent
# w:x的兄弟結點
if x == p.left:
w = x.right
else:
w = x.left
# case1:x的兄弟w是紅色的
if w.color == RED:
p.PAINT(RED)
w.PAINT(BLACK)
if w == p.right:
self.LEFT_ROTATE(p)
else:
self.RIGHT_ROTATE(p)
if w.color == BLACK:
# case2:x的兄弟w是黑色的，而且w的兩個孩子都是黑色的
if w.left.color == BLACK and w.right.color == BLACK:
w.PAINT(RED)
if p.color == BLACK:
return
else:
p.color = BLACK
self.DELETE_FIXUP(p)
# case3:x的兄弟w是黑色的，而且w的左兒子是紅色的，右兒子是黑色的
if w.left.color == RED and w.color == BLACK:
w.left.PAINT(BLACK)
w.PAINT(RED)
self.RIGHT_ROTATE(w)
# case4:x的兄弟w是黑色的，而且w的右兒子是紅
if w.right.color == RED:
p.PAINT(BLACK)
w.PAINT(RED)
if w == p.right:
self.LEFT_ROTATE(p)
else:
self.RIGHT_ROTATE(p)
def SHOW(self):
self.DISPLAY1(self.root)
return self.zlist
def DISPLAY1(self, node):
if node is None:
return
self.DISPLAY1(node.left)
self.zlist.append(node.val)
self.DISPLAY1(node.right)
def DISPLAY2(self, node):
if node is None:
return
self.DISPLAY2(node.left)
print node.val,
self.DISPLAY2(node.right)
def DISPLAY3(self, node):
if node is None:
return
self.DISPLAY3(node.left)
self.DISPLAY3(node.right)
print node.val,
class RBTnode:
'''紅黑樹的節點類型'''
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
def PAINT(self, color):
self.color = color
def zuoxuan(b, c):
a = b.parent
a.left = c
c.parent = a
b.parent = c
c.left = b
if __name__ == '__main__':
rbt=RBT()
b = []
for i in range(100):
m = randint(0, 500)
rbt.INSERT(m)
b.append(m)
a = rbt.SHOW()
b.sort()
equal = True
for i in range(100):
if a[i] != b[i]:
equal = False
break
if not equal:
print 'wrong'
else:
print 'OK!'
PS:這篇文章剛寫好的時候，代碼中是有錯誤的，而且DELETE_FIXUP()也沒有給出；分析中也有小錯誤。不過現在已經改正了，代碼中通過隨機生成的數字，用系統的排序和我寫的紅黑樹的排序對比，發現是結果是一樣的，所以可以認為前面的算法分析是正確的。不過，速度上其實還是有點慢的，比如我用紅黑樹去排序，用在一道codeforces的題目中取代系統的sort，結果就會超時。
文章列表
留言列表
