C++ AVL 树功能实现原理剖析

检查是否为空树并处理根节点

if (_root == nullptr) {
    _root = new Node(kv);
    return true;
}

如果 AVL 树当前为空树，即 _root 为 nullptr，直接将新节点作为根节点插入，并结束操作。因为此时没有其他节点需要进行平衡因子的调整，所以插入结束。

查询插入位置（非递归）

Node* parent = nullptr;
Node* cur = _root;
// find insert place
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; // Duplicate key, insertion failed
    }
}

在树中插入节点时，需要按照二叉搜索树的规则找到适当的位置：

• 当前节点（cur）的键值（cur->_kv.first）与要插入的值（kv.first）进行比较。
• 如果插入值小于当前节点，则移动到左子树。
• 如果插入值大于当前节点，则移动到右子树。
• 如果发现与当前节点的键值相同，插入失败，因为 AVL 树不允许重复键值。

通过遍历，cur 最终会指向 nullptr，即找到了插入的位置，parent 指向插入节点的父节点。

插入节点并连接父节点

cur = new Node(kv);
if (parent->_kv.first < kv.first) {
    parent->_right = cur;
} else {
    parent->_left = cur;
}
cur->_parent = parent;

找到插入位置后，新节点 cur 将被创建并插入到父节点 parent 的左子树或右子树中。此时新节点已经成功插入，但它可能会影响树的平衡，需要继续调整平衡因子。

更新平衡因子（在失去平衡的条件下进行旋转）

while (parent) {
    if (cur == parent->_left) {
        parent->_bf--; // 插入左子树，平衡因子 -1
    } else {
        parent->_bf++; // 插入右子树，平衡因子 +1
    }
    if (parent->_bf == 0) {
        break; // 如果平衡因子为 0，树高度未变，停止更新
    } else if (parent->_bf == -1 || parent->_bf == 1) {
        cur = parent;
        parent = parent->_parent; // 继续向上更新平衡因子
    } else if (parent->_bf == -2 || parent->_bf == 2) {
        // 需要旋转
        // ...
        break;
    } else {
        assert(false); // 出现了异常情况
    }
}

平衡因子的更新：更新原则平衡因⼦ = 右⼦树⾼度 - 左⼦树⾼度只有⼦树⾼度变化才会影响当前结点平衡因⼦。插⼊结点，会增加⾼度，所以新增结点在 parent 的右⼦树，parent 的平衡因⼦ ++，新增结点在 parent 的左⼦树，parent 平衡因⼦ -- parent 所在⼦树的⾼度是否变化决定了是否会继续往上更新更新停止条件更新后 parent 的平衡因⼦等于 0，更新中 parent 的平衡因⼦变化为 -1->0 或者 1->0，说明更新前 parent ⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后 parent 所在的⼦树⾼度不变，不会影响 parent 的⽗亲结点的平衡因⼦，更新结束。更新后 parent 的平衡因⼦等于 1 或 -1，更新前更新中 parent 的平衡因⼦变化为 0->1 或者 0->-1，说明更新前 parent ⼦树两边⼀样⾼，新增的插⼊结点后，parent 所在的⼦树⼀边⾼⼀边低，parent 所在的⼦树符合平衡要求，但是⾼度增加了 1，会影响 parent 的⽗亲结点的平衡因⼦，所以要继续向上更新。更新后 parent 的平衡因⼦等于 2 或 -2，更新前更新中 parent 的平衡因⼦变化为 1->2 或者 -1->-2，说明更新前 parent ⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent 所在的⼦树⾼的那边更⾼了，破坏了平衡，parent 所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：

1. 把 parent ⼦树旋转平衡。
2. 降低 parent ⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。

旋转

旋转的原则

保持搜索树的规则通过降低旋转树的高度，让旋转的树从不平衡变为平衡

通过不同的情况，旋转分为四种：左单旋、右单旋、左右单旋、右左单旋。

右单旋（R）

旋转场景

