当前位置： 首页 > ai >正文

【重走C++学习之路】16、AVL树

ai 2025/7/18 14:32:51

目录

一、概念

二、AVL树的模拟实现

2.1 AVL树节点定义

2.2 AVL树的基本结构 

2.3 AVL树的插入

1. 插入步骤

2. 调节平衡因子

3. 旋转处理 

 4. 开始插入

2.4 AVL树的查找

2.5 AVL树的删除

1. 删除步骤

2. 调节平衡因子

3. 旋转处理

4. 开始删除

结语

一、概念

二叉搜索树查找效率为O(logN)，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率变为O(N)，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1(超过则需要对树中的节点进行调整)，即可降低树的高度，从而减少平均搜索长度。

AVL树具有以下特点：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/01)

平衡因子的取值由自己规定，在这里为了模拟实现，规定左子树的高度在根结点中为负值，右子树的高度在根结点中为正值，即平衡因子= 右子树高度 - 左子树高度。

二、AVL树的模拟实现

2.1 AVL树节点定义

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;    // 该节点的左孩子AVLTreeNode<K, V>* _right;   // 该节点的右孩子AVLTreeNode<K, V>* _parent;  // 该节点的父结点pair<K, V> _kv;int _bf;                     // 该节点的平衡因子AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

2.2 AVL树的基本结构 

template <class K, class V>
class AVLTree
{typedef AVTreeNode<K, V> Node;
public:bool Insert(const std::pair<K, V>& kv)；bool Find(const K& key)；bool Erase(const K& key)；private:Node* _root = nullptr;
};

2.3 AVL树的插入

1. 插入步骤

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子

2. 调节平衡因子

插入节点后，会影响该节点到根节点这一条路径上节点的平衡因子，因此需要进行迭代，将这一条路径上的平衡因子更新。

步骤：

第一步： 对插入的节点的父节点进行更新，会发生两种情况：

  1. 如果插入的是根节点，则无父节点，不用更新。
  2. 如果插入的是父节点的左节点，则父节点的平衡因子-1；如果插入的是父节点的右节点，则父节点的平衡因子+1。

第二步： 父节点的平衡因子在插入节点后会有三种变化，也对应着三种措施：

  1. 父节点的平衡因子变为0，则说明在插入前两颗子树高度相差1，插入后整体的高度没有发生变化，不需要向上继续调整。
  2. 父节点的平衡因子变为-1或1，则说明在插入前两颗子树高度相等，插入后整体的高度+1，需要对父节点的父节点的平衡因子进行更新，这样就回到了步骤一。
  3. 父节点的平衡因子变为-2或2，则说明在插入前两个子树高度相差1，且插入的节点为高度较高的那颗子树的叶子节点，这导致了高度相差变为2，需要进行旋转处理，降低树的高度，从而达到平衡整颗树的要求。

图解：

第一种情况：

第二种情况：

可以看到这里在更新平衡因子的时候，只会影响节点到根节点路径上的节点的平衡因子，其它的节点不需要考虑。

第三种情况：

更新平衡因子的时候，发现不满足规则后，直接停止更新，转而进行旋转处理。

3. 旋转处理 

旋转有四种情况：

第一种情况：右单旋

新节点插入到较高左子树的左侧，左侧的高度变高需要将右边的调整下来，因此叫做右单旋。

具体操作：

让subL的右孩子成为parent的左孩子，然后让parent成为subL的右孩子，最后把两个节点的平衡因子修改为0。

 图解：

实现代码：

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 1.先让把subL的右边作为parent的左边parent->_left = subLR;// 2.如果subLR不为空，就让subLR的父指针指向parentif (subLR) subLR->_parent = parent;// 3.记录parent的父节点的位置，然后把parent作为subL的右边Node* pParent = parent->_parent;subL->_right = parent;// 4.parent的父指针指向subLparent->_parent = subL;// 5.如果ppNode为空，说明subR现在是根节点，就让subL的父指针指向nullptr//   不是根节点就把subL的父指针指向parent的父节点，parent的父节点（左或右）指向subLif (pParent == nullptr){// 更新根节点_root = subL;subL->_parent = nullptr;}else{// 判断parent是pparent的左还是右if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;subL->_parent = pParent;}// 6.把parent和subL的平衡因子更新为0subL->_bf = parent->_bf = 0;
}

第二种情况：左单旋 

新节点插入到较高右子树的右侧，右侧的高度变高需要将左边的调整下来，因此叫做右单旋。

 具体操作：

