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

DevKevin

发布于 2024-10-03 09:41:26

11300

代码可运行

文章被收录于专栏：Base_CDNKevin

运行总次数：0

代码可运行

引言

AVL树是由Adelson-Velsky和Landis发明的第一种自平衡二叉搜索树，它通过控制每个节点左右子树的高度差（称为平衡因子）不超过1，确保树的高度维持在对数级别。这种自平衡特性使得AVL树的查找、插入和删除操作的时间复杂度保持在 O(log⁡N)O(\log N)O(logN)，从而提升效率。

AVL树的关键性质

二叉搜索树结构：AVL树是一种特殊的二叉搜索树，每个节点的平衡因子始终保持在 -1、0 或 1 之间。
平衡因子：平衡因子定义为右子树高度减去左子树高度。若某个节点的平衡因子超出此范围，则需进行旋转以恢复平衡。

为什么选择AVL树？

未平衡的二叉搜索树在最坏情况下可能退化成链表，导致操作时间复杂度增至 O(N)O(N)O(N)。AVL树通过保持树的高度平衡，保证了查找、插入和删除操作的高效性。

AVL树的结构

节点

template<class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv; // kv结构
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K，V>* _right;
	AVLTreeNode<K, V> _parent // 需要parent指针，后续更新平衡因⼦可以看到
	int _bf; // 平衡因子

	AVLTreeNode(const pair<K, V>& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};

对象的类

template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    // ...

private:
    // ...
    Node* _root = nullptr;
};

AVL树的插入

AVL树的插入按照二叉搜索树的规则进行插入，但是会在不平衡的条件下进行旋转操作。也就是说，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⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。

如下图，当插入**13**时，此时平衡因子更新，**10**的**_bf**更新为**2**使树变得不平衡，因此需要旋转处理。

如下图，插入后平衡因子一直更新到根截止：

旋转

旋转的原则

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

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

右单旋（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旋转），再进行右旋。

无法平衡

操作步骤

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

旋转后平衡因子的更新

旋转前，需要记录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旋转），再进行左旋。

操作步骤

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

旋转后平衡因子的更新

同样，旋转前记录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(logN)，其中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。
确认节点的平衡因子是否等于左右子树高度差。
如果所有节点都满足条件，则该树是平衡的。

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. 删除节点的三种情况

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树的删除比插入稍微复杂，因为可能涉及前驱节点或后继节点的替换，以及删除后的平衡恢复。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-02，如有侵权请联系 cloudcommunity@tencent.com 删除

parent

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！