右单旋用于修复左左失衡（LL 失衡），即插入的新节点位于左子树的左侧，导致该节点的左子树高度比右子树大 2。

旋转原理

通过右旋，可以将失衡的左子树提升到当前节点的根节点位置，将当前节点向右旋转，形成新的平衡状态。

操作步骤

void RotateR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    // 将 subL 的右子树 subLR 链接为 parent 的左子树
    parent->_left = subLR;
    if (subLR) {
        subLR->_parent = parent;
    }
    // 将 subL 提升为 parent 的父节点
    Node* pParent = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
    // 更新父节点指针，如果 parent 是根节点，则更新根节点
    if (pParent == nullptr) {
        _root = subL;
        subL->_parent = nullptr;
    } else {
        if (pParent->_left == parent) {
            pParent->_left = subL;
        } else {
            pParent->_right = subL;
        }
        subL->_parent = pParent;
    }
    // 调整平衡因子
    parent->_bf = subL->_bf = 0;
}

将 parent 的左子树（即 subL）提升为新的根节点。将 subL 的右子树（即 subLR，subL 的右子树是 parent 左子树中最大的节点，对于右子树来说是最小的节点，所以用来做 parent 的左子树用来保持搜索树的规则）链接为 parent 的左子树。将 subL 的右子树设置为 parent。如果 parent 是树的根节点，需要更新树的根节点为 subL，否则，将 subL 链接到 parent 的父节点上。

左单旋（L）

旋转场景

左单旋用于修复右右失衡（RR 失衡），即插入的新节点位于右子树的右侧，导致该节点的右子树高度比左子树大 2。

旋转原理

通过左旋，可以将失衡的右子树提升到当前节点的根节点位置，将当前节点向左旋转，形成新的平衡状态。

操作步骤

void RotateL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    // 将 subR 的左子树 subRL 链接为 parent 的右子树
    parent->_right = subRL;
    if (subRL) {
        subRL->_parent = parent;
    }
    // 将 subR 提升为 parent 的父节点
    Node* pParent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    // 更新父节点指针，如果 parent 是根节点，则更新根节点
    if (pParent == nullptr) {
        _root = subR;
        subR->_parent = nullptr;
    } else {
        if (pParent->_left == parent) {
            pParent->_left = subR;
        } else {
            pParent->_right = subR;
        }
        subR->_parent = pParent;
    }
    // 调整平衡因子
    parent->_bf = subR->_bf = 0;
}

将 parent 的右子树（即 subR）提升为新的根节点。将 subR 的左子树（即 subRL，subR 的左子树是 parent 右子树中最小的节点，对于左子树来说是最大的节点，所以用来做 parent 的右子树用来保持搜索树的规则）链接为 parent 的右子树。将 subR 的左子树设置为 parent。如果 parent 是树的根节点，需要更新树的根节点为 subR，否则，将 subR 链接到 parent 的父节点上。

左右双旋（LR 旋转）

旋转场景

左右双旋用于修复左右失衡（LR 失衡），这种情况发生在插入的节点位于左子树的右侧，导致左子树比右子树高 2，但左子树的右子树比左子树的左子树高。这种情况下，仅仅进行一次右旋（RR 旋转）无法恢复平衡，必须先进行左旋（LL 旋转），再进行右旋。

操作步骤

1. 第一步：左旋
   首先对失衡节点的左子树进行一次左旋，使其符合右右失衡（RR 失衡）的结构。
2. 第二步：右旋
   然后对当前失衡节点进行一次右旋，使整个子树重新恢复平衡。

旋转后平衡因子的更新

