AVL 树与红黑树：平衡树插入的艺术
在数据结构的世界里，平衡树是一种特殊的树形结构，它能够在插入、删除和查找操作中保持平衡，从而保证这些操作的时间复杂度接近于 O(log n)。AVL 树和红黑树是两种著名的平衡树，它们通过不同的方式维护树的平衡。本文将围绕 AVL 树的旋转和红黑树的着色这两个核心概念，探讨平衡树插入的技术细节。
AVL 树：旋转的艺术
AVL 树是一种自平衡的二叉搜索树，它通过在插入和删除操作后进行必要的旋转来保持树的平衡。AVL 树的平衡是通过树的高度差来衡量的，任何节点的左右子树高度之差不超过 1。
AVL 树节点定义
python
class AVLNode:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
self.height = 1 新节点插入时，初始高度为 1
AVL 树插入
AVL 树的插入操作与二叉搜索树的插入操作类似，但在插入后需要检查并可能进行旋转以保持树的平衡。
python
def insert(node, key):
if not node:
return AVLNode(key)
elif key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
node.height = 1 + max(get_height(node.left), get_height(node.right))
balance = get_balance(node)
Left Left Case
if balance > 1 and key < node.left.key:
return right_rotate(node)
Right Right Case
if balance < -1 and key > node.right.key:
return left_rotate(node)
Left Right Case
if balance > 1 and key > node.left.key:
node.left = left_rotate(node.left)
return right_rotate(node)
Right Left Case
if balance < -1 and key < node.right.key:
node.right = right_rotate(node.right)
return left_rotate(node)
return node
def left_rotate(z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(get_height(z.left), get_height(z.right))
y.height = 1 + max(get_height(y.left), get_height(y.right))
return y
def right_rotate(y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(get_height(y.left), get_height(y.right))
x.height = 1 + max(get_height(x.left), get_height(x.right))
return x
def get_height(node):
if not node:
return 0
return node.height
def get_balance(node):
if not node:
return 0
return get_height(node.left) - get_height(node.right)
红黑树：着色的艺术
红黑树是一种自平衡的二叉搜索树，它通过一系列的着色规则来保证树的平衡。红黑树的节点可以是红色或黑色，并且遵循以下规则：
1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 所有叶子节点（NIL 节点）是黑色。
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树节点定义
python
class RBNode:
def __init__(self, key, color='red', left=None, right=None, parent=None):
self.key = key
self.color = color
self.left = left
self.right = right
self.parent = parent
红黑树插入
红黑树的插入操作比 AVL 树复杂，因为它需要处理更多的着色和旋转情况。
python
def insert(root, key):
node = RBNode(key)
node.left = None
node.right = None
node.color = 'red'
parent = None
current = root
while current:
parent = current
if node.key < current.key:
current = current.left
else:
current = current.right
node.parent = parent
if not parent:
root = node
elif node.key < parent.key:
parent.left = node
else:
parent.right = node
fix_insertion(root, node)
def fix_insertion(root, node):
while node != root and node.parent.color == 'red':
if node.parent == node.parent.parent.left:
uncle = node.parent.parent.right
if uncle and uncle.color == 'red':
node.parent.color = 'black'
uncle.color = 'black'
node.parent.parent.color = 'red'
node = node.parent.parent
else:
if node == node.parent.right:
node = node.parent
left_rotate(node)
node.parent.color = 'black'
node.parent.parent.color = 'red'
right_rotate(node.parent.parent)
else:
uncle = node.parent.parent.left
if uncle and uncle.color == 'red':
node.parent.color = 'black'
uncle.color = 'black'
node.parent.parent.color = 'red'
node = node.parent.parent
else:
if node == node.parent.left:
node = node.parent
right_rotate(node)
node.parent.color = 'black'
node.parent.parent.color = 'red'
left_rotate(node.parent.parent)
root.color = 'black'
总结
AVL 树和红黑树都是通过特定的旋转和着色规则来保持树的平衡，从而保证插入、删除和查找操作的高效性。AVL 树通过旋转来保持树的高度差不超过 1，而红黑树通过着色规则来保证从根到叶子的所有路径都包含相同数目的黑色节点。这两种平衡树在数据结构中有着广泛的应用，特别是在需要频繁进行插入和删除操作的场景中。
本文通过代码示例介绍了 AVL 树和红黑树的基本概念和插入操作，希望对读者理解平衡树插入的艺术有所帮助。在实际应用中，平衡树的选择取决于具体的应用场景和性能要求。
Comments NOTHING