树 - 平衡二叉树 - 平衡二叉树的调整与维护

树 - 平衡二叉树 - 平衡二叉树的调整与维护

一、引言

在数据结构的世界里，树是一种非常重要的非线性数据结构，而平衡二叉树（AVL树）作为树结构中的一颗璀璨明星，有着独特的魅力和广泛的应用。平衡二叉树是一种自平衡的二叉搜索树，它能保证树的高度始终保持在一个相对较小的范围内，从而使得插入、删除和查找操作的时间复杂度都能稳定在 $O(log n)$。然而，要让平衡二叉树始终保持平衡状态，就需要对其进行有效的调整与维护，下面我们就来深入探讨这个过程。

二、平衡二叉树的基本概念

2.1 二叉搜索树（BST）

在了解平衡二叉树之前，我们先回顾一下二叉搜索树的定义。二叉搜索树是一种二叉树，对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。这种特性使得二叉搜索树在查找、插入和删除操作上具有一定的效率。

2.2 平衡二叉树（AVL树）

平衡二叉树是在二叉搜索树的基础上发展而来的。它要求每个节点的左右子树的高度差（平衡因子）的绝对值不超过 1。平衡因子的计算公式为：平衡因子 = 左子树高度 - 右子树高度。平衡二叉树通过这种方式保证了树的平衡性，从而提高了操作的效率。

三、平衡被破坏的原因

在对平衡二叉树进行插入或删除操作时，可能会破坏树的平衡。当插入或删除一个节点后，某些节点的平衡因子可能会超出 $[-1, 1]$ 的范围，导致树不再平衡。具体来说，插入或删除操作可能会导致以下四种不平衡的情况：

1. LL 型：在节点的左子树的左子树上插入节点，导致该节点的平衡因子大于 1。
2. RR 型：在节点的右子树的右子树上插入节点，导致该节点的平衡因子小于 -1。
3. LR 型：在节点的左子树的右子树上插入节点，导致该节点的平衡因子大于 1。
4. RL 型：在节点的右子树的左子树上插入节点，导致该节点的平衡因子小于 -1。

四、平衡二叉树的调整方法

为了恢复平衡二叉树的平衡状态，我们需要对树进行旋转操作。旋转操作主要分为左旋、右旋、左右旋和右左旋四种。

4.1 右旋（LL 型调整）

当出现 LL 型不平衡时，我们需要进行右旋操作。右旋操作的步骤如下：

1. 将当前节点的左子节点作为新的根节点。
2. 将新根节点的右子树作为当前节点的左子树。
3. 将当前节点作为新根节点的右子树。

示例代码（Python）：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.height = 1
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

4.2 左旋（RR 型调整）

当出现 RR 型不平衡时，我们需要进行左旋操作。左旋操作的步骤如下：

1. 将当前节点的右子节点作为新的根节点。
2. 将新根节点的左子树作为当前节点的右子树。
3. 将当前节点作为新根节点的左子树。

示例代码（Python）：

def left_rotate(x):
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

4.3 左右旋（LR 型调整）

当出现 LR 型不平衡时，我们需要先对当前节点的左子节点进行左旋操作，然后再对当前节点进行右旋操作。

示例代码（Python）：

def left_right_rotate(z):
    z.left = left_rotate(z.left)
    return right_rotate(z)

4.4 右左旋（RL 型调整）

当出现 RL 型不平衡时，我们需要先对当前节点的右子节点进行右旋操作，然后再对当前节点进行左旋操作。

示例代码（Python）：

def right_left_rotate(z):
    z.right = right_rotate(z.right)
    return left_rotate(z)

五、平衡二叉树的维护流程

在插入或删除节点后，我们需要按照以下步骤来维护平衡二叉树的平衡：

1. 插入或删除节点，更新节点的高度。
2. 从插入或删除节点的位置开始，向上回溯，更新每个节点的平衡因子。
3. 检查每个节点的平衡因子，如果平衡因子超出 $[-1, 1]$ 的范围，则根据不平衡的类型进行相应的旋转操作。

示例代码（Python）：

def insert(root, key):
    if not root:
        return TreeNode(key)
    elif key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    root.height = 1 + max(get_height(root.left), get_height(root.right))
    balance = get_balance(root)
    # LL
    if balance > 1 and key < root.left.val:
        return right_rotate(root)
    # RR
    if balance < -1 and key > root.right.val:
        return left_rotate(root)
    # LR
    if balance > 1 and key > root.left.val:
        return left_right_rotate(root)
    # RL
    if balance < -1 and key < root.right.val:
        return right_left_rotate(root)
    return root
def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

六、总结

平衡二叉树的调整与维护是一个复杂但有趣的过程。通过合理地运用旋转操作，我们可以确保平衡二叉树始终保持平衡状态，从而提高数据操作的效率。在实际应用中，平衡二叉树常用于需要频繁进行插入、删除和查找操作的场景，如数据库索引、搜索引擎等。希望通过本文的介绍，你能对平衡二叉树的调整与维护有更深入的理解。