数据结构二叉查找树AVL
时间: 2023-12-21 08:30:03 浏览: 32
AVL树是一种自平衡二叉查找树,它的每个节点都保存了一个平衡因子(balance factor),用于判断是否需要进行旋转操作来保持树的平衡。AVL树的平衡因子可以是-1、0或1,当插入或删除节点后,如果某个节点的平衡因子的绝对值大于1,则需要进行旋转操作来保持树的平衡。AVL树的查找、插入和删除操作的时间复杂度都是O(log n)。
以下是一个简单的Python实现AVL树的例子:
```python
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self):
self.root = None
def insert(self, key):
self.root = self._insert(self.root, key)
def _insert(self, node, key):
if not node:
return AVLNode(key)
elif key < node.key:
node.left = self._insert(node.left, key)
else:
node.right = self._insert(node.right, key)
node.height = 1 + max(self._height(node.left), self._height(node.right))
balance = self._balance(node)
if balance > 1 and key < node.left.key:
return self._right_rotate(node)
if balance < -1 and key > node.right.key:
return self._left_rotate(node)
if balance > 1 and key > node.left.key:
node.left = self._left_rotate(node.left)
return self._right_rotate(node)
if balance < -1 and key < node.right.key:
node.right = self._right_rotate(node.right)
return self._left_rotate(node)
return node
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if not node:
return node
elif key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
else:
if not node.left and not node.right:
node = None
elif not node.left:
node = node.right
elif not node.right:
node = node.left
else:
temp = self._get_min(node.right)
node.key = temp.key
node.right = self._delete(node.right, temp.key)
if not node:
return node
node.height = 1 + max(self._height(node.left), self._height(node.right))
balance = self._balance(node)
if balance > 1 and self._balance(node.left) >= 0:
return self._right_rotate(node)
if balance < -1 and self._balance(node.right) <= 0:
return self._left_rotate(node)
if balance > 1 and self._balance(node.left) < 0:
node.left = self._left_rotate(node.left)
return self._right_rotate(node)
if balance < -1 and self._balance(node.right) > 0:
node.right = self._right_rotate(node.right)
return self._left_rotate(node)
return node
def _height(self, node):
if not node:
return 0
return node.height
def _balance(self, node):
if not node:
return 0
return self._height(node.left) - self._height(node.right)
def _left_rotate(self, node):
new_root = node.right
node.right = new_root.left
new_root.left = node
node.height = 1 + max(self._height(node.left), self._height(node.right))
new_root.height = 1 + max(self._height(new_root.left), self._height(new_root.right))
return new_root
def _right_rotate(self, node):
new_root = node.left
node.left = new_root.right
new_root.right = node
node.height = 1 + max(self._height(node.left), self._height(node.right))
new_root.height = 1 + max(self._height(new_root.left), self._height(new_root.right))
return new_root
def _get_min(self, node):
if not node.left:
return node
return self._get_min(node.left)
def inorder_traversal(self):
self._inorder_traversal(self.root)
def _inorder_traversal(self, node):
if node:
self._inorder_traversal(node.left)
print(node.key)
self._inorder_traversal(node.right)
tree = AVLTree()
tree.insert(10)
tree.insert(20)
tree.insert(30)
tree.insert(40)
tree.insert(50)
tree.insert(25)
tree.delete(30)
tree.inorder_traversal()
```