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


文章目录

  • 引言
        • AVL树的关键性质
        • 为什么选择AVL树？
  • AVL树的结构
    • 节点
    • 对象的类
  • AVL树的插入
    • 检查是否为空树并处理根节点
    • 查询插入位置（非递归）
    • 插入节点并连接父节点
    • 更新平衡因子（在失去平衡的条件下进行旋转）
  • 旋转
    • 旋转的原则
    • 右单旋（R）
      • 旋转场景
      • 旋转原理
      • 操作步骤
    • 左单旋（L）
      • 旋转场景
      • 旋转原理
      • 操作步骤
    • 左右双旋（ LR旋转）
      • 旋转场景
      • 操作步骤
      • 旋转后平衡因子的更新
      • 代码实现
    • 右左双旋（RL旋转）
      • 旋转场景
      • 操作步骤
      • 旋转后平衡因子的更新
      • 代码实现
  • AVL树的查找
    • 查找操作的基本原理
    • 查找逻辑
  • AVL树的平衡检测
    • 平衡检测的基本原理
    • 平衡因子与高度计算
    • 检测逻辑
  • AVL树旋转的时机
      • 1. 平衡因子更新
      • 2. 旋转的使用时机
        • 2.1 左左失衡（LL失衡） - 右单旋（RotateR）
        • 2.2 右右失衡（RR失衡） - 左单旋（RotateL）
        • 2.3 左右失衡（LR失衡） - 左右双旋（RotateLR）
        • 2.4 右左失衡（RL失衡） - 右左双旋（RotateRL）
      • 3. 代码解释
  • AVL树节点的删除
        • 删除节点的主要步骤可以分为以下几个部分：
      • 1. 删除节点的三种情况
        • 1.1 删除叶子节点
        • 1.2 删除只有一个子节点的节点
        • 1.3 删除有两个子节点的节点
      • 2. AVL树删除的平衡维护
        • 2.1 平衡因子的更新规则
        • 2.2 旋转操作
      • 3. 删除操作的代码实现
      • 4. 删除后的旋转恢复平衡
      • 5. 总结

引言

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);  // 出现了异常情况}
}

平衡因子的更新：

  1. 更新原则
  • 平衡因⼦ = 右⼦树⾼度 - 左⼦树⾼度
  • 只有⼦树⾼度变化才会影响当前结点平衡因⼦。
  • 插⼊结点，会增加⾼度，所以新增结点在<font style="color:rgb(31,35,41);">parent</font>的右⼦树，<font style="color:rgb(31,35,41);">parent</font>的平衡因⼦<font style="color:rgb(31,35,41);">++</font>，新增结点在parent的左⼦树，<font style="color:rgb(31,35,41);">parent</font>平衡因⼦<font style="color:rgb(31,35,41);">--</font>
  • <font style="color:rgb(31,35,41);">parent</font>所在⼦树的⾼度是否变化决定了是否会继续往上更新
  1. 更新停止条件
  • 更新后<font style="color:rgb(31,35,41);">parent</font>的平衡因⼦等于<font style="color:rgb(31,35,41);">0</font>，更新中parent的平衡因⼦变化为 <font style="color:rgb(31,35,41);">-1->0</font>或者<font style="color:rgb(31,35,41);">1->0</font>，说明更新前<font style="color:rgb(31,35,41);">parent</font>⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后<font style="color:rgb(31,35,41);">parent</font>所在的⼦树⾼度不变，不会影响<font style="color:rgb(31,35,41);">parent</font>的⽗亲结点的平衡因⼦，更新结束。
  • 更新后<font style="color:rgb(31,35,41);">parent</font>的平衡因⼦等于 <font style="color:rgb(31,35,41);">1 </font>或<font style="color:rgb(31,35,41);">-1</font>，更新前更新中<font style="color:rgb(31,35,41);">parent</font>的平衡因⼦变化为<font style="color:rgb(31,35,41);">0->1</font>或者<font style="color:rgb(31,35,41);">0->-1</font>，说明更新前<font style="color:rgb(31,35,41);">parent</font>⼦树两边⼀样⾼，新增的插⼊结点后，<font style="color:rgb(31,35,41);">parent</font>所在的⼦树⼀边⾼⼀边低，<font style="color:rgb(31,35,41);">parent</font>所在的⼦树符合平衡要求，但是⾼度增加了<font style="color:rgb(31,35,41);">1</font>，会影响<font style="color:rgb(31,35,41);">parent</font>的⽗亲结点的平衡因⼦，所以要继续向上更新。
  • 更新后parent的平衡因⼦等于<font style="color:rgb(31,35,41);">2</font>或<font style="color:rgb(31,35,41);">-2</font>，更新前更新中<font style="color:rgb(31,35,41);">parent</font>的平衡因⼦变化为<font style="color:rgb(31,35,41);">1->2</font>或者<font style="color:rgb(31,35,41);">-1->-2</font>，说明更新前<font style="color:rgb(31,35,41);">parent</font>⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，<font style="color:rgb(31,35,41);">parent</font>所在的⼦树⾼的那边更⾼了，破坏了平衡，<font style="color:rgb(31,35,41);">parent</font>所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：
    1. 把<font style="color:rgb(31,35,41);">parent</font>⼦树旋转平衡。
    2. 降低<font style="color:rgb(31,35,41);">parent</font>⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。

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

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

