欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

C++ AVL树保姆级详解：从平衡因子到四大旋转机制

2026-10-31 分类：服务器技术 阅读(11) 评论(0)

AVL树

  • 1. 引言：为什么需要 AVL 树？
    • ⭐ AVL 树的核心设计原则
  • 2. AVL 树的节点结构与三叉链设计
  • 3. 插入算法（Insert）分段拆解与答疑
    • 3.1 步骤 1：空树特判
    • 3.2 步骤 2：迭代查找落脚点并记录父节点
    • 3.3 步骤 3：开辟新节点与物理挂接
    • 3.4 步骤 4：向上回溯更新平衡因子与失衡调整
    • 3.5 Insert 接口完整代码展示
  • 4. 四大旋转机制深度剖析【重点/难点📌】
    • 4.1 右单旋（RotateR：左高右旋转）
      • 步骤 1：记录相关关键节点指针
      • 步骤 2：将 subLR 挂接在 parent 的左孩子位置
      • 步骤 3：将 parent 降为 subL 的右孩子
      • 步骤 4：链接上层父节点并更新平衡因子
      • RotateR 完整接口展示
    • 4.2 左单旋（RotateL：右高左旋转）
      • 步骤 1：记录指针与转移 subRL
      • 步骤 2：建立父子关联（降级 parent）
      • 步骤 3：重连根节点/上层节点并复位平衡因子
    • 4.3 左右双旋（RotateLR：先左旋后右旋）
      • 步骤 1：记录关键节点与平衡因子
      • 步骤 2：先后调用左单旋与右单旋
      • 步骤 3：根据原本的 bf 精准修正平衡因子
    • 4.4 右左双旋（RotateRL：先右旋后左旋）
      • 步骤 1：记录关键节点与平衡因子
      • 步骤 2：先后调用右单旋与左单旋
      • 步骤 3：根据原本的 bf 精准修正平衡因子
    • 4.5 旋转机制微总结📌
  • 5. 查找与平衡校验接口详解
    • 5.1 查找接口（Find）
    • 5.2 平衡性验证接口（IsBalanceTree）剖析

1. 引言：为什么需要 AVL 树？

我们曾学过普通二叉搜索树（BST）。它的核心特性是“左子树所有节点小于等于根节点，右子树所有节点大于等于根节点”。 但在实际应用中，如果我们向二叉搜索树中连续插入一组有序数据（例如 1, 2, 3, 4, 5, 6），树就会彻底退化成一根单向的“单支树”（类似于链表）。此时，它的查找效率会从理想的

O

(

log

⁡

2

N

)

O(\\log_2 N)

O(log2​N) 直接暴跌到

O

(

N

)

O(N)

O(N)。

为了解决普通二叉搜索树退化的问题，两位苏联数学家 Adelson-Velsky 和 Landis 在 1962 年的论文《An algorithm for the organization of information》中提出了一种经典的高度平衡二叉搜索树——AVL 树（以两人名字缩写命名）。

