二进制搜索树的平衡判定：如何在 C++ 中实现 AVL 树的平衡因子检查

作者

在实现 AVL 树时，最核心的任务之一就是检查并维护每个节点的平衡因子（即左子树高度减去右子树高度）。若平衡因子不在 [-1, 1] 范围内，就需要进行旋转操作来重新平衡树。本文将从数据结构设计、递归计算高度、计算平衡因子以及触发旋转的判断逻辑等方面，给出完整的 C++ 示例代码，并对其性能与可维护性进行简要讨论。

1. 结构体设计

struct Node {
    int key;              // 关键字
    Node* left;           // 左子树
    Node* right;          // 右子树
    int height;           // 子树高度
    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};
  • height 的初始值为 1（单节点高度为 1）。
  • 为了便于后续计算，节点高度始终存储在节点本身。

2. 计算节点高度

int getHeight(Node* n) {
    return n ? n->height : 0;
}

如果节点为空，返回 0；否则返回节点本身记录的高度。

3. 更新节点高度

void updateHeight(Node* n) {
    if (!n) return;
    n->height = 1 + std::max(getHeight(n->left), getHeight(n->right));
}

在每次插入或旋转后，都需要调用此函数以保持高度信息的正确。

4. 计算平衡因子

int getBalance(Node* n) {
    if (!n) return 0;
    return getHeight(n->left) - getHeight(n->right);
}

若返回值为 -2 或 2，说明该节点失衡，需要进行旋转。

5. 旋转操作

// 右旋
Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // 旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    updateHeight(y);
    updateHeight(x);

    return x; // 新根
}

// 左旋
Node* rotateLeft(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // 旋转
    y->left = x;
    x->right = T2;

    // 更新高度
    updateHeight(x);
    updateHeight(y);

    return y; // 新根
}

6. 插入并保持平衡

Node* insert(Node* node, int key) {
    // 1. 标准 BST 插入
    if (!node) return new Node(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node; // 不允许重复

    // 2. 更新高度
    updateHeight(node);

    // 3. 计算平衡因子
    int balance = getBalance(node);

    // 4. 四种失衡情况
    // 左左情况
    if (balance > 1 && key < node->left->key)
        return rotateRight(node);

    // 右右情况
    if (balance < -1 && key > node->right->key)
        return rotateLeft(node);

    // 左右情况
    if (balance > 1 && key > node->left->key) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }

    // 右左情况
    if (balance < -1 && key < node->right->key) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    // 归一返回
    return node;
}

7. 删除节点与平衡

删除节点与插入类似，需要在递归返回后更新高度并检查平衡。常见实现可参考 Boost 或 C++ 标准库的 std::map 内部实现。由于篇幅限制，本文仅展示插入过程。

8. 性能与可维护性讨论

  1. 时间复杂度

    • 插入、删除和查找均为 O(log n)（平衡因子保持 AVL 树高度为 O(log n)）。
    • 旋转操作是常数时间。

  2. 空间复杂度

    • 递归调用栈深度为 O(log n)，若 n 较大可改为迭代实现。

  3. 代码可维护性

    • 通过把 updateHeight、getBalance、旋转函数拆分为独立函数，可读性强，易于单元测试。
    • 若想进一步模块化，可使用类包装节点并提供 insert、remove 接口。

9. 小结

本文从 AVL 树的核心——平衡因子——出发，给出了完整的 C++ 实现流程。通过在插入过程中及时更新高度并检查平衡因子，我们可以确保二叉搜索树始终保持平衡，从而提供对数级别的操作效率。希望这段代码能帮助你在项目中快速搭建一套高效的自平衡二叉搜索树。

发表评论