让subR的左孩子成为parent的右孩子，然后让parent成为subR的左孩子，最后把两个节点的平衡因子修改为0。

图解：

实现代码：

void RotateL(Node* parent)
{		Node* subR = parent->_right;Node* subRL = subR->_left;// 1.先让把subR的左边作为parent的右边parent->_right = subRL;// 2.如果subRL不为空，就让subRL的父指针指向parentif (subRL) subRL->_parent = parent;// 3.先记录parent的父节点的位置，然后把parent作为subR的左边 Node* pParent = parent->_parent;subR->_left = parent;// 4.parent的父指针指向subRparent->_parent = subR;// 5.如果ppNode为空，说明subR现在是根节点，就让subR的父指针指向nullptr//   不是根节点就把subR的父指针指向parent的父节点，parent的父节点（左或右）指向subRif (pParent == nullptr){// 更新根节点_root = subR;subR->_parent = nullptr;}else{// 判断parent是ppNode的左还是右if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;subR->_parent = pParent;}// 6.把parent和subR的平衡因子更新为0subR->_bf = parent->_bf = 0;
}

第三种情况：左右双旋 

新节点插入在较高左子树右侧，这里和第一种情况的区别就是前者是直线，后者是折线

具体操作：

先对subL进行一个左单旋，然后对parent进行右单旋，修改平衡因子，有三种改法。三个节点从左至右的三个节点一次是：subL、subLR和parent。
如果subLR的平衡因子为0，就将它们依次改为0，0, 0；
如果subLR的平衡因子为1，就将它们依次改为-1，0, 0；
如果subLR的平衡因子为-1，就将它们依次改为0，0, 1。

图解：（这里只画出了一种情况，剩下的类似）

实现代码：

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;// 保留subLR的平衡因子的值，方便知道新插入的节点是在subLR的左子树还是右子树// 旋转 先对subL进行左旋转，再对parent进行右旋转RotateL(subL);RotateR(parent);// 从左到右 subL subLR parentif (bf == -1)// subLR的左子树  bf: 0 0 1{subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1)// subLR的右子树 bf: -1 0 0{subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}
}

第四种情况：右左单旋 

新节点插入在较高右子树左侧，这里和第二种情况的区别就是前者是直线，后者是折线

 具体操作：

先对subR进行一个右单旋，然后对parent进行左单旋，修改平衡因子，有三种改法。三个节点从左至右的三个节点一次是：parent、subRL和subR。
如果subRL的平衡因子为0，就将它们依次改为0，0, 0；
如果subRL的平衡因子为1，就将它们依次改为-1，0, 0；
如果subRL的平衡因子为-1，就将它们依次改为0，0, 1。

图解：（这里只画出了一种情况，剩下的类似）

实现代码：

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;// 保留subRL的平衡因子的值，方便知道新插入的节点是在subRL的左子树还是右子树// 旋转 先对subR进行右旋转，再对parent进行左旋转RotateR(subR);RotateL(parent);// 从左到右 parent subRL subRif (bf == -1)// subRL的左子树  bf: 0 0 1{parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1)// subRL的右子树 bf: -1 0 0{parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}
}

 4. 开始插入

bool Insert(const pair<K, V>& kv)
{// 先按照二叉搜索数一样插入元素// 无节点是插入if (_root == nullptr){_root = new Node(kv);return true;}// 有节点时插入Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;// 小于往左走if (kv.first < cur->_kv.first){cur = cur->_left;}// 大于往右走else if (kv.first > cur->_kv.first){cur = cur->_right;}else{// 找到了，就返回falsereturn false;}}cur = new Node(kv);// 判断cur应该插在parent的左还是右 // 小于在左，大于在右		if (cur->_kv.first < parent->_kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}// 更新parent的平衡因子// 节点的插入只会影响cur的祖先的平衡因子（不是所有的，是一部分，分情况）while (parent){// 更新parent的平衡因子// cur在parent的左，parent->_bf--// cur在parent的右，parent->_bf++if (cur == parent->_left)parent->_bf--;elseparent->_bf++;// bf 可能为 -2、-1、0、1、2if (parent->_bf == 0){// 对上层无影响，退出break;}else if (parent->_bf == -1 || parent->_bf == 1){// 对上层有影响，迭代更新cur = parent;parent = parent->_parent;}else{// 平衡树出现了问题，需要调整// 1.右边高，左旋转调整if (parent->_bf == 2){// 如果是一条直线==>左旋转即可// 如果是一条折线==>右左旋转if (cur->_bf == 1)RotateL(parent);else if (cur->_bf == -1)RotateRL(parent);}// 2.左边高，右旋转调整else if (parent->_bf == -2){// 如果是一条直线==>右旋转即可// 如果是一条折线==>左右旋转if (cur->_bf == -1)RotateR(parent);else if (cur->_bf == 1)RotateLR(parent);}// 调整后是平衡树，bf为0，不需要调整了break;}}return bool;
}

