AVL 树是一种自平衡二叉搜索树，它的插入和删除操作的时间复杂度都是 O(log n)。AVL 树的高度始终保持在 O(log n) 级别，因此它是一种高效的数据结构。
AVL 树的基本原理是，它的每个节点都有一个平衡因子，表示该节点的左子树和右子树的高度差。插入和删除操作会改变节点的平衡因子，因此需要通过旋转操作来重新平衡树。
使用 AVL 树时，需要提供以下几个方法:
- 插入节点：将一个节点插入到 AVL 树中，并返回插入后的树。
- 删除节点：将一个节点从 AVL 树中删除，并返回删除后的树。
- 旋转操作：将一个节点旋转以重新平衡树。
- 获取平衡因子：获取一个节点的平衡因子。
- 更新平衡因子：更新一个节点的平衡因子。
在插入和删除节点时，需要先比较当前节点的平衡因子，如果平衡因子大于 1 或小于 -1，则需要进行旋转操作来重新平衡树。
下面是一个简单的 AVL 树的实现:
class Node:
def init(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
self.balance_factor = 0
class AVLTree:
def init(self):
self.root = None
def insert(self, key):
if not self.root:
self.root = Node(key)
else:
self.root = self._insert(self.root, key)
return self
def _insert(self, node, key):
if not node:
return Node(key)
if 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._get_balance_factor(node)
if balance > 1:
if key < node.left.key:
return self._rotate_right(node)
else:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
if balance < -1:
if key > node.right.key:
return self._rotate_left(node)
else:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node
def delete(self, key):
if self.root:
self.root = self._delete(self.root, key)
return self
def _delete(self, node, key):
if not node:
return node
if 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:
return node.right
if not node.right:
return node.left
temp = self._find_min_value_node(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._get_balance_factor(node)
if balance > 1:
if self._get_balance_factor(node.left) < 0:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
if balance < -1:
if self._get_balance_factor(node.right) > 0:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node
def _rotate_left(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