• 旋转前，需要记录 subLR 节点（左子树的右子树）的平衡因子。旋转后，需要根据 subLR 的平衡因子来决定父节点、subL（左子树）和 subLR 的平衡因子如何调整：
• 如果 subLR 的平衡因子为 0，由 subLR 左子树右子树分给 parent 和 subL 的左右子树高度相同，则所有节点的平衡因子重置为 0。
• 如果 subLR 的平衡因子为 1，表示 subLR 的右子树会比左子树低 1，subLR 左子树会分配给 subL 作为右子树，此时 subL 左子树比分配的右子树高 1，所以 subL 的平衡因子应该更新为 -1，而右子树会分给 parent 作为左子树，两个子树高度相同，平衡因子为 0。
• 如果 subLR 的平衡因子为 -1，表示 subLR 的左子树比右子树低 1，subLR 左子树会分配给 subL 作为右子树，两个子树高度相同，subL 平衡因子更新为 0，而右子树会分给 parent 作为左子树，会比 parent 右子树低 1，所以 parent 的平衡因子应该更新为 1。

代码实现

void RotateLR(Node* parent) {
    Node* subL = parent->_left; // 左子树
    Node* subLR = subL->_right; // 左子树的右子树
    int bf = subLR->_bf; // 记录旋转前 subLR 的平衡因子
    // 第一步：对子树进行左旋
    RotateL(parent->_left);
    // 第二步：对当前节点进行右旋
    RotateR(parent);
    // 根据旋转后 subLR 的平衡因子更新平衡因子
    if (bf == 0) {
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 0;
    } else if (bf == 1) {
        subL->_bf = -1;
        subLR->_bf = 0;
        parent->_bf = 0;
    } else if (bf == -1) {
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 1;
    } else {
        assert(false); // 不应发生的情况
    }
}

右左双旋（RL 旋转）

旋转场景

右左双旋用于修复右左失衡（RL 失衡），这种情况发生在插入的节点位于右子树的左侧，导致右子树比左子树高 2，但右子树的左子树比右子树的右子树高。类似于左右双旋，这种情况不能通过一次左旋解决，必须先进行右旋（RR 旋转），再进行左旋。

操作步骤

1. 第一步：右旋
   首先对失衡节点的右子树进行一次右旋，使其符合左左失衡（LL 失衡）的结构。
2. 第二步：左旋
   然后对当前失衡节点进行一次左旋，使整个子树恢复平衡。

旋转后平衡因子的更新

• 同样，旋转前记录 subRL（右子树的左子树）的平衡因子，旋转后根据 subRL 的平衡因子来调整父节点、subR 和 subRL 的平衡因子。

代码实现

void RotateRL(Node* parent) {
    Node* subR = parent->_right; // 右子树
    Node* subRL = subR->_left; // 右子树的左子树
    int bf = subRL->_bf; // 记录旋转前 subRL 的平衡因子
    // 第一步：对右子树进行右旋
    RotateR(parent->_right);
    // 第二步：对当前节点进行左旋
    RotateL(parent);
    // 根据旋转后 subRL 的平衡因子更新平衡因子
    if (bf == 0) {
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = 0;
    } else if (bf == 1) {
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = -1;
    } else if (bf == -1) {
        subR->_bf = 1;
        subRL->_bf = 0;
        parent->_bf = 0;
    } else {
        assert(false); // 不应发生的情况
    }
}

AVL 树的查找

查找操作的基本原理

AVL 树是自平衡的二叉搜索树，所以查找操作与普通的二叉搜索树一致。由于 AVL 树保持了平衡，它的查找时间复杂度为 O(log N)，其中 N 是节点的数量。每次查找都是通过比较键值，沿着树的一条路径从根节点到叶节点。

查找逻辑

查找操作从根节点开始，比较目标键值（key）与当前节点的键值（cur->_kv.first）：

• 如果目标值 小于 当前节点的值，继续在左子树中查找。
• 如果目标值 大于 当前节点的值，继续在右子树中查找。
• 如果找到相等的键值，则返回该节点。
• 如果最终到达 nullptr，说明树中没有该键值，返回 nullptr。

Node* Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < key) {
            cur = cur->_right; // 查找右子树
        } else if (cur->_kv.first > key) {
            cur = cur->_left; // 查找左子树
        } else {
            return cur; // 找到目标节点
        }
    }
    return nullptr; // 未找到，返回空指针
}

