Red-Black Tree
相較於 AVL 樹在每次插入與刪除節點時調整樹至平衡，紅黑樹只有在違反以下條件時才會調整樹至符合條件：
- 每個節點是紅色或黑色。
- 最上層的根節點是黑色。
- 所有葉節點都是黑色的 NIL 節點。
- 每個紅色節點有兩個黑色的子節點。
- 每個節點到它的葉節點的路徑都包含相同數量的黑色節點。
新插入的節點 N 預設是紅色，循環以下六種情況調整樹至符合條件，記得將最上層的根節點設為黑色：
1. N 的父節點 P 為黑，符合條件。
2. N 的父節點 P 與其兄弟節點 U，即 N 的叔父節點 (Uncle Node) 為紅，將 P 與 U 變黑，P 的父節點 G，即 N 的祖父節點 (Grandparent Node) 變紅。
3. N 的父節點 P 為紅、叔父節點 U 為黑或不存在，且 N 為其父節點 P 的左子節點、P 為其父節點 G 的左子節點，將 P 變黑、G 變紅加往右做樹旋轉。
4. N 的父節點 P 為紅、叔父節點 U 為黑或不存在，且 N 為其父節點 P 的右子節點、P 為其父節點 G 的右子節點，將 P 變黑、G 變紅加往左做樹旋轉。
5. N 的父節點 P 為紅、叔父節點 U 為黑或不存在，且 N 為其父節點 P 的右子節點、P 為其父節點 G 的左子節點，將 P 往左做樹旋轉。
6. N 的父節點 P 為紅、叔父節點 U 為黑或不存在，且 N 為其父節點 P 的左子節點、P 為其父節點 G 的右子節點，將 P 往右做樹旋轉。
下面演示插入節點過程，省略葉節點 NIL。插入 10，預設為紅，違反根節點必須為黑，將其設為黑。插入 20，此為情況一，無需任何調整。
插入 30，此為情況四。
將 20 變黑、10 變紅加往左做樹旋轉。
插入 40，此為情況二。
將 30 與 10 變黑、20 變紅。
20 違反根節點必須為黑，將其設為黑。
插入 50，此為情況四。
將 40 變黑、30 變紅加往左做樹旋轉。
插入 60，此為情況二。
將 50 與 30 變黑、40 變紅。
插入 70，此為情況四，將 60 變黑、50 變紅加往左做樹旋轉。插入 80，此為情況二。
將 70 與 50 變黑、60 變紅。60 出現情況四。
將 40 變黑、20 變紅加往左做樹旋轉。整個插入過程符合紅黑樹條件。
刪除節點需要進行移植 (Transplant) 來移動子樹，下面演示移植的三種情況，省略葉節點 NIL：
1. 欲刪除的節點 15 沒有父節點。
將欲取代的節點 19 設為根節點。
將 19 的父節點設為跟 15 的父節點一樣為空。
2. 欲刪除的節點 12 為其父節點 15 的左子節點。
將欲取代的節點 13 設為 15 的左子節點。
將 13 的父節點設為 15。
3. 欲刪除的節點 19 為其父節點 15 的右子節點。
將欲取代的節點 23 設為 15 的右子節點。
將 23 的父節點設為 15。
下面演示刪除節點的過程，以刪除 40 為例，記住其原始顏色為黑色：
宣告一個空節點 x，接下來看 x 會被設為樹中的哪一個節點，它將被用來做刪除後的修正 (Fixup)，也就是把樹調整至符合條件。
如果 40 的左子節點是葉節點 NIL，將 x 設為 40 的右子節點並移植至 40 的位置：
如果 40 的左子節點不是葉節點 NIL，但右子節點是，則將 x 設為 40 的左子節點並移植至 40 的位置。判斷順序就是如此先左再右。
如果「欲刪除的節點」的左右子節點都不是葉節點 NIL，如下圖的節點 2，那用以取代它的節點則為其右子樹中最小的節點 4，記住 4 的原始顏色為黑色，並將 x 設為 4 的右子節點。
如果「欲取代的節點」為「欲刪除的節點」的子節點 (4 為 2 的子節點)，將 x 的父節點設為「欲取代的節點」4。接著，將 4 移植至 2 的位置，並將其顏色設為 4 的原始顏色 (黑色)。如上圖移植後 4 為紅，要將其變黑。
如果「欲取代的節點」不為「欲刪除的節點」的子節點，如下圖中 22 不為 17 的子節點，那先將 22 的右子節點 (葉節點 NIL) 移植至 22 的位置，再將 22 移植至 17 的位置，並將其顏色設為 22 的原始顏色 (紅色)。
以上即為刪除節點的過程，如果欲刪除的節點的原始顏色為黑色，如第一個例子 40，則要將節點 x 傳入修正函式來調整樹至符合條件。我們將 w 設為 x 的兄弟節點，如果 x 為其父節點的左子節點，按以下順序來判斷四種情況：
1. w 為紅。
將「x 的父節點的右子節點」變黑、「x 的父節點」變紅。
將「x 的父節點」往左做樹旋轉。
將 w 設為「x 的父節點的右子節點」。
2. w 的左右子節點皆為黑。
將 w 變紅、x 設為「x 的父節點」。
3. w 的左子節點為紅、右子節點為黑。
將「w 的左子節點」變黑、w 變紅。
將 w 往右做樹旋轉。
將 w 設為「x 的父節點的右子節點」。
4. 都不符合以上情況。
將 w 變跟「x 的父節點」一樣顏色、「x 的祖父節點」變黑、「w 的右子節點」變黑。
將「x 的父節點」往左做樹旋轉。
將 x 設為根節點。
那如果在修正函式的一開始，x 為其父節點的右子節點，則一樣是分以上四種情況，只是調整從右改到左。
在修正函式的最後，跟插入節點一樣，記得將 x 設為黑色。以下為修正函式的流程圖：
用大 O 符號表示的時間複雜度與空間複雜度為：
下面示範用 Python 構造一棵紅黑樹：
class TreeNode():
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
self.color = 1
class RBT():
def __init__(self):
self.TNULL = TreeNode(0)
self.TNULL.color = 0
self.TNULL.left = None
self.TNULL.right = None
self.root = self.TNULL
def get_root(self):
return self.root
def search(self, key):
return self._search(key, self.root)
def _search(self, key, node):
if node == TNULL or key == node.key:
return node
if key < node.key:
return self._search(key, node.left)
return self._search(key, node.right)
def insert(self, key):
node = TreeNode(key)
node.key = key
node.left = self.TNULL
node.right = self.TNULL
node.parent = None
node.color = 1
y = None
x = self.root
while x != self.TNULL:
y = x
if node.key < x.key:
x = x.left
else:
x = x.right
node.parent = y
if y == None:
self.root = node
elif node.key < y.key:
y.left = node
else:
y.right = node
if node.parent == None:
node.color = 0
return
if node.parent.parent == None:
return
self._insert_fixup(node)
def _insert_fixup(self, k):
while k.parent.color == 1:
if k.parent == k.parent.parent.right:
u = k.parent.parent.left
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.left:
k = k.parent
self._rotate_right(k)
k.parent.color = 0
k.parent.parent.color = 1
self._rotate_left(k.parent.parent)
else:
u = k.parent.parent.right
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.right:
k = k.parent
self._rotate_left(k)
k.parent.color = 0
k.parent.parent.color = 1
self._rotate_right(k.parent.parent)
if k == self.root:
break
self.root.color = 0
def delete(self, key):
self._delete(key, self.root)
def _delete(self, key, node):
z = self.TNULL
while node != self.TNULL:
if node.key == key:
z = node
if node.key <= key:
node = node.right
else:
node = node.left
if z == self.TNULL:
print('Cannot find key in the tree')
return
y = z
y_original_color = y.color
if z.left == self.TNULL:
x = z.right
self._transplant(z, z.right)
elif (z.right == self.TNULL):
x = z.left
self._transplant(z, z.left)
else:
y = self._get_min_node(z.right)
y_original_color = y.color
x = y.right
if y.parent == z:
x.parent = y
else:
self._transplant(y, y.right)
y.right = z.right
y.right.parent = y
self._transplant(z, y)
y.left = z.left
y.left.parent = y
y.color = z.color
if y_original_color == 0:
self._delete_fixup(x)
def _delete_fixup(self, x):
while x != self.root and x.color == 0:
if x == x.parent.left:
s = x.parent.right
if s.color == 1:
s.color = 0
x.parent.color = 1
self._rotate_left(x.parent)
s = x.parent.right
if s.left.color == 0 and s.right.color == 0:
s.color = 1
x = x.parent
else:
if s.right.color == 0:
s.left.color = 0
s.color = 1
self._rotate_right(s)
s = x.parent.right
s.color = x.parent.color
x.parent.color = 0
s.right.color = 0
self._rotate_left(x.parent)
x = self.root
else:
s = x.parent.left
if s.color == 1:
s.color = 0
x.parent.color = 1
self._rotate_right(x.parent)
s = x.parent.left
if s.right.color == 0 and s.left.color == 0:
s.color = 1
x = x.parent
else:
if s.left.color == 0:
s.right.color = 0
s.color = 1
self._rotate_left(s)
s = x.parent.left
s.color = x.parent.color
x.parent.color = 0
s.left.color = 0
self._rotate_right(x.parent)
x = self.root
x.color = 0
def _transplant(self, u, v):
if u.parent == None:
self.root = v
elif u == u.parent.left:
u.parent.left = v
else:
u.parent.right = v
v.parent = u.parent
def _get_min_node(self, node):
while node.left != self.TNULL:
node = node.left
return node
def _get_max_node(self, node):
while node.right != self.TNULL:
node = node.right
return node
def _rotate_left(self, x):
y = x.right
x.right = y.left
if y.left != self.TNULL:
y.left.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def _rotate_right(self, x):
y = x.left
x.left = y.right
if y.right != self.TNULL:
y.right.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
def print_tree(self):
self._print_tree(self.root, '', True)
print()
def _print_tree(self, node, indent, last):
if node != self.TNULL:
print(indent, end='')
if last:
print('R----', end='')
indent += ' '
else:
print('L----', end='')
indent += '| '
s_color = 'RED' if node.color == 1 else 'BLACK'
print(str(node.key) + '(' + s_color + ')')
self._print_tree(node.left, indent, False)
self._print_tree(node.right, indent, True)
def traverse_preorder(self):
self._traverse_preorder(self.root)
print()
def _traverse_preorder(self, node):
if node != TNULL:
print(node.key, end=' ')
self._traverse_preorder(node.left)
self._traverse_preorder(node.right)
def traverse_inorder(self):
self._traverse_inorder(self.root)
print()
def _traverse_inorder(self, node):
if node != TNULL:
self._traverse_inorder(node.left)
print(node.key, end=' ')
self._traverse_inorder(node.right)
def traverse_postorder(self):
self._traverse_postorder(self.root)
print()
def _traverse_postorder(self, node):
if node != TNULL:
self._traverse_postorder(node.left)
self._traverse_postorder(node.right)
print(node.key, end=' ')
def _get_successor(self, x):
if x.right != self.TNULL:
return self._get_min_node(x.right)
y = x.parent
while y != self.TNULL and x == y.right:
x = y
y = y.parent
return y
def _get_predecessor(self, x):
if (x.left != self.TNULL):
return self._get_max_node(x.left)
y = x.parent
while y != self.TNULL and x == y.left:
x = y
y = y.parent
return y測試插入與刪除節點功能：
rbt = RBT()
rbt.insert(55)
rbt.insert(40)
rbt.insert(65)
rbt.insert(60)
rbt.insert(75)
rbt.insert(57)
rbt.print_tree()
print('After deleting a node:\n')
rbt.delete(40)
rbt.print_tree()輸出結果如下：
R----55(BLACK)
L----40(BLACK)
R----65(RED)
L----60(BLACK)
| L----57(RED)
R----75(BLACK)
After deleting a node:
R----65(BLACK)
L----57(RED)
| L----55(BLACK)
| R----60(BLACK)
R----75(BLACK)參考資料
https://clu.gitbook.io/data-structure-note/1.4.1.1-rb-tree-insert
https://josephjsf2.github.io/data/structure/and/algorithm/2020/04/28/red-black-tree-part-1.html
https://josephjsf2.github.io/data/structure/and/algorithm/2020/04/28/red-black-tree-part-2.html
https://www.programiz.com/dsa/deletion-from-a-red-black-tree
