3 平衡二叉树之平衡二叉树的旋转操作
在上一篇文章中，我们探讨了平衡二叉树的红黑树特性与应用。红黑树是一种自平衡的二叉搜索树，通过定义节点的颜色和一系列规则来保持树的平衡性。接下来，我们将深入了解平衡二叉树的旋转操作，旋转操作是保持树平衡的核心技术之一。
平衡二叉树（AVL树）的旋转操作
AVL树是一种自平衡的二叉搜索树，它通过旋转操作保持树的高度平衡。所谓的旋转操作，主要有以下几种类型：
- 单右旋转
- 单左旋转
- 双右左旋转
- 双左右旋转
1. 单右旋转
单右旋转用于处理左子树的插入导致的不平衡情况，尤其是当左子树的左子树高度较高时。
示例
考虑以下插入序列：30, 20, 10，当插入10后，就会产生不平衡。
30
/
20
/
10
为了恢复平衡，我们进行单右旋转：
20
/ \
10 30
2. 单左旋转
单左旋转用于处理右子树的插入导致的不平衡情况，尤其是当右子树的右子树高度较高时。
示例
考虑插入序列：10, 20, 30，插入30后，树结构变为：
10
\
20
\
30
进行单左旋转后，我们得到平衡的树：
20
/ \
10 30
3. 双右左旋转
双右左旋转是一种组合操作，用于处理左子树的右子树导致的不平衡。
示例
考虑插入序列：30, 10, 20，插入20后，树结构为：
30
/
10
\
20
我们对30节点执行双右左旋转，首先进行左旋转再右旋转，最终得到：
20
/ \
10 30
4. 双左右旋转
双左右旋转则是用于处理右子树的左子树导致的不平衡。
示例
考虑插入序列：10, 30, 20，插入20后，树结构如下：
10
\
30
/
20
进行双左右旋转后，同样首先进行右旋转再左旋转，最终得到平衡的树：
20
/ \
10 30
实现旋转操作
下面是用Python实现AVL树的简单旋转操作代码示例。我们将定义AVLTreeNode类，包含旋转操作的方法。
class AVLTreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def right_rotate(y):
x = y.left
T2 = x.right
# 进行右旋转
x.right = y
y.left = T2
# 更新高度
y.height = max(height(y.left), height(y.right)) + 1
x.height = max(height(x.left), height(x.right)) + 1
return x
def left_rotate(x):
y = x.right
T2 = y.left
# 进行左旋转
y.left = x
x.right = T2
# 更新高度
x.height = max(height(x.left), height(x.right)) + 1
y.height = max(height(y.left), height(y.right)) + 1
return y
def height(node):
if not node:
return 0
return node.height
总结
平衡二叉树的旋转操作是实现自平衡的核心，通过单旋转和双旋转来恢复树的平衡。在AVL树这类数据结构中，旋转操作至关重要，因为它们能够保证在插入或删除操作后，树的高度始终保持在对数级别，确保了操作的高效率。
下一篇文章中，我们将转向图的高级算法，具体介绍图的表示方法，帮助我们更好地处理复杂的数据结构。请继续关注！
