紅黑樹的介紹與Python代碼實現

紅黑樹的介紹

• 紅黑樹(Red-Black Tree)是一種平衡二叉查找樹，它是一種以比較簡單的方式實現的2-3查找樹

紅黑樹基于2-3查找樹的表現

• 紅鏈接:將兩個2-結點連接起來構成一個3-結點 ;
• 黑鏈接:則是2-3樹中的普通鏈接。
  

紅黑樹的定義：
紅黑樹是含有紅黑鏈接并滿足下列條件的二叉查找樹: .

紅鏈接均為左鏈接;

沒有任何一個結點同時和兩條紅鏈接相連;

該樹是完美色平衡的,即任意空鏈接到根結點的路徑上的黑鏈接數量相同;

紅黑樹的優點：

• 一顆二叉樹，每一個結點只需要額外多一位空間即可實現紅黑樹，這一位空間通常用于存放和表示紅黑結點，而這些紅黑標識則可以用來使紅黑樹保持接近平衡的狀態
• 記錄每一個結點的紅黑狀態，只需要額外的一位空間，這使得紅黑樹的儲存空間大小在一定程度上可以認為和無顏色標記的二叉樹的儲存空間大小等同，在大多數情況下，無需額外的儲存成本就能儲存著一位的紅黑記錄信息
• 紅黑樹不是完美的平衡二叉樹，但是它的平衡狀態足夠讓我們能很方便地進行搜尋操作，紅黑樹的查詢、插入、刪除操作時間復雜度都是O(log n)

紅黑樹的平衡化

為什么需要平衡化？

• 在對紅黑樹進行一些增刪改查的操作后 ,很有可能會出現紅色的右鏈接或者兩條連續紅色的鏈接,而這些都不滿足紅黑樹的定義,所以我們需要對這些情況通過旋轉進行修復,讓紅黑樹保持平衡。

平衡化的方法

左旋

右旋

左旋

時機：

• 當某個結點的左子結點為黑色,右子結點為紅色,此時需要左旋。

實現方式：

• 當前節點為h，它的右節點是x；
  color的值是由父結點指過來的線的顏色
  

實現過程：

右旋

時機：

• 當某個結點的左子結點是紅色，并且左子結點的左子結點也是紅色,要右旋

實現方式

• 前提:當前結點為h ,它的左子結點為x ;
  color的值由父結點指過來的線的顏色
  
  實現過程：
  
  右旋之后保持了有序性；但是紅鏈接連接了三個結點不滿足2-3樹的性質，同時違背了紅黑樹右鏈接不能為紅鏈接的要求，這個問題下面將會介紹使用顏色反轉的方法來解決

平衡步驟

向單個2-結點中插入新鍵后，結果是插入到該結點的右子結點，則需要進行左旋：

將c結點替換b（使b=c），b的顏色變為紅，然后讓b稱為c的左子節點即可完成左旋（根結點的顏色后面會有一個操作讓其始終保持黑色）

向底部的2-結點插入新鍵

情況同一，只是需要多一步，左旋之后，C的顏色要變為黑色（表示指向C的邊為紅色）

顏色反轉

當一個結點的左子結點和右子結點的color都為RED時, 也就是出現了臨時的4-結點,此時只需要把左子結點和右子結點的顏色變為BLACK ,同時讓當前結點的顏色變為RED即可。

向一棵雙鍵樹(即一個3-結點)中插入新鍵
可分為三種子情況
4-1. 新鍵大于原樹中的兩個鍵：

4-2. 新鍵小于原樹中的兩個鍵

4-3. 新鍵介于原數中兩個鍵之間

根結點的顏色總是黑色
在每次放入元素的操作完成之后，將根結點的顏色變更為’Black’即可：
self.root.color = 'Black'

向樹底部的3-結點插入新鍵

操作方法

is_red(node) 判斷傳入的結點node是否為紅色

rotate_left(node) 將傳入的結點進行左旋操作

rotate_right(node) 將傳入的結點進行右旋操作

alter_color(node) 將傳入的結點進行顏色反轉操作

put(key, val) 插入一個鍵為key，值為val的元素，插入之后自動按鍵進行排序

get_value(key) 根據傳入的鍵key，獲取對應結點的值

Python代碼實現

二叉樹結點設計

class Node:def __init__(self, key, value):self.key = keyself.value = valueself.left = Noneself.right = Noneself.color = False

功能實現

class RedBlackTree:def __init__(self):self.root = Noneself.N = 0def size(self):return self.Ndef is_red(self, node):return str(node.color).lower() == 'red' if node else Falsedef rotate_left(self, node):"""Rotate left when the edge from the current node to its right child node is red"""# h is the current nodeh = node# x is the current node's right childx = node.righth.right = x.leftx.left = hx.color = h.colorh.color = 'Red'return xdef rotate_right(self, node):"""Rotate right when both the left edge and the left child's left edge are red"""h = nodex = node.lefth.left = x.rightx.right = hx.color = h.colorh.color = 'Red'return xdef alter_color(self, node):"""Alter a node's color"""node.color = 'Red'node.left.color = 'Black'node.right.color = 'Black'def put(self, key, val):"""Put an element into this tree"""def put_into(node, key, val):if not node:return Node(key, val)# Rank the orderif key < node.key: # Recursively to compare key with its left childnode.left = put_into(node.left, key, val)elif key > node.key:node.right = put_into(node.right, key, val)else: # Swap their the node.value with valnode.value = valreturn node# Rotation or alter colorif self.is_red(node.right) and not self.is_red(node.left):# Rotate leftself.rotate_left(node)if self.is_red(node.left) and self.is_red(node.left.left):# Rotate rightself.rotate_right(node)if self.is_red(node.left) and self.is_red(node.right):# Alter colorself.alter_color(node)self.N += 1return nodeself.root = put_into(self.root, key, val)self.root.color = 'Black'return self.rootdef get(self, key):"""Get a value according to the given key"""def get_value(node, key):if not node:returnif key < node.key:return get_value(node.left, key)elif key > node.key:return get_value(node.right, key)else:return node.valueval = get_value(self.root, key)return val

代碼測試

if __name__ == '__main__':RBT = RedBlackTree()RBT.put(1, 'G')RBT.put(2, 'K')RBT.put(3, 'd')RBT.put(3, 'D')for i in range(1, 4):print(RBT.get(i), end=' ')print('\n', RBT.size())print(RBT.root.color)print(RBT.root.key, RBT.root.value)print(RBT.root.right.key, RBT.root.right.value)print(RBT.root.right.right.key, RBT.root.right.right.value)

測試結果

G K D 5 Black 1 G 2 K 3 D

插入的元素都按照對應的鍵獲取到了，說明代碼沒有什么問題

總結

以上是生活随笔為你收集整理的数据结构之平衡树：红黑树的介绍与Python代码实现——17的全部內容，希望文章能夠幫你解決所遇到的問題。

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