AVL 树的平衡检测

平衡检测的基本原理

AVL 树的核心特性是自平衡。为了确保树的平衡，每个节点的左右子树高度差不能超过 1。因此，平衡检测的目的是检查每个节点的左右子树高度差是否满足这个条件，并验证节点的平衡因子是否正确。

平衡因子与高度计算

• 平衡因子：平衡因子是节点右子树的高度减去左子树的高度。对于 AVL 树来说，平衡因子的值只能是 -1, 0, 1。
• 高度计算：节点的高度是从该节点到叶子节点的最长路径的长度，叶子节点的高度为 0，空节点高度为 -1。

检测逻辑

1. 对每个节点，递归计算其左子树和右子树的高度。
2. 比较左右子树的高度差，确保其绝对值不超过 1。
3. 确认节点的平衡因子是否等于左右子树高度差。
4. 如果所有节点都满足条件，则该树是平衡的。

int _Height(Node* root) {
    if (root == nullptr) {
        return 0; // 空树的高度为 0
    }
    int leftHeight = _Height(root->_left); // 计算左子树的高度
    int rightHeight = _Height(root->_right); // 计算右子树的高度
    return (leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1); // 返回更大的子树高度加 1
}

bool _IsBalanceTree(Node* root) {
    // 空树也是 AVL 树
    if (root == nullptr) {
        return true;
    }
    // 计算左右子树的高度
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int diff = rightHeight - leftHeight;
    // 检查平衡因子是否正确，左右子树高度差是否超出范围
    if (abs(diff) >= 2) {
        cout << root->_kv.first << " 高度差异常" << endl;
        return false;
    }
    if (root->_bf != diff) {
        cout << root->_kv.first << " 平衡因子异常" << endl;
        return false;
    }
    // 递归检查左右子树是否平衡
    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

AVL 树旋转的时机

AVL 树的核心在于保持树的平衡性，即每个节点的平衡因子（左右子树高度差）保持在 -1、0、1 之间。当插入或删除节点后，树可能失衡，此时需要通过旋转来恢复平衡。具体的旋转方式取决于失衡的位置和失衡的类型。

1. 平衡因子更新

在插入节点后，从插入位置沿着路径向上更新每个祖先节点的平衡因子：

• 如果插入在左子树：parent->_bf--，平衡因子减 1。
• 如果插入在右子树：parent->_bf++，平衡因子加 1。

更新的过程中有三种可能情况：

• 平衡因子为 0：表示插入节点后，该节点的高度没有变化，更新可以停止。
• 平衡因子为 1 或 -1：表示节点仍然保持平衡，但高度发生变化，继续向上更新祖先节点。
• 平衡因子为 2 或 -2：表示节点失衡，需要进行旋转来恢复平衡。

2. 旋转的使用时机

当检测到某个节点的平衡因子为 2 或 -2 时，表示该节点失衡。失衡分为四种类型，具体的旋转操作取决于失衡的子树是左子树还是右子树，以及失衡的方向是左左失衡（LL）、右右失衡（RR）、左右失衡（LR） 还是 右左失衡（RL）。

2.1 左左失衡（LL 失衡） - 右单旋（RotateR）

• 情况：当节点的左子树高度过高，并且插入的新节点在左子树的左侧时，会导致左左失衡。
• 解决：需要进行右单旋（RotateR），将左子树提升为根节点。

if (parent->_bf == -2 && cur->_bf == -1) {
    RotateR(parent);
}

• 示例：

插入前： 10
       /
      5
     /
    2
插入 1 后，导致 10 左左失衡。
右旋后： 5
       / \
      2  10
     /
    1

2.2 右右失衡（RR 失衡） - 左单旋（RotateL）

• 情况：当节点的右子树高度过高，并且插入的新节点在右子树的右侧时，会导致右右失衡。
• 解决：需要进行左单旋（RotateL），将右子树提升为根节点。

if (parent->_bf == 2 && cur->_bf == 1) {
    RotateL(parent);
}

• 示例：

插入前： 10
         \
          15
           \
            20
插入 25 后，导致 10 右右失衡。
左旋后： 15
       / \
      10  20
           \
            25

2.3 左右失衡（LR 失衡） - 左右双旋（RotateLR）

• 情况：当节点的左子树高度过高，但插入的新节点在左子树的右侧时，会导致左右失衡。
• 解决：需要进行左右双旋（RotateLR），即先对左子树进行左旋，再对当前节点进行右旋。

if (parent->_bf == -2 && cur->_bf == 1) {
    RotateLR(parent);
}

• 示例：

插入前： 10
       /
      5
       \
        8
插入 9 后，导致 10 左右失衡。
左右双旋后： 8
           / \
          5  10
         /
        9

2.4 右左失衡（RL 失衡） - 右左双旋（RotateRL）

• 情况：当节点的右子树高度过高，但插入的新节点在右子树的左侧时，会导致右左失衡。
• 解决：需要进行右左双旋（RotateRL），即先对右子树进行右旋，再对当前节点进行左旋。

if (parent->_bf == 2 && cur->_bf == -1) {
    RotateRL(parent);
}

• 示例：

插入前： 10
         \
          20
         /
        15
插入 12 后，导致 10 右左失衡。
右左双旋后： 15
           / \
          10  20
         /
        12

3. 代码解释

在代码中，旋转的具体逻辑如下：

while (parent) {
    if (cur == parent->_left) {
        parent->_bf--; // 插入在左子树，平衡因子减 1
    } else {
        parent->_bf++; // 插入在右子树，平衡因子加 1
    }
    if (parent->_bf == 0) {
        break; // 平衡因子为 0，树的高度没有变化，停止更新
    } 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); // 不应发生的情况
    }
}

