要實現一個平衡的樹,通常我們會使用 AVL 樹或紅黑樹。這里我將簡要介紹如何實現一個簡單的 AVL 樹。
AVL 樹是一種自平衡二叉搜索樹,它的每個節點的左子樹和右子樹的高度差不超過 1。為了實現一個 AVL 樹,我們需要定義一個 TreeNode 類,并實現插入、刪除和平衡等操作。
首先,定義一個 TreeNode 類:
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
接下來,實現插入操作。在插入節點時,我們需要更新節點的高度,并檢查樹是否平衡。如果不平衡,我們需要進行相應的旋轉操作來恢復平衡。
class AVLTree:
def insert(self, root, key):
if not root:
return TreeNode(key)
elif key< root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
balance = self.get_balance(root)
# Left Left Case
if balance > 1 and key< root.left.key:
return self.right_rotate(root)
# Right Right Case
if balance < -1 and key > root.right.key:
return self.left_rotate(root)
# Left Right Case
if balance > 1 and key > root.left.key:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# Right Left Case
if balance < -1 and key< root.right.key:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def get_height(self, root):
if not root:
return 0
return root.height
def get_balance(self, root):
if not root:
return 0
return self.get_height(root.left) - self.get_height(root.right)
def left_rotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def right_rotate(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
return x
類似地,你可以實現刪除操作,并在刪除節點時檢查樹是否平衡。如果不平衡,進行相應的旋轉操作來恢復平衡。
注意:這里給出的代碼僅作為實現 AVL 樹的參考,你可能需要根據自己的需求進行調整和優化。