AVL树python代码
时间: 2023-10-13 18:54:11 浏览: 45
以下是一个简单的AVL树的Python实现代码示例:
```python
# 定义AVL树节点类
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
# AVL树类
class AVLTree:
def __init__(self):
self.root = None
# 获取节点的高度
def get_height(self, node):
if node is None:
return 0
return node.height
# 获取节点的平衡因子
def get_balance(self, node):
if node is None:
return 0
return self.get_height(node.left) - self.get_height(node.right)
# 更新节点的高度
def update_height(self, node):
if node is None:
return
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
# 执行左旋转操作
def left_rotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
self.update_height(z)
self.update_height(y)
return y
# 执行右旋转操作
def right_rotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
self.update_height(z)
self.update_height(y)
return y
# 插入节点
def insert(self, key):
self.root = self._insert(self.root, key)
def _insert(self, root, key):
if root is None:
return AVLNode(key)
elif key < root.key:
root.left = self._insert(root.left, key)
else:
root.right = self._insert(root.right, key)
self.update_height(root)
balance = self.get_balance(root)
# 左旋
if balance > 1 and key < root.left.key:
return self.right_rotate(root)
# 右旋
if balance < -1 and key > root.right.key:
return self.left_rotate(root)
# 左右旋
if balance > 1 and key > root.left.key:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# 右左旋
if balance < -1 and key < root.right.key:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
# 中序遍历
def inorder_traversal(self):
self._inorder_traversal(self.root)
def _inorder_traversal(self, root):
if root:
self._inorder_traversal(root.left)
print(root.key, end=" ")
self._inorder_traversal(root.right)
```
这只是一个简单的AVL树实现,还可以根据需要进一步完善和扩展。