AVL 树节点的删除

AVL 树节点的删除较为复杂，可以选择性理解

AVL 树节点的删除操作类似于二叉搜索树的删除，但需要额外维护 AVL 树的平衡性。当删除一个节点后，可能会导致 AVL 树失衡，因此在删除节点后需要通过更新平衡因子并执行旋转来恢复平衡。

删除节点的主要步骤可以分为以下几个部分：

1. 找到要删除的节点：根据二叉搜索树的规则，找到需要删除的节点。
2. 删除节点：处理节点的删除操作，有三种情况：
   • 节点是叶子节点。
   • 节点只有一个子节点。
   • 节点有两个子节点。
3. 更新平衡因子并旋转：从删除节点的父节点开始，沿着路径向上更新平衡因子，并进行必要的旋转操作以恢复平衡。

1. 删除节点的三种情况

1.1 删除叶子节点

如果删除的节点是叶子节点，那么直接删除该节点，不需要其他调整。然后从父节点开始，检查树是否失衡。

1.2 删除只有一个子节点的节点

如果删除的节点只有一个子节点（左子节点或右子节点），那么直接用该子节点替换要删除的节点。同样，从父节点开始更新平衡因子并检查是否需要旋转。

1.3 删除有两个子节点的节点

如果删除的节点有两个子节点，则需要找到该节点的前驱节点或后继节点，并用该前驱或后继节点的值替换要删除的节点。然后，递归删除前驱或后继节点，这样问题就转化为删除一个有一个子节点或没有子节点的节点。

2. AVL 树删除的平衡维护

在删除节点后，树可能失衡，原因是删除节点后会减小某些子树的高度，从而导致其祖先节点的平衡因子发生变化。因此，需要从删除节点的父节点开始，逐级更新平衡因子，并根据情况执行旋转操作。

2.1 平衡因子的更新规则

• 如果节点被删除自左子树，其父节点的平衡因子增加 1。
• 如果节点被删除自右子树，其父节点的平衡因子减少 1。

2.2 旋转操作

和插入操作类似，删除节点后如果某个节点的平衡因子变为 2 或 -2，需要通过旋转来恢复平衡。常见的失衡和旋转情况有：

