python 代码编写 AVLTree 添加元素
时间: 2024-08-14 22:08:30 浏览: 30
在Python中,AVL树是一种自平衡二叉搜索树,其每个节点的高度最多比它的两个子节点高1。添加元素到AVL树的过程通常包括插入操作,并同时保持树的平衡。以下是插入元素的基本步骤:
```python
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def insert(self, root, key):
# Standard BST insertion
if not root:
return Node(key)
elif key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
# Update height of the current node
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
# Check balance factor and rotate if necessary
balance = self.getBalance(root)
# 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
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
# Rotation functions (not shown here for brevity but essential for maintaining AVL property)
def rightRotate(self, z):
# Details about right rotation would go here
pass
def leftRotate(self, y):
# Details about left rotation would go here
pass
```
在这个例子中,`insert`函数递归地查找合适的插入位置,并根据旋转规则调整树结构以保持平衡。`getHeight`和`getBalance`用于计算节点高度和判断是否需要旋转。`rightRotate`和`leftRotate`是实际的旋转操作,它们会改变节点的连接关系并更新节点的高度。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)