python实现avl树
时间: 2023-07-07 19:06:56 浏览: 35
下面是一个简单的 Python 实现 AVL 树的例子:
```python
# AVL Tree Implementation in Python
# Create Node Class
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
# Create AVL Tree Class
class AVLTree:
# Insert Function
def insert(self, root, key):
# Step 1 - Perform normal BST
if not root:
return AVLNode(key)
elif key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
# Step 2 - Update the height of the ancestor node
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
# Step 3 - Get the balance factor
balance = self.getBalance(root)
# Step 4 - If the node is unbalanced, then try out the 4 cases
# Case 1 - Left Left
if balance > 1 and key < root.left.key:
return self.rightRotate(root)
# Case 2 - Right Right
if balance < -1 and key > root.right.key:
return self.leftRotate(root)
# Case 3 - Left Right
if balance > 1 and key > root.left.key:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
# Case 4 - Right Left
if balance < -1 and key < root.right.key:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
# Delete Function
def delete(self, root, key):
# Step 1 - Perform standard BST delete
if not root:
return root
elif key < root.key:
root.left = self.delete(root.left, key)
elif key > root.key:
root.right = self.delete(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.getMinValueNode(root.right)
root.key = temp.key
root.right = self.delete(root.right, temp.key)
# If the tree has only one node, then return
if root is None:
return root
# Step 2 - Update the height of the ancestor node
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
# Step 3 - Get the balance factor
balance = self.getBalance(root)
# Step 4 - If the node is unbalanced, then try out the 4 cases
# Case 1 - Left Left
if balance > 1 and self.getBalance(root.left) >= 0:
return self.rightRotate(root)
# Case 2 - Right Right
if balance < -1 and self.getBalance(root.right) <= 0:
return self.leftRotate(root)
# Case 3 - Left Right
if balance > 1 and self.getBalance(root.left) < 0:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
# Case 4 - Right Left
if balance < -1 and self.getBalance(root.right) > 0:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
# Get Minimum Value Node
def getMinValueNode(self, root):
if root is None or root.left is None:
return root
return self.getMinValueNode(root.left)
# Left Rotation Function
def leftRotate(self, z):
y = z.right
T2 = y.left
# Perform Rotation
y.left = z
z.right = T2
# Update Heights
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
# Return the new root
return y
# Right Rotation Function
def rightRotate(self, z):
y = z.left
T3 = y.right
# Perform Rotation
y.right = z
z.left = T3
# Update Heights
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
# Return the new root
return y
# Get Height Function
def getHeight(self, root):
if not root:
return 0
return root.height
# Get Balance Function
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
# Print Function
def printPreOrder(self, root):
if not root:
return
print("{0} ".format(root.key), end="")
self.printPreOrder(root.left)
self.printPreOrder(root.right)
```
这是一个基本的实现,可以用来插入、删除和打印 AVL 树。