⭐ AVL 树的核心设计原则

  • AVL 树本质上依然是一棵二叉搜索树，但它额外增加了一条严格的平衡约束：它的左右子树都是 AVL 树，且左右子树的高度差（平衡因子）的绝对值不超过 1（即

    ≤

    1

    \\le 1

    ≤1）。

  • 通过控制高度差去控制平衡，树的高度可以严格控制在

    O

    (

    log

    ⁡

    N

    )

    O(\\log N)

    O(logN)，增删查改的效率也保持在

    O

    (

    log

    ⁡

    N

    )

    O(\\log N)

    O(logN)

    • 💡思考：为什么 AVL 树要求高度差不超过 1，而不是做到高度差为 0？ 不是不想做到高度差为 0（绝对平衡），而是客观上无法做到！例如当节点总数为 2 或 4 时，一棵满二叉树需要满足

    2

    k

    −

    1

    2^k – 1

    2k−1 个节点，在节点数不满足满二叉树要求时，高度差最小只能维持在 1。

    2. AVL 树的节点结构与三叉链设计

    为了方便在插入新节点后向上回溯、更新平衡因子以及进行旋转调整，AVL 树的节点设计采用了三叉链结构（即包含左孩子、右孩子以及父节点指针）。

    template<class K, class V>
    struct AVLTreeNode
    {
    pair<K, V> _kv; // 键值对
    AVLTreeNode<K, V>* _left; // 左孩子指针
    AVLTreeNode<K, V>* _right; // 右孩子指针
    AVLTreeNode<K, V>* _parent; // 父亲节点指针（三叉链，便于向上回溯）
    int _bf; // 平衡因子 (Balance Factor)

    // 节点构造函数
    AVLTreeNode(const pair<K, V>& kv)
    :_kv(kv)
    , _left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _bf(0) // 新节点初始平衡因子为 0
    { }
    };

    template<class K, class V>
    class AVLTree
    {
    typedef AVLTreeNode<K, V> Node;
    public:
    // …
    private:
    Node* _root = nullptr;
    };

    ⭐ 语法细节与行为机制：

    平衡因子（_bf）：定义为 右子树高度减去左子树高度（_bf = 右子树高度 – 左子树高度）。 因此，AVL 树中所有节点的 _bf 值只能是 -1、0 或 1。一旦绝对值达到 2（变为 2 或 -2），就代表树失去了平衡，必须触发旋转！

    3. 插入算法（Insert）分段拆解与答疑

    AVL 树的插入逻辑非常严密，我们可以将其拆解为 4 个步骤 逐步进行解析：

    函数声明为：

    bool Insert(const pair<K, V>& kv);

    3.1 步骤 1：空树特判

    // 1. 空树特判
    if (_root == nullptr)
    {
    _root = new Node(kv);
    return true;
    }

    ⭐ 语法细节与行为机制： 当树为空（_root == nullptr）时，没有父节点可供链接。此时直接开辟新节点作为整棵树的根节点即可完成插入。

    3.2 步骤 2：迭代查找落脚点并记录父节点

    Node* cur = _root;
    Node* parent = nullptr;

    while (cur)
    // cur要找到空位置插入
    {
    // 记录父亲节点，子节点继续走
    // 新插入大于原节点，右边走
    if (cur->_kv.first < kv.first)
    {
    parent = cur;
    cur = cur->_right;
    }
    else if (cur->_kv.first > kv.first)
    {
    parent = cur;
    cur = cur->_left;
    }
    else
    {
    return false; // 已存在相同的 Key，不允许冗余，插入失败
    }
    }

    ⭐ 语法细节与行为机制：

    Parent 追踪：利用 parent 实时记录 cur 的父节点指针，因为当 while(cur) 循环结束时，cur 已经为 nullptr，无法直接通过 cur 修改上级节点的指针，必须依赖 parent。

    去重校验：按二叉搜索树规则查找，若遇到相同 key，直接返回 false。

    3.3 步骤 3：开辟新节点与物理挂接

    // 创造新节点
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
    parent->_right = cur;
    }
    else
    {
    parent->_left = cur;
    }
    cur->_parent = parent;// 链接父亲

    ⭐ 语法细节与行为机制： 新节点 new 出来后，除了更新 parent 的 _left 或 _right 指向 cur，还必须建立反向链接：cur->_parent = parent，这是三叉链结构维持后续向上更新的核心。

    3.4 步骤 4：向上回溯更新平衡因子与失衡调整

    // 更新平衡因子
    while (parent)// 为什么？
    // 一旦parent为空，则cur达到了根部，更新结束
    {
    // 新插入节点 插在左边 —
    if (cur == parent->_left)
    parent->_bf—;
    else
    parent->_bf++;

    if (parent->_bf == 0)
    {
    // 更新结束
    break;
    }
    else if (parent->_bf == 1 || parent->_bf == –1)
    {
    // 向上更新
    cur = parent;
    parent = parent->_parent;
    }
    else if (parent->_bf == 2 || parent->_bf == –2)
    {
    if (parent->_bf == –2 && cur->_bf == –1)
    {
    // 左高右旋转
    RotateR(parent);
    }
    else if (parent->_bf == 2 && cur->_bf == 1)
    {
    // 右高左旋转
    RotateL(parent);
    }
    else if (parent->_bf == –2 && cur->_bf == 1)
    {
    // 孩子右高，父亲左高
    // 孩子左旋，父亲右旋
    RotateLR(parent);
    }
    else if (parent->_bf == 2 && cur->_bf == –1)
    {
    RotateRL(parent);
    }
    else
    {
    assert(false);
    }

    // 旋转结束退出循环！
    break;
    }
    else
    {
    assert(false);
    }
    }
    return true;

    ⭐ 语法细节与行为机制：

    平衡因子更新规则： 新增节点在 parent 的左边，parent->_bf–；在右边，parent->_bf++。

    🤔 疑问：为什么需要循环向上更新？ 插入新节点后，直接受影响的是 parent。但 parent 高度发生变化后，可能会进一步影响祖先节点：

    • parent->_bf == 0：说明插入前 parent->_bf 是 1 或 -1，新节点填平了矮的一侧，子树整体高度没有改变，不会影响上层祖先，break 停止更新。

    • parent->_bf == ±1：说明插入前 parent->_bf 是 0，新节点导致子树高度增加了一层，会改变上层祖先节点的平衡因子，必须 cur = parent; parent = parent->_parent; 继续向上回溯。

    • parent->_bf == ±2：说明打破了平衡，需要触发旋转。旋转会将子树高度降回插入前的水平，不再影响上层，旋转后直接 break 结束。

    • 当更新到根节点时，parent 变为 nullptr，循环自然结束。

    3.5 Insert 接口完整代码展示

    bool Insert(const pair<K, V>& kv)
    {
    // 步骤 1：空树特判
    if (_root == nullptr)
    {
    _root = new Node(kv);
    return true;
    }

    // 步骤 2：迭代查找落脚点
    Node* cur = _root;
    Node* parent = nullptr;

    while (cur)
    {
    if (cur->_kv.first < kv.first)
    {
    parent = cur;
    cur = cur->_right;
    }
    else if (cur->_kv.first > kv.first)
    {
    parent = cur;
    cur = cur->_left;
    }
    else
    {
    return false;
    }
    }

    // 步骤 3：开辟新节点与建立物理挂接
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
    parent->_right = cur;
    }
    else
    {
    parent->_left = cur;
    }
    cur->_parent = parent;

    // 步骤 4：向上更新平衡因子与调整
    while (parent)
    {
    if (cur == parent->_left)
    parent->_bf—;
    else
    parent->_bf++;

    if (parent->_bf == 0)
    {
    break;
    }
    else if (parent->_bf == 1 || parent->_bf == –1)
    {
    cur = parent;
    parent = parent->_parent;
    }
    else if (parent->_bf == 2 || parent->_bf == –2)
    {
    if (parent->_bf == –2 && cur->_bf == –1)
    {
    RotateR(parent);
    }
    else if (parent->_bf == 2 && cur->_bf == 1)
    {
    RotateL(parent);
    }
    else if (parent->_bf == –2 && cur->_bf == 1)
    {
    RotateLR(parent);
    }
    else if (parent->_bf == 2 && cur->_bf == –1)
    {
    RotateRL(parent);
    }
    else
    {
    assert(false);
    }

    break;
    }
    else
    {
    assert(false);
    }
    }
    return true;
    }

    4. 四大旋转机制深度剖析【重点/难点📌】

    旋转的核心目的是：在保持二叉搜索树“左小右大”性质的前提下，降低失衡子树的高度，恢复平衡。

    4.1 右单旋（RotateR：左高右旋转）

    💡 触发场景与具体示例 当 parent->_bf == -2 且 cur->_bf == -1 时，说明新节点插入在了左孩子的左子树中（左左过高，直线结构）。

    假设初始树如下，插入节点 1 导致失衡： 在这里插入图片描述

    • 失衡原因： 在 5 的左子树插入新节点 1，使得 5 的平衡因子变为 -1，顺着父节点向上回溯导致 10 的平衡因子变为 -2，触发右单旋。

    • 旋转效果： 以 10 为旋转轴向右压，5 提升为新根，10 降为 5 的右孩子，5 的右子树 b 挂到 10 的左侧。旋转后树的高度恢复平衡，且 5 和 10 的平衡因子全部复位为 0。

    函数声明为：

    void RotateR(Node* parent);

    步骤 1：记录相关关键节点指针

    为了防止指针修改导致丢失节点，先定义并记录 subL（左孩子）、subLR（左孩子的右子树）以及 pParent（parent 的上层父节点）：

    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* pParent = parent->_parent; // 提前记录父亲节点

    步骤 2：将 subLR 挂接在 parent 的左孩子位置

    根据 BST 特性，subLR 的值介于 subL 与 parent 之间，旋转后挂在 parent 的左侧：

    parent->_left = subLR;
    if (subLR)
    subLR->_parent = parent;

    🤔 疑问：为什么需要连接 subLR 与 parent，且必须判断 subLR 不为空？

    性质原因：subLR 作为 subL 的右子树，其值大于 subL 但小于 parent。旋转后 parent 降为 subL 的右孩子，subLR 必须重新挂接在 parent 的左孩子位置，以维持二叉搜索树的“左小右大”性质。

    防御原因：subL 并不一定拥有右子树（subLR 可能为 nullptr）。若不判空直接访问 subLR->_parent，会引发空指针解引用崩溃。

    步骤 3：将 parent 降为 subL 的右孩子

    维持双向链表属性，将 parent 挂接为 subL 的右子树：

    subL->_right = parent;
    parent->_parent = subL; // 父亲也要改

    步骤 4：链接上层父节点并更新平衡因子

    判断 parent 原先是整棵树的根节点还是局部子树的根节点：

    if (parent == _root)
    {
    _root = subL;
    _root->_parent = nullptr; // 根节点无父亲
    }
    else
    {
    if (pParent->_left == parent)
    {
    pParent->_left = subL;
    }
    else
    {
    pParent->_right = subL;
    }
    subL->_parent = pParent; // subL 也要连接父亲
    }

    // 更新平衡因子
    subL->_bf = parent->_bf = 0;

    RotateR 完整接口展示

    void RotateR(Node* parent)
    {
    // 步骤 1：记录相关关键节点指针
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* pParent = parent->_parent;

    // 步骤 2：挂接 subLR 到 parent 的左侧
    parent->_left = subLR;
    if (subLR)
    subLR->_parent = parent;

    // 步骤 3：降 parent 为 subL 的右孩子
    subL->_right = parent;
    parent->_parent = subL;

    // 步骤 4：处理上层父节点链接与平衡因子更新
    if (parent == _root)
    {
    _root = subL;
    _root->_parent = nullptr;
    }
    else
    {
    if (pParent->_left == parent)
    {
    pParent->_left = subL;
    }
    else
    {
    pParent->_right = subL;
    }
    subL->_parent = pParent;
    }

    subL->_bf = parent->_bf = 0;
    }

    4.2 左单旋（RotateL：右高左旋转）

    💡 触发场景与具体示例 当 parent->_bf == 2 且 cur->_bf == 1 时，说明新节点插入在了右孩子的右子树中（右右过高，直线结构）。

    假设初始树如下，插入节点 20 导致失衡： 在这里插入图片描述 函数声明为：

    void RotateL(Node* parent)

    步骤 1：记录指针与转移 subRL

    首先记录关键节点 subR（右孩子）、subRL（右孩子的左子树）。将 subRL 挂接到 parent 的右边：

    // 1. 记录右孩子及其左子树
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    // 2. 将 subRL 移交挂接到 parent 的右侧
    parent->_right = subRL;

    // 3. 若 subRL 存在，维护其双向父指针（注意防范空指针）
    if (subRL)
    subRL->_parent = parent;

    步骤 2：建立父子关联（降级 parent）

    记录 parent 的上层父节点 pParent，并将 parent 降格挂接为 subR 的左孩子：

    // 1. 记录 parent 原本的父节点
    Node* pParent = parent->_parent;

    // 2. 将 parent 降为 subR 的左孩子，并修改其父指针
    subR->_left = parent;
    parent->_parent = subR;

    步骤 3：重连根节点/上层节点并复位平衡因子

    判断 parent 原先是否为整棵树的根节点。如果是根节点，直接更新 _root；如果是局部子树，则让上层父节点接管 subR：

    if (parent == _root)
    {
    _root = subR;
    _root->_parent = nullptr; // 根节点没有父亲
    }
    else
    {
    // 让上层父节点连接新的子树根 subR
    if (pParent->_left == parent)
    {
    pParent->_left = subR;
    }
    else
    {
    pParent->_right = subR;
    }
    subR->_parent = pParent; // subR 建立向上的链接
    }

    // 4. 旋转完成后，复位平衡因子
    subR->_bf = parent->_bf = 0;

    4.3 左右双旋（RotateLR：先左旋后右旋）

    💡 触发场景与具体示例 当 parent->_bf == -2 且 cur->_bf == 1 时，说明新节点插入在了左孩子的右子树中（左右过高，呈折线形态）。

    单纯的单旋无法解决折线问题，必须通过两次旋转组合完成：

  • 先对左孩子 parent->_left 做左单旋（将折线拉直成纯左斜线）；

  • 再对父节点 parent 做右单旋（整体降低高度恢复平衡）。

    • 示例图解（以 subLR 插入在左侧为例）：

    在这里插入图片描述

    失衡原因： 新节点插在 5 的右孩子 8 的左子树中，导致 5 的平衡因子为 1（孩子右高），而 10 的平衡因子变为 -2（父亲左高），呈折线形。

    旋转效果： 通过左旋 5 再右旋 10，8 被提升为新根。

    精修平衡因子： 双旋后各个节点的平衡因子需要根据旋转前 subLR（即 8）原本的 _bf 来精准修补。

    函数声明为：

    void RotateLR(Node* parent);

    步骤 1：记录关键节点与平衡因子

    在单旋修改平衡因子之前，必须提前保存 subLR->_bf，因为它是最后决定各个节点平衡因子如何赋值的关键依据：

    // 1. 记录左孩子及其右子树
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    // 2. 提前保存 subLR 原本的平衡因子
    int bf = subLR->_bf;

    步骤 2：先后调用左单旋与右单旋

    通过两次单旋组合调整结构：

    // 1. 先对左孩子进行左单旋（拉直折线）
    RotateL(parent->_left);

    // 2. 再对父节点进行右单旋（恢复平衡）
    RotateR(parent);

    步骤 3：根据原本的 bf 精准修正平衡因子

    根据插入前 subLR 的平衡因子状态（bf == -1, 1, 或 0），分情况精细更新各个节点的 _bf：

    if (bf == –1)
    {
    subLR->_bf = 0;
    subL->_bf = 0;
    parent->_bf = 1;
    }
    else if (bf == 1)
    {
    subLR->_bf = 0;
    subL->_bf = –1;
    parent->_bf = 0;
    }
    else if (bf == 0)
    {
    subLR->_bf = 0;
    subL->_bf = 0;
    parent->_bf = 0;
    }
    else
    {
    // 防御性编程：若走到这里说明平衡因子记录出错
    assert(false);
    }

    4.4 右左双旋（RotateRL：先右旋后左旋）

    💡 触发场景与具体示例 当 parent->_bf == 2 且 cur->_bf == -1 时，说明新节点插入在了右孩子的左子树中（右左过高，呈折线形态）。

    单纯的单旋无法解决折线问题，必须通过两次旋转组合完成：

  • 先对右孩子 parent->_right 做右单旋（将折线拉直成纯右斜线）；

  • 再对父节点 parent 做左单旋（整体降低高度恢复平衡）。

    • 示例图解：

    在这里插入图片描述 失衡原因： 新节点插在 15 的左孩子 12 的左侧，引发 15 平衡因子变为 -1（孩子左高），而 10 的平衡因子变为 2（父亲右高），呈折线形。

    旋转效果： 通过右旋 15 再左旋 10，12 被提升为新根。

    精修平衡因子： 双旋后各个节点的平衡因子需要根据旋转前 subRL（即 12）原本的 _bf 来精准修补。

    函数声明为：

    void RotateRL(Node* parent);

    步骤 1：记录关键节点与平衡因子

    在旋转修改平衡因子之前，必须提前保存 subRL->_bf，因为它是最后决定各个节点平衡因子如何赋值的关键依据：

    // 1. 记录右孩子及其左子树
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    // 2. 提前保存 subRL 原本的平衡因子
    int bf = subRL->_bf;

    步骤 2：先后调用右单旋与左单旋

    通过两次单旋组合调整结构：

    // 1. 先对右孩子进行右单旋（拉直折线）
    RotateR(parent->_right);

    // 2. 再对父节点进行左单旋（恢复平衡）
    RotateL(parent);

    步骤 3：根据原本的 bf 精准修正平衡因子

    根据插入前 subRL 的平衡因子状态（bf == -1, 1, 或 0），分情况精细更新各个节点的 _bf：

    if (bf == –1)
    {
    subRL->_bf = 0;
    subR->_bf = 1;
    parent->_bf = 0;
    }
    else if (bf == 1)
    {
    subRL->_bf = 0;
    subR->_bf = 0;
    parent->_bf = –1;
    }
    else if (bf == 0)
    {
    subR->_bf = 0;
    subRL->_bf = 0;
    parent->_bf = 0;
    }
    else
    {
    // 防御性编程：若走到这里说明平衡因子记录出错
    assert(false);
    }

    4.5 旋转机制微总结📌

    学完四大旋转，我们可以把它们归纳为一个清晰的记忆口诀：

  • 直线失衡（单旋解决）：

    • 左左高 (-2, -1)

      →

      \\rightarrow

      → 右单旋（RotateR）。

    • 右右高 (2, 1)

      →

      \\rightarrow

      → 左单旋（RotateL）。

  • 折线失衡（双旋解决）：

    • 左右高 (-2, 1)

      →

      \\rightarrow

      → 左右双旋（RotateLR）（先左旋子树，再右旋父亲）。

    • 右左高 (2, -1)

      →

      \\rightarrow

      → 右左双旋（RotateRL）（先右旋子树，再左旋父亲）。

    • 核心重点：双旋的核心在于“先拉直，后整体压平衡”，并且必须根据插入点位置（即孙子节点的平衡因子）来精准修正各个节点的 _bf。

    5. 查找与平衡校验接口详解

    在写完 AVL 树的核心增删改结构后，我们需要提供对应的查找接口来对外提供数据检索，以及提供平衡校验接口来验证我们写的 AVL 树是否真正符合高度平衡的规范。

    5.1 查找接口（Find）

    剖析查找逻辑与普通二叉搜索树完全一致，利用“左小右大”的有序性进行二分路径排除，时间复杂度为

    O

    (

    log

    ⁡

    N

    )

    O(\\log N)

    O(logN)。

    函数声明为：

    Node* Find(const K& key);

    代码解析：

    Node* Find(const K& key)
    {
    Node* cur = _root; // 从根节点开始遍历

    while (cur)
    {
    if (cur->_kv.first == key)
    return cur; // 找到了，直接返回该节点的指针

    else if (cur->_kv.first < key)
    {
    cur = cur->_right; // 目标 key 大于当前节点，向右子树查找
    }
    else if (cur->_kv.first > key)
    {
    cur = cur->_left; // 目标 key 小于当前节点，向左子树查找
    }
    else
    {
    assert(false);
    }
    }
    return nullptr; // 遍历到空仍未找到，返回空指针
    }

    5.2 平衡性验证接口（IsBalanceTree）剖析

    为了确保我们在旋转和平衡因子更新过程中没有出现逻辑漏洞，必须写一个自动化检测工具来反向验证整棵树是否满足 AVL 树的要求：

    任意节点的左右子树高度差绝对值不超过 1。

    节点内部记录的 _bf 平衡因子必须与其实际计算出来的高度差（右子树高度 – 左子树高度）完全吻合。

    函数声明为：

    bool IsBalanceTree();

    代码解析： 我们可以通过递归后序遍历的方式来实现检验：

    public:
    // 对外暴露的公有校验接口
    bool IsBalanceTree()
    {
    return _IsBalanceTree(_root);
    }

    private:
    // 递归计算子树高度
    int _Height(Node* root)
    {
    if (root == nullptr)
    return 0;

    int leftH = _Height(root->_left);
    int rightH = _Height(root->_right);

    return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    // 递归检查是否为合格的 AVL 树（采用后序遍历，自底向上校验）
    bool _IsBalanceTree(Node* root)
    {
    // 空树也是合法的 AVL 树
    if (root == nullptr)
    return true;

    // 1. 分别计算左右子树的实际高度
    int leftH = _Height(root->_left);
    int rightH = _Height(root->_right);
    int diff = rightH – leftH;

    // 2. 检查高度差绝对值是否超过 1
    if (abs(diff) > 1)
    {
    cout << "错误：节点 " << root->_kv.first << " 高度差异常，实际高度差为: " << diff << endl;
    return false;
    }

    // 3. 检查节点内部记录的平衡因子 _bf 是否与实际高度差匹配
    if (root->_bf != diff)
    {
    cout << "错误：节点 " << root->_kv.first << " 平衡因子异常，当前记录: " << root->_bf << "，实际应为: " << diff << endl;
    return false;
    }

    // 4. 递归检查其左子树和右子树是否也满足 AVL 树
    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
    }

  • AVL 树完整 C++ 实现代码 以下是整合修正后的完整版 C++ 代码，方便拷贝测试与复习：

    • #pragma once
    #include <assert.h>
    #include <iostream>
    #include <cmath>
    using namespace std;

    // 1. AVL 树节点定义
    template<class K, class V>
    struct AVLTreeNode
    {
    pair<K, V> _kv; // 键值对
    AVLTreeNode<K, V>* _left; // 左孩子指针
    AVLTreeNode<K, V>* _right; // 右孩子指针
    AVLTreeNode<K, V>* _parent; // 父亲节点指针（三叉链，便于向上回溯）
    int _bf; // 平衡因子 (Balance Factor = 右子树高度 – 左子树高度)

    // 节点构造函数
    AVLTreeNode(const pair<K, V>& kv)
    :_kv(kv)
    , _left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _bf(0)
    { }
    };

    // 2. AVL 树类定义
    template<class K, class V>
    class AVLTree
    {
    typedef AVLTreeNode<K, V> Node;
    public:
    // —————————————–
    // 插入接口（Insert）
    // —————————————–
    bool Insert(const pair<K, V>& kv)
    {
    // 步骤 1：空树特判
    if (_root == nullptr)
    {
    _root = new Node(kv);
    return true;
    }

    Node* cur = _root;
    Node* parent = nullptr;

    // 步骤 2：迭代查找落脚点
    while (cur)
    {
    if (cur->_kv.first < kv.first)
    {
    parent = cur;
    cur = cur->_right;
    }
    else if (cur->_kv.first > kv.first)
    {
    parent = cur;
    cur = cur->_left;
    }
    else
    {
    return false; // 不允许插入相同的 Key
    }
    }

    // 步骤 3：开辟新节点与物理挂接
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
    parent->_right = cur;
    }
    else
    {
    parent->_left = cur;
    }
    cur->_parent = parent; // 建立双向父子链接

    // 步骤 4：向上回溯更新平衡因子并处理失衡
    while (parent)
    {
    // 新增在左边，平衡因子–；新增在右边，平衡因子++
    if (cur == parent->_left)
    parent->_bf—;
    else
    parent->_bf++;

    if (parent->_bf == 0)
    {
    // 说明子树高度没变，更新结束
    break;
    }
    else if (parent->_bf == 1 || parent->_bf == –1)
    {
    // 子树高度增加，继续向上回溯更新祖先
    cur = parent;
    parent = parent->_parent;
    }
    else if (parent->_bf == 2 || parent->_bf == –2)
    {
    // 触发失衡，根据失衡形态选择对应的旋转策略
    if (parent->_bf == –2 && cur->_bf == –1)
    {
    RotateR(parent); // 左左：右单旋
    }
    else if (parent->_bf == 2 && cur->_bf == 1)
    {
    RotateL(parent); // 右右：左单旋
    }
    else if (parent->_bf == –2 && cur->_bf == 1)
    {
    RotateLR(parent); // 左右：左右双旋
    }
    else if (parent->_bf == 2 && cur->_bf == –1)
    {
    RotateRL(parent); // 右左：右左双旋
    }
    else
    {
    assert(false);
    }

    // 旋转后子树高度恢复，直接退出循环
    break;
    }
    else
    {
    assert(false);
    }
    }
    return true;
    }

    // —————————————–
    // 右单旋（RotateR）
    // —————————————–
    void RotateR(Node* parent)
    {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    parent->_left = subLR;
    if (subLR)
    subLR->_parent = parent;

    Node* pParent = parent->_parent;

    subL->_right = parent;
    parent->_parent = subL;

    if (parent == _root)
    {
    _root = subL;
    _root->_parent = nullptr;
    }
    else
    {
    if (pParent->_left == parent)
    {
    pParent->_left = subL;
    }
    else
    {
    pParent->_right = subL;
    }
    subL->_parent = pParent;
    }

    subL->_bf = parent->_bf = 0;
    }

    // —————————————–
    // 左单旋（RotateL）
    // —————————————–
    void RotateL(Node* parent)
    {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    parent->_right = subRL;
    if (subRL)
    subRL->_parent = parent;

    Node* pParent = parent->_parent;

    subR->_left = parent;
    parent->_parent = subR;

    if (parent == _root)
    {
    _root = subR;
    _root->_parent = nullptr;
    }
    else
    {
    if (pParent->_left == parent)
    {
    pParent->_left = subR;
    }
    else
    {
    pParent->_right = subR;
    }
    subR->_parent = pParent;
    }

    subR->_bf = parent->_bf = 0;
    }

    // —————————————–
    // 左右双旋（RotateLR）
    // —————————————–
    void RotateLR(Node* parent)
    {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;

    RotateL(parent->_left);
    RotateR(parent);

    if (bf == –1)
    {
    subLR->_bf = 0;
    subL->_bf = 0;
    parent->_bf = 1;
    }
    else if (bf == 1)
    {
    subLR->_bf = 0;
    subL->_bf = –1;
    parent->_bf = 0;
    }
    else if (bf == 0)
    {
    subLR->_bf = 0;
    subL->_bf = 0;
    parent->_bf = 0;
    }
    else
    {
    assert(false);
    }
    }

    // —————————————–
    // 右左双旋（RotateRL）
    // —————————————–
    void RotateRL(Node* parent)
    {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;

    RotateR(parent->_right);
    RotateL(parent);

    if (bf == –1)
    {
    subRL->_bf = 0;
    subR->_bf = 1;
    parent->_bf = 0;
    }
    else if (bf == 1)
    {
    subRL->_bf = 0;
    subR->_bf = 0;
    parent->_bf = –1;
    }
    else if(bf == 0)
    {
    subR->_bf = 0;
    subRL->_bf = 0;
    parent->_bf = 0;
    }
    else
    {
    assert(false);
    }
    }

    // —————————————–
    // 查找接口（Find）
    // —————————————–
    Node* Find(const K& key)
    {
    Node* cur = _root;

    while (cur)
    {
    if (cur->_kv.first == key)
    return cur;
    else if (cur->_kv.first < key)
    cur = cur->_right;
    else
    cur = cur->_left;
    }
    return nullptr;
    }

    // —————————————–
    // 中序遍历接口
    // —————————————–
    void InOrder()
    {
    _InOrder(_root);
    cout << endl;
    }

    // —————————————–
    // 平衡性验证接口（IsBalanceTree）
    // —————————————–
    bool IsBalanceTree()
    {
    return _IsBalanceTree(_root);
    }

    int Height()
    {
    return _Height(_root);
    }

    int Size()
    {
    return _Size(_root);
    }

    private:
    Node* _root = nullptr;

    void _InOrder(Node* root)
    {
    if (root == nullptr)
    return;

    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
    }

    int _Height(Node* root)
    {
    if (root == nullptr)
    return 0;

    int leftH = _Height(root->_left);
    int rightH = _Height(root->_right);

    return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    bool _IsBalanceTree(Node* root)
    {
    if (root == nullptr)
    return true;

    int leftH = _Height(root->_left);
    int rightH = _Height(root->_right);
    int diff = rightH – leftH;

    if (abs(diff) > 1)
    {
    cout << "高度差异常" << endl;
    return false;
    }

    if (root->_bf != diff)
    {
    cout << "平衡因子异常" << endl;
    return false;
    }

    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
    }

    int _Size(Node* root)
    {
    if (root == nullptr)
    return 0;

    return _Size(root->_left) + _Size(root->_right) + 1;
    }
    };

    赞(0)
    未经允许不得转载：171主机测评 » C++ AVL树保姆级详解：从平衡因子到四大旋转机制
    分享到： 更多 (0)
    标签：

    相关推荐

    评论 抢沙发

    取消

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址

    热门标签

    #人工智能(64385)#python(21453)#开发语言(17850)#java(16427)#运维(16188)#linux(15663)#大数据(15330)#服务器(13676)#算法(12310)#前端(11668)#ai(10291)#网络(9919)#数据库(9519)#c++(8660)#学习(7175)#课程设计(7035)#机器学习(7014)#区块链(6064)#后端(5543)#OpenClaw(5416)#spring boot(5300)#深度学习(5278)#c语言(4558)#安全(4495)#毕业设计(4401)#数据结构(4341)#架构(4175)#docker(4120)#javascript(3984)#大模型(3921)

    热门文章

    最新文章

    归档

    分类