• 右单旋（RR 旋转）：当左子树比右子树矮 2，并且右子树的平衡因子为正时。
• 左单旋（LL 旋转）：当右子树比左子树矮 2，并且左子树的平衡因子为负时。
• 左右双旋（LR 旋转）：当左子树比右子树矮 2，并且左子树的右子树较高时。
• 右左双旋（RL 旋转）：当右子树比左子树矮 2，并且右子树的左子树较高时。

3. 删除操作的代码实现

以下是一个 AVL 树删除节点的简化实现。

template <class K, class V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
public:
    bool Erase(const K& key) {
        Node* parent = nullptr;
        Node* cur = _root;
        // 1. 查找要删除的节点
        while (cur) {
            if (cur->_kv.first < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_kv.first > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                break;
            }
        }
        if (!cur) {
            return false; // 节点不存在
        }
        // 2. 执行删除操作
        // 如果有两个子节点
        if (cur->_left && cur->_right) {
            Node* replace = cur->_left;
            parent = cur;
            // 找到左子树的最右节点（即前驱节点）
            while (replace->_right) {
                parent = replace;
                replace = replace->_right;
            }
            // 用前驱节点替换当前节点的值
            cur->_kv = replace->_kv;
            cur = replace;
        }
        // 只有一个子节点或没有子节点
        Node* subTree = cur->_left ? cur->_left : cur->_right;
        if (!parent) {
            // 删除的是根节点
            _root = subTree;
        } else {
            if (parent->_left == cur) {
                parent->_left = subTree;
            } else {
                parent->_right = subTree;
            }
            if (subTree) {
                subTree->_parent = parent;
            }
        }
        // 删除节点
        delete cur;
        // 3. 更新平衡因子并旋转
        while (parent) {
            if (subTree == parent->_left) {
                parent->_bf++;
            } else {
                parent->_bf--;
            }
            if (parent->_bf == 1 || parent->_bf == -1) {
                break; // 高度没有发生变化，停止调整
            }
            if (parent->_bf == 2 || parent->_bf == -2) {
                // 旋转
                Rebalance(parent);
            }
            subTree = parent;
            parent = parent->_parent;
        }
        return true;
    }
private:
    // 恢复平衡的方法，根据不同情况选择旋转方式
    void Rebalance(Node* parent) {
        if (parent->_bf == 2) {
            if (parent->_right->_bf >= 0) {
                RotateL(parent); // LL 旋转
            } else {
                RotateRL(parent); // RL 旋转
            }
        } else if (parent->_bf == -2) {
            if (parent->_left->_bf <= 0) {
                RotateR(parent); // RR 旋转
            } else {
                RotateLR(parent); // LR 旋转
            }
        }
    }
    // 左旋，右旋，左右双旋，右左双旋函数省略
};

4. 删除后的旋转恢复平衡

与插入操作类似，删除节点后如果某个节点的平衡因子变为 2 或 -2，则需要进行旋转：

• 左单旋（LL 旋转）：用于修复右子树较高的情况。
• 右单旋（RR 旋转）：用于修复左子树较高的情况。
• 左右双旋（LR 旋转）：用于修复左子树较高且左子树的右子树较高的情况。
• 右左双旋（RL 旋转）：用于修复右子树较高且右子树的左子树较高的情况。

通过这些旋转操作，AVL 树可以在删除节点后保持平衡，确保树的高度始终维持在对数级别 ( O(log N) )。

5. 总结

• 删除操作：通过常规的二叉搜索树删除方法处理节点删除，但要在删除后检查树是否失衡。
• 更新平衡因子：从删除节点的父节点开始，沿着路径向上更新平衡因子。
• 旋转恢复平衡：当某个节点的平衡因子变为 2 或 -2 时，通过适当的旋转恢复树的平衡。

AVL 树的删除比插入稍微复杂，因为可能涉及前驱节点或后继节点的替换，以及删除后的平衡恢复。