3 平衡二叉树之平衡二叉树的旋转操作

在上一篇文章中，我们探讨了平衡二叉树的红黑树特性与应用。红黑树是一种自平衡的二叉搜索树，通过定义节点的颜色和一系列规则来保持树的平衡性。接下来，我们将深入了解平衡二叉树的旋转操作，旋转操作是保持树平衡的核心技术之一。

平衡二叉树（AVL树）的旋转操作

AVL树是一种自平衡的二叉搜索树，它通过旋转操作保持树的高度平衡。所谓的旋转操作，主要有以下几种类型：

1. 单右旋转
2. 单左旋转
3. 双右左旋转
4. 双左右旋转

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树这类数据结构中，旋转操作至关重要，因为它们能够保证在插入或删除操作后，树的高度始终保持在对数级别，确保了操作的高效率。

下一篇文章中，我们将转向图的高级算法，具体介绍图的表示方法，帮助我们更好地处理复杂的数据结构。请继续关注！