python代碼實(shí)現(xiàn)AVL樹和紅黑樹
AVL樹
AVL樹是一種自平衡二叉搜索樹。在這種樹中，任何節(jié)點(diǎn)的兩個(gè)子樹的高度差被嚴(yán)格控制在1以內(nèi)。這確保了樹的平衡，從而保證了搜索、插入和刪除操作的高效性。AVL樹是由Georgy Adelson-Velsky和Evgenii Landis在1962年發(fā)明的，因此得名（Adelson-Velsky和Landis樹）。
平衡因子：每個(gè)節(jié)點(diǎn)的平衡因子是其左子樹的高度減去其右子樹的高度。平衡因子必須保持在-1、0或1之間。
旋轉(zhuǎn)操作：為了維持平衡，在進(jìn)行插入或刪除操作后，可能會(huì)執(zhí)行單旋轉(zhuǎn)或雙旋轉(zhuǎn)。單旋轉(zhuǎn)包括右旋（針對(duì)左重失衡）和左旋（針對(duì)右重失衡）。雙旋轉(zhuǎn)是一種更復(fù)雜的調(diào)整，包括左-右旋轉(zhuǎn)和右-左旋轉(zhuǎn)。
時(shí)間復(fù)雜度：在AVL樹中，查找、插入和刪除操作的時(shí)間復(fù)雜度均為O(log n)，其中n是樹中的節(jié)點(diǎn)數(shù)。
AVL樹節(jié)點(diǎn)定義
class AVLNode:
def __init__(self, key):
self.key = key
self.height = 1
self.left = None
self.right = None這里定義了一個(gè)AVL樹的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)有一個(gè)鍵值key，一個(gè)高度屬性height，以及指向左右子節(jié)點(diǎn)的指針left和right。
AVL樹的高度和平衡因子
AVL樹的關(guān)鍵是保持每個(gè)節(jié)點(diǎn)的平衡。平衡因子被定義為節(jié)點(diǎn)的左子樹高度減去其右子樹高度。這個(gè)因子應(yīng)該是-1、0或1。如果在任何時(shí)候，一個(gè)節(jié)點(diǎn)的平衡因子不在這個(gè)范圍內(nèi)，我們需要通過旋轉(zhuǎn)來重新平衡樹。
def get_height(node):
if not node:
return 0
return node.height
def get_balance(node):
if not node:
return 0
return get_height(node.left) - get_height(node.right)這兩個(gè)函數(shù)幫助我們計(jì)算任何節(jié)點(diǎn)的高度和平衡因子。
AVL樹旋轉(zhuǎn)操作
為了維持平衡，我們可能需要進(jìn)行樹的旋轉(zhuǎn)操作。主要有四種類型的旋轉(zhuǎn)：右旋轉(zhuǎn)、左旋轉(zhuǎn)、左-右旋轉(zhuǎn)和右-左旋轉(zhuǎn)。
右旋轉(zhuǎn)：
當(dāng)一個(gè)節(jié)點(diǎn)的左子樹比右子樹高時(shí)，我們進(jìn)行右旋轉(zhuǎn)。
def rotate_right(z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(get_height(z.left), get_height(z.right))
y.height = 1 + max(get_height(y.left), get_height(y.right))
return y左旋轉(zhuǎn)：
當(dāng)一個(gè)節(jié)點(diǎn)的右子樹比左子樹高時(shí)，我們進(jìn)行左旋轉(zhuǎn)。
def rotate_left(z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(get_height(z.left), get_height(z.right))
y.height = 1 + max(get_height(y.left), get_height(y.right))
return y左-右旋轉(zhuǎn)和右-左旋轉(zhuǎn)：
這些是雙旋轉(zhuǎn)操作，先進(jìn)行一次旋轉(zhuǎn)使其成為第一種或第二種情況，然后再進(jìn)行相應(yīng)的旋轉(zhuǎn)。
AVL樹插入操作
插入操作類似于普通的二叉搜索樹插入，但是在插入后，我們需要更新祖先節(jié)點(diǎn)的高度，并檢查每個(gè)節(jié)點(diǎn)的平衡因子，以確保樹保持平衡。
def insert(node, key):
if not node:
return AVLNode(key)
elif key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
node.height = 1 + max(get_height(node.left), get_height(node.right))
balance = get_balance(node)
if balance > 1 and key < node.left.key:
return rotate_right(node)
if balance < -1 and key > node.right.key:
return rotate_left(node)
if balance > 1 and key > node.left.key:
node.left = rotate_left(node.left)
return rotate_right(node)
if balance < -1 and key < node.right.key:
node.right = rotate_right(node.right)
return rotate_left(node)
return nodeAVL樹刪除操作
刪除操作也與普通的二叉搜索樹類似，但在刪除節(jié)點(diǎn)后，我們需要更新祖先節(jié)點(diǎn)的高度，并檢查每個(gè)節(jié)點(diǎn)的平衡因子以重新平衡樹。
def min_value_node(node):
current = node
while current.left is not None:
current = current.left
return current
def delete(node, key):
if not node:
return node
if key < node.key:
node.left = delete(node.left, key)
elif key > node.key:
node.right = delete(node.right, key)
else:
if node.left is None:
temp = node.right
node = None
return temp
elif node.right is None:
temp = node.left
node = None
return temp
temp = min_value_node(node.right)
node.key = temp.key
node.right = delete(node.right, temp.key)
if node is None:
return node
node.height = 1 + max(get_height(node.left), get_height(node.right))
balance = get_balance(node)
if balance > 1 and get_balance(node.left) >= 0:
return rotate_right(node)
if balance < -1 and get_balance(node.right) <= 0:
return rotate_left(node)
if balance > 1 and get_balance(node.left) < 0:
node.left = rotate_left(node.left)
return rotate_right(node)
if balance < -1 and get_balance(node.right) > 0:
node.right = rotate_right(node.right)
return rotate_left(node)
return node這個(gè)刪除函數(shù)處理了三種情況：要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)、一個(gè)子節(jié)點(diǎn)或沒有子節(jié)點(diǎn)。在刪除節(jié)點(diǎn)后，它會(huì)通過旋轉(zhuǎn)操作確保樹保持平衡。
使用AVL樹
現(xiàn)在我們可以創(chuàng)建一個(gè)AVL樹的實(shí)例，并進(jìn)行插入和刪除操作：
avl_tree = None
keys = [20, 4, 15, 70, 50, 80, 100]
for key in keys:
avl_tree = insert(avl_tree, key)
avl_tree = delete(avl_tree, 70)在這個(gè)例子中，我們插入了一些數(shù)字，然后刪除了一個(gè)。
紅黑樹
紅黑樹是另一種自平衡二叉搜索樹，它通過確保樹從根到葉子的最長(zhǎng)可能路徑不超過最短可能路徑的兩倍來維持大致的平衡。
紅黑樹的節(jié)點(diǎn)有兩種顏色：紅色或黑色。這種樹遵循以下重要屬性：
顏色屬性：每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。
根屬性：樹的根總是黑色。
葉子屬性：所有葉子（NIL節(jié)點(diǎn)）都是黑色。
紅色節(jié)點(diǎn)屬性：如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的兩個(gè)子節(jié)點(diǎn)都是黑色的。
路徑屬性：從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)。
紅黑樹通過旋轉(zhuǎn)和重新著色來維持這些屬性。雖然紅黑樹的平衡性不如AVL樹，但它在插入和刪除操作中需要更少的旋轉(zhuǎn)，這使得它在某些類型的應(yīng)用中更高效。
紅黑樹節(jié)點(diǎn)定義：
class RedBlackNode:
def __init__(self, key, color="red"):
self.key = key
self.color = color
self.left = None
self.right = None
self.parent = None這里定義了一個(gè)紅黑樹的節(jié)點(diǎn)。除了常規(guī)的key外，節(jié)點(diǎn)還包含一個(gè)color屬性以及指向父節(jié)點(diǎn)和子節(jié)點(diǎn)的鏈接。
紅黑樹旋轉(zhuǎn)操作：
為了維持紅黑樹的特性，在插入和刪除節(jié)點(diǎn)時(shí)可能需要進(jìn)行樹的旋轉(zhuǎn)操作。主要有兩種類型的旋轉(zhuǎn)：左旋和右旋。
左旋：
當(dāng)一個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)是紅色而左子節(jié)點(diǎn)是黑色時(shí)進(jìn)行。
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右旋：
當(dāng)一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)是紅色而左子節(jié)點(diǎn)的左子節(jié)點(diǎn)也是紅色時(shí)進(jìn)行。
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紅黑樹插入操作：
插入操作首先類似于普通的二叉搜索樹插入。但在插入一個(gè)節(jié)點(diǎn)后，可能需要進(jìn)行多次顏色更改和旋轉(zhuǎn)來修復(fù)可能違反的紅黑樹性質(zhì)。
def insert(self, key):
node = RedBlackNode(key)
node.parent = None
node.key = key
node.left = self.TNULL
node.right = self.TNULL
node.color = 1 # 新節(jié)點(diǎn)必須是紅色
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.fix_insert(node)在插入節(jié)點(diǎn)后，fix_insert函數(shù)被調(diào)用以重新平衡樹，確保樹仍然是一個(gè)有效的紅黑樹。
紅黑樹刪除操作：
刪除操作比插入操作更復(fù)雜。刪除節(jié)點(diǎn)后，可能需要進(jìn)行多次顏色更改和旋轉(zhuǎn)來修復(fù)可能違反的紅黑樹性質(zhì)。
def delete_node(self, node, key):
# 省略具體刪除邏輯
self.fix_delete(x)在刪除節(jié)點(diǎn)后，fix_delete函數(shù)被調(diào)用以重新平衡樹。
使用紅黑樹：
現(xiàn)在我們可以創(chuàng)建一個(gè)紅黑樹的實(shí)例，并進(jìn)行插入和刪除操作：
rbt = RedBlackTree()
numbers = [20, 15, 25, 10, 30, 5, 35]
for number in numbers:
rbt.insert(number)
rbt.delete_node(rbt.root, 15)在這個(gè)例子中，我們插入了一些數(shù)字，然后刪除了一個(gè)。
紅黑樹是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，它通過一系列精心設(shè)計(jì)的規(guī)則和操作來確保樹的平衡。盡管它的實(shí)現(xiàn)比普通的二叉搜索樹復(fù)雜得多，但它在插入、刪除和查找操作上提供了良好的最壞情況性能。這種平衡是通過確保任何路徑上的黑色節(jié)點(diǎn)數(shù)目大致相同來實(shí)現(xiàn)的。紅黑樹廣泛應(yīng)用于計(jì)算機(jī)科學(xué)的許多領(lǐng)域，尤其是在那些需要快速查找操作的場(chǎng)景中，如數(shù)據(jù)庫和文件系統(tǒng)。
實(shí)現(xiàn)紅黑樹要求對(duì)它的性質(zhì)和操作有深入的理解。上述代碼提供了一個(gè)基本的框架，但它并不完整。在實(shí)際應(yīng)用中，您可能還需要處理更多的邊界情況和優(yōu)化。每個(gè)操作背后都有復(fù)雜的邏輯和數(shù)學(xué)原理，這是理解和實(shí)現(xiàn)紅黑樹的關(guān)鍵部分。
到此這篇關(guān)于python代碼實(shí)現(xiàn)AVL樹和紅黑樹的文章就介紹到這了,更多相關(guān)AVL樹和紅黑樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Python實(shí)現(xiàn)自動(dòng)發(fā)送郵件功能
這篇文章主要為大家詳細(xì)介紹了Python實(shí)現(xiàn)自動(dòng)發(fā)送郵件功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-12-12
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)文件的分割與合并，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-08-08
Python數(shù)據(jù)結(jié)構(gòu)之圖的應(yīng)用示例
pygame游戲之旅 計(jì)算游戲中躲過的障礙數(shù)量
如何在Django項(xiàng)目中引入靜態(tài)文件
keras .h5轉(zhuǎn)移動(dòng)端的.tflite文件實(shí)現(xiàn)方式
python爬蟲之爬取百度音樂的實(shí)現(xiàn)方法
在python tkinter中Canvas實(shí)現(xiàn)進(jìn)度條顯示的方法
Boston數(shù)據(jù)集預(yù)測(cè)放假及應(yīng)用優(yōu)缺點(diǎn)評(píng)估