2.4 AVL树的查找

与二叉搜索树的过程一致，这里就不多解释了，直接上代码：

bool Find(const K& key)
{if (_root == nullptr)return false;Node* cur = _root;while (cur){// 小于往左走if (key < cur->_kv.first){cur = cur->_left;}// 大于往右走else if (key > cur->_kv.first){cur = cur->_right;}else{// 找到了return true;}}return false;
}

2.5 AVL树的删除

1. 删除步骤

  1. 我们先按照二叉搜索树树删除节点的方式，删除节点。
  2. 根据对应删除情况更新平衡因子，更新平衡因子的方法与插入的更新方法是相反的。

2. 调节平衡因子

步骤：

第一步：

  1. 删除节点后，如果删除的节点为根节点，就结束。
  2. 如果删除节点是父节点的左孩子，那么父节点的平衡因子加1；删除节点是父节点的右孩子，那么父节点的平衡因子减1。

第二步：父节点的平衡因子在插入节点后会有三种变化，也对应着三种措施：

  1. 父节点的平衡因子变为0，则说明删除前父亲的平衡因子为1或-1，多出一个左节点或右节点，删除节点后，左右高度相等，整体高度减1，对上层有影响，需要继续调节。
  2. 父节点的平衡因子变为-1或1，则说明删除前父亲的平衡因子为0，左右高度相等，删除节点后，少了一个左节点或右节点，但是整体高度不变，对上层无影响，不需要继续调节。
  3. 父节点的平衡因子变为-2或2，则说明删除前父亲的平衡因子为-1或1，多了一个左节点或一个右节点，删除了一个右节点或左节点，此时多了两个左节点和右节点，这棵子树一边已经被拉高了，此时这棵子树不平衡了，需要旋转处理。

3. 旋转处理

这里的旋转与插入时旋转的没有区别，就不详细解答了，直接上代码。

4. 开始删除

bool Erase(const K& key)
{if (_root == nullptr)return false;// 有节点时插入Node* parent = nullptr;Node* cur = _root;while (cur){// 小于往左走if (key < cur->_kv.first){parent = cur;cur = cur->_left;}// 大于往右走else if (key > cur->_kv.first){parent = cur;cur = cur->_right;}else{// 找到了// 1.左边为空，把parent指向cur的右// 2.右边为空，把parent指向cur的左// 3.左右都不为空，用右子树的最左边的节点的值替换要删除的节点，然后转换为用1的情况删除该节点if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;delete cur;break;}else{if (parent->_left == cur){parent->_left = cur->_right;parent->_bf++;}else{parent->_right = cur->_right;parent->_bf--;}}if (parent->_bf != -1 && parent->_bf != 1) UpdateBf(parent);delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;delete cur;break;}else{if (parent->_left == cur){parent->_left = cur->_left;parent->_bf++;}else{parent->_right = cur->_left;parent->_bf--;}}if (parent->_bf != -1 && parent->_bf != 1) UpdateBf(parent);delete cur;}else{Node* rightMinParent = cur;Node* rightMin = cur->_right;// 先去右子树while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;// 一种往左走}cur->_kv = rightMin->_kv;// 替代删除// 删除minNode  第一种情况：左节点为空if (rightMinParent->_left == rightMin){rightMinParent->_left = rightMin->_right;rightMinParent->_bf++;}else{rightMinParent->_right = rightMin->_right;rightMinParent->_bf--;}if (rightMinParent->_bf != -1 && rightMinParent->_bf != 1)                 UpdateBf(rightMinParent);delete rightMin;}return true;}}return false;
}void UpdateBf(Node* parent)
{if (parent == nullptr)return;Node* cur = parent;goto first;while (parent){// 更新parent的平衡因子// cur在parent的左，parent->_bf++// cur在parent的右，parent->_bf--if (cur == parent->_left)parent->_bf++;elseparent->_bf--;// bf 可能为 -2、-1、0、1、2first:if (parent->_bf == 0){// 对上层有影响，迭代更新// 如果parent是根节点就结束if (parent->_parent == nullptr)break;cur = parent;parent = parent->_parent;}else if (parent->_bf == -1 || parent->_bf == 1){// 对上层无影响，退出break;}else{// 平衡树出现了问题，需要调整// 1.右边高，左旋转调整if (parent->_bf == 2){// 如果是一条直线==>左旋转即可// 如果是一条折线==>右左旋转if (parent->_right->_bf == 1){RotateL(parent);cur = parent->_parent;parent = cur->_parent;continue;}else if (parent->_right->_bf == -1)// 调整后 p sL s  如果sL是1或-1可以退出 {Node* s = parent->_right;Node* sL = s->_left;RotateRL(parent);// 不平衡向上调整if (sL->_bf != 1 && sL->_bf != -1){cur = sL;parent = cur->_parent;continue;}}else if (parent->_right->_bf == 0)    // 平衡因子修改{RotateL(parent);parent->_bf = 1;parent->_parent->_bf = -1;}}// 2.左边高，右旋转调整else if (parent->_bf == -2){// 如果是一条直线==>右旋转即可// 如果是一条折线==>左右旋转if (parent->_left->_bf == -1){RotateR(parent);cur = parent->_parent;parent = cur->_parent;continue;    //parent不是-1或1就继续}else if (parent->_left->_bf == 1)// 调整后 s sR p  如果sL是1或-1可以退出{Node* s = parent->_left;Node* sR = s->_right;RotateLR(parent);// 不平衡向上调整 为0时如果parent为根//if (sR->_bf != 1 && sR->_bf != -1){cur = sR;parent = cur->_parent;continue;}}else if (parent->_left->_bf == 0)    // 平衡因子修改{RotateR(parent);parent->_parent->_bf = 1;parent->_bf = -1;}}// 调整后是平衡树，bf为1或-1，不需要调整了break;}}
}

结语

上面这些是AVL树的大致内容，其中旋转是有些难的地方，但是面试会考察，需要着重掌握，而删除是二叉搜索树的删除加上旋转的叠加，难度更上一层了，这里如果没能理解，可以自己画一画图，并且配合着插入的图来分析，应该会有所帮助。

下一篇将会介绍二叉搜索树的另一种改良：红黑树，有兴趣的朋友可以关注一下。

http://www.xdnf.cn/news/1179.html

相关文章：

  • Java练习——day3
  • qemu如何支持vmovdqa64指令（百度AI)
  • 游戏工作室为何要更换IP进行多开？工作室使用代理IP要注意什么？
  • 35.编写一个简单的Mybatis插件
  • ​​电商系统用户需求报告（示例）
  • 随着ai技术的应用，及玩具类产品的层出不穷，开发此类产品的情感AI算法技术的底层构架，及情感AI算法的应用场景是转型的比较好的一个方向
  • HTTP状态码有哪些常见的类型？
  • 三网通电玩城平台系统结构与源码工程详解（四）：子游戏集成与服务器调度机制全解
  • Spring AOP + Logback + MDC全链路日志追踪
  • 三线服务器通常适用于哪些用户？
  • GPIO（通用输入输出端口）详细介绍
  • 【T2I】TOKENCOMPOSE: Text-to-Image Diffusion with Token-level Supervision
  • 【2025最新面试Java八股】Java虚拟线程怎么回事，是协程吗？
  • 解决开启代理时无法正常使用Microsoft Store, OneDrive, Outlook等应用的问题
  • 构建“穿戴+云端”落水应急响应体系，为海上作业人员打造全天候、全场景的安全守护网
  • 三网通电玩城平台系统结构与源码工程详解（三）：控制台与银商权限模块设计
  • 互联网大厂Java面试：从基础到进阶的技术点探讨
  • 108. 将有序数组转换为二叉搜索树
  • Python——入门... ...
  • 突破 RAG 检索瓶颈：Trae+MCP 构建高精度知识库检索系统实践
  • 嘻游组件解密工具实战教程：资源解包与UI替换全流程
  • 一目十行阅读法
  • 航电系统自适应与容错机制要点
  • Git ——提交至github，Vercel拉取，更新不了项目的问题解决
  • LOH 怎么进行深度标准化？
  • （15）VTK C++开发示例 --- 生成随机数的首选方法
  • 【读论文】HM-RAG：分层多智能体多模态检索增强生成
  • Spring Boot多环境配置详解
  • 通俗的理解TCP的三次握手四次挥手
  • Mysql的redolog