旋转

旋转的原则

  1. 保持搜索树的规则
  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;
}
  1. 将parent的左子树（即subL）提升为新的根节点。
  2. 将subL的右子树（即subLR，subL的右子树是parent左子树中最大的节点，对于右子树来说是最小的节点，所以用来做parent的左子树用来保持搜索树的规则）链接为parent的左子树。
  3. 将subL的右子树设置为parent。
  4. 如果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;
}
  1. 将parent的右子树（即subR）提升为新的根节点。
  2. 将subR的左子树（即subRL，subR的左子树是parent右子树中最小的节点，对于左子树来说是最大的节点，所以用来做parent的右子树用来保持搜索树的规则）链接为parent的右子树。
  3. 将subR的左子树设置为parent。
  4. 如果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(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. 对每个节点，递归计算其左子树和右子树的高度。
  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树的删除比插入稍微复杂，因为可能涉及前驱节点或后继节点的替换，以及删除后的平衡恢复。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1553133.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

基于ssm的学生社团管理系统 社团分配系统 社团活动调度平台 学生社团管理 信息化社团管理开发项目 社团活动管理 社团预约系统（源码+文档+定制）

基于ssm的学生社团管理系统 社团分配系统 社团活动调度平台 学生社团管理 信息化社团管理开发项目 社团活动管理 社团预约系统（源码+文档+定制）

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…
阅读更多...
VMware中Ubuntu系统Docker正常运行但网络不通（已解决）

VMware中Ubuntu系统Docker正常运行但网络不通（已解决）

问题描述&#xff1a;在VMware中的Ubuntu系统下部署了Docker&#xff0c;当在docker容器中运行Eureka微服务时&#xff0c;发现Eureka启动正常&#xff0c;但无法通过网页访问该容器中Eureka。 解决办法如下&#xff1a; 1、创建桥接网络&#xff1a;test-net sudo docker n…
阅读更多...
一文带你入门客制化键盘，打造专属打字利器

一文带你入门客制化键盘，打造专属打字利器

我用过不少键盘&#xff0c;但是都不太符合自己的需求&#xff0c;最后还是走向了客制化。 客制化&#xff0c;可以理解为自定义、DIY&#xff0c;自己动手拼装出一把只属于自己的键盘。 本文会对客制化做个简单的介绍&#xff0c;旨在读者能自己简单拼装出一款键盘。 目前市…
阅读更多...
QStyle文档

QStyle文档

前言 本文翻译自Qt官方文档&#xff0c;详细介绍了各成员/类型的作用&#xff0c;包含部分示例代码。 QStyle类的内容非常庞大&#xff0c;如需快速了解类成员和使用简介&#xff0c;请参见 QStyle简介。 一、QStyle Class QStyle是一个抽象基类&#xff0c;封装了GUI的外观…
阅读更多...
OpenGL笔记之事件驱动设计将相机控制类和应用程序类分离

OpenGL笔记之事件驱动设计将相机控制类和应用程序类分离

OpenGL笔记之事件驱动设计将相机控制类和应用程序类分离 —— 2024-10-02 下午 code review! 文章目录 OpenGL笔记之事件驱动设计将相机控制类和应用程序类分离1.代码图片2.分析3.UML4.代码 1.代码图片 运行 Mouse button 1 pressed at (100, 200) Mouse dragged by (50, 50)…
阅读更多...
Spring（学习笔记）

Spring（学习笔记）

<context:annotation-config/>是 Spring 配置文件中的一个标签&#xff0c;用于开启注解配置功能。这个标签可以让 Spring 容器识别并处理使用注解定义的 bean。例如&#xff0c;可以使用 Autowired 注解自动装配 bean&#xff0c;或者使用 Component 注解将类标记为 bea…
阅读更多...
10/02赛后总结

10/02赛后总结

T1学习除法 题目传送门&#xff1a;学习除法http://bbcoj.cn/contest/1028/problem/1 说白了&#xff0c;就是检验是不是质数罢了&#xff0c;是质数输出0&#xff0c;不然输出1&#xff1b; 但是质数判断写错了 100分只有60分&#xff0c;damn #include<bits/stdc.h>…
阅读更多...
【Linux】进程间关系与守护进程

【Linux】进程间关系与守护进程

超出能力之外的事&#xff0c; 如果永远不去做&#xff0c; 那你就永远无法进步。 --- 乌龟大师 《功夫熊猫》--- 进程间关系与守护进程 1 进程组2 会话3 控制终端4 作业控制5 守护进程 1 进程组 之前我们提到了进程的概念&#xff0c; 其实每一个进程除了有一个进程 ID(P…
阅读更多...
Django5 使用pyinstaller打包成 exe服务

Django5 使用pyinstaller打包成 exe服务

首先&#xff1a;确保当前的django项目可以完美运行&#xff0c;再进行后续操作 python manage.py runserver第一步 安装 pyinstaller pip install pyinstaller第二步 创建spec 文件 pyinstaller --name manage --onefile manage.pypyinstaller&#xff1a;这是调用 PyInsta…
阅读更多...
数据异质性与数据异构性的本质和举例说明

数据异质性与数据异构性的本质和举例说明

&#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 在现代数据科学与信息技术领域&#xff0c;“数据异质性” 与 “数据异构性” 是两个常见的概念。对于初学者而言&#xff0c;明确这两个概念的本质及其间的差异至关重要。本文旨在以简明易懂的方式&am…
阅读更多...
Python笔记 - 利用装饰器设计注解体系

Python笔记 - 利用装饰器设计注解体系

认识注解 注解&#xff08;Annotation&#xff09;是一种用于为代码添加元数据的机制。这些元数据可以在运行时被访问&#xff0c;用于为代码元素&#xff08;如类、方法、字段等&#xff09;提供额外的信息或指示。 由于Python中装饰器只能装饰类和方法&#xff0c;因此也只…
阅读更多...
Mac 网络连接正常，微信可以使用，但浏览器打不开网页？

Mac 网络连接正常，微信可以使用，但浏览器打不开网页？

解决&#xff1a; Step1&#xff0c;选择&#x1f34e;图标&#xff0c;选择系统设置&#xff08;或系统偏好设置&#xff09;打开&#xff1b; Step2&#xff0c;选择网络&#xff0c;Wi-Fi Step3&#xff0c;选择详细信息&#xff1b; Step4: 选择代理&#xff0c;关闭右…
阅读更多...
3.点位管理改造-列表查询——帝可得管理系统

3.点位管理改造-列表查询——帝可得管理系统

目录 前言一、与页面原型差距1.现在&#xff1a;2.目标&#xff1a;3. 存在问题&#xff1a;所在区域和合作商ID展示的都是ID&#xff0c;而不是名称&#xff1b;同时合作商ID应改为合作商 二、修改1.重新设计SQL语句2.修改mapper层&#xff0c;使用Mybatis中的嵌套查询3.修改s…
阅读更多...
C. Tree Pruning【Codeforces Round 975 (Div. 1)】

C. Tree Pruning【Codeforces Round 975 (Div. 1)】

C. Tree Pruning (永远不知道为什么TLE直到把初始化的memset换成for循环 题意很简单&#xff0c;就是找到一个深度&#xff0c;使得删除最少的节点且所有的叶子节点都为这个深度。 从小到大遍历可能的深度i&#xff0c;容易知道所有 深度大于i的节点 和所有 子树最大深度小于i…
阅读更多...
操作符详解与表达式求值

操作符详解与表达式求值

目录 操作符分类 1.算数操作符 2.移位操作符&#xff08;只适用于整数范围&#xff09; &#xff08;1&#xff09;引入 &#xff08;2&#xff09;左移操作符<< &#xff08;2&#xff09;右移操作符>> 3.位操作符 4.赋值操作符 复合赋值符 5.单目操作符 5…
阅读更多...
深度优先搜索（DFS）与有向图中的唯一结点

深度优先搜索（DFS）与有向图中的唯一结点

深度优先搜索（DFS）与有向图中的唯一结点 前提与定义分析与方法伪代码与 C 代码实现解释结果在图论中，深度优先搜索（DFS）是一种用于遍历或搜索图的算法。DFS 从给定的起始结点出发，沿着图的深度方向尽可能深地搜索，直到无法继续为止，然后回溯并从未访问过的邻接结点继续…
阅读更多...
Unraid的cache使用btrfs或zfs？

Unraid的cache使用btrfs或zfs？

Unraid的cache使用btrfs或zfs&#xff1f; 背景&#xff1a;由于在unraid中添加了多个docker和虚拟机&#xff0c;因此会一直访问硬盘。然而&#xff0c;单个硬盘实在难以让人放心。在阵列盘中&#xff0c;可以通过添加校验盘进行数据保护&#xff0c;在cache中无法使用xfs格式…
阅读更多...
YOLOv11改进 | Neck篇 | YOLOv11引入Slim-Neck（轻量）

YOLOv11改进 | Neck篇 | YOLOv11引入Slim-Neck（轻量）

1. Slim-Neck介绍 摘要&#xff1a;目标检测是计算机视觉中重要的下游任务。 对于车载边缘计算平台来说&#xff0c;巨大的模型很难达到实时检测的要求。 而且&#xff0c;由大量深度可分离卷积层构建的轻量级模型无法达到足够的精度。 我们引入了一种新的轻量级卷积技术 GSCon…
阅读更多...
【顺序查找】

【顺序查找】

目录 一. 顺序查找的概念二. 查找的性能计算 \quad 一. 顺序查找的概念 \quad \quad 二. 查找的性能计算 \quad
阅读更多...
使用ROCm的GPU感知MPI

使用ROCm的GPU感知MPI

GPU-aware MPI with ROCm — ROCm Blogs (amd.com) 注意: 此博客之前是 AMD Lab Notes博客系列的一部分。 MPI&#xff08;消息传递接口&#xff09;是高性能计算中进程间通信的事实标准。MPI进程在其本地数据上进行计算&#xff0c;同时进行大量的相互通信。这使得MPI程序可以…
阅读更多...
最新文章

Copyright @ 2022~2023