在Python中实现树的平衡可以通过实现平衡二叉树(AVL树)来实现。AVL树是一种自平衡二叉搜索树,即树的每个节点的左子树和右子树的高度差不超过1。
下面是一个简单的Python实现:
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def getHeight(self, node):
if not node:
return 0
return node.height
def getBalance(self, node):
if not node:
return 0
return self.getHeight(node.left) - self.getHeight(node.right)
def rotateRight(self, y):
x = y.left
T = x.right
x.right = y
y.left = T
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
x.height = 1 + max(self.getHeight(x.left), self.getHeight(x.right))
return x
def rotateLeft(self, x):
y = x.right
T = y.left
y.left = x
x.right = T
x.height = 1 + max(self.getHeight(x.left), self.getHeight(x.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
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.getHeight(root.left), self.getHeight(root.right))
balance = self.getBalance(root)
if balance > 1 and key < root.left.key:
return self.rotateRight(root)
if balance < -1 and key > root.right.key:
return self.rotateLeft(root)
if balance > 1 and key > root.left.key:
root.left = self.rotateLeft(root.left)
return self.rotateRight(root)
if balance < -1 and key < root.right.key:
root.right = self.rotateRight(root.right)
return self.rotateLeft(root)
return root
使用上述代码可以创建一个AVL树,然后通过调用insert
方法向树中插入新节点,保持树的平衡。