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

AVLTree【c++实现】

news 2025/5/14 23:35:52

目录

  • AVL树
    • 1.AVL树的概念
    • 2.AVLTree节点的定义
    • 3.AVLTree的插入
    • 4.AVLTree的旋转
      • 4.1左单旋
      • 4.2右单旋
      • 4.3左右双旋
      • 4.4右左双旋
    • 5.AVLTree的验证
    • 6.AVLTree的性能

AVL树

AVLTree的代码实现连接：

AVLTree 代码链接

1.AVL树的概念

学习了二叉搜索树之后，我们知道二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此AVLTree就出现来解决这个问题了。

AVLTree如何解决的呢？——当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度

AVLTree也可以叫做高度平衡二叉搜索树

AVLTree的特点：

  1. 所有子树的左右子树高度差的绝对值不超过1
  2. 所有子树都是AVLTree
  3. AVLTree如果有n个节点，那么其高度保持在log_2_N，搜索的时间复杂度会保持在O(log_2_N)

image-20240926102000806

注意：

上面-1代表对于3这个节点来说，其左子树高度比右子树大1.

1代表右子树高度比左子树高度大1

0代表左右子树高度平衡

2.AVLTree节点的定义

实现AVLTree有多种办法，这里我们选择引入平衡因子。用于判断该树是否平衡

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

3.AVLTree的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

  1. 按照二叉搜索树的规则进行插入
  2. 调整平衡因子
  3. 根据平衡因子来判断是否平衡，并进行相应处理。【不平衡要旋转】

下图对平衡因子的调整的三种情况进行了分析：

image-20240926122656350

对第一种情况进行解析:

image-20240926124105840

对第二种情况进行解析:

image-20240926124804620

对第三种情况进行解析:

image-20240926124400594

下面是更新平衡因子的代码实现：

		// 更新平衡因子while (parent) // 可能会更新到根节点{// 如果插入的节点是当前parent节点的右孩子if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}// 这个时候判断parent的平衡因子的情况是否还要向上调整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){// 这种情况就代表着该parent子树已经不平衡了，要进行旋转处理}}

要完成AVLTree的插入，旋转的实现是必不可少的。

4.AVLTree的旋转

旋转就是保持树仍然是二叉搜索树的前提下，让它变成平衡二叉搜索树【旋的过程可不是乱旋的】

首先要知道什么情况需要旋转，上面也说了，这里在通过图片复习一下：

就是当树出现高度的不平衡的时候，就需要旋转。

image-20240926195046604

旋转分多种情况的旋转：

4.1左单旋

当节点插入较高的左子树的左侧的时候——左单旋

image-20240926202507470

因此根据上面两个进行左单旋的例子，我们可以总结出左单旋的两个重要规律

  1. subR的左孩子变成parent的右孩子
  2. parent会成为subR的左孩子

有了这个规律，我们就可以用一个抽象图来表示左单旋：

image-20240926202841941

可以进行左单旋的情况是非常多的。上面我们的例子就是当h为0和1的情况。

注意：

在插入前，AVL树是平衡的，新节点插入到60的右子树(注意：此处不是右孩子)中，60右子树增加了一层，导致以30为根的二叉树不平衡，要让30这课树平衡，只能将30子树的高度减少一层，左子树增加一层

即将右子树往上提，这样30转下来，因为30比60大，只能将其放在60的左子树，而如果60有左子树，左子树根的值一定大于30，小于60，只能将其放在30的右子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：

  1. 60节点的左孩子可能存在，也可能不存在

    要注意左孩子不存在时，是否存在对空指针的解引用

    如果左孩子存在，要处理其父亲指针的链接

  2. 30可能是根节点，也可能是子树

    如果是根节点，旋转完成后，要更新根节点

    如果是子树，可能是某个节点的左子树，也可能是右子树【要提前保存下parent的parent，这样才能在此时进行连接】

左单旋的代码实现如下：

	//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;// 处理关系的时候还要注意到父亲指针的变化// 1.先让subR的左孩子变成parent的右孩子，再处理subR左孩子的父亲指针parent->_right = subRL;if(subRL) // 防止当h为0时，也就是subRL的左孩子是空的情况subRL->_parent - parent; // 处理父亲指针//2.再让parent成为subR的左孩子，并处理parent的父亲指针subR->_left = parent;Node* ppNode = parent->_parent; // 防止后面subR链接不到parent->_parent，这里要做个保存parent->_parent = subR; // 处理父亲指针//3.subR的父亲指针也需要变化// 这里会有两种情况// 1.左单旋之后，subR直接是根节点if (_root = parent){// 原本parent是根节点，左单旋之后subR变成跟节点_root = subR;subR->_parent = nullptr;}else //2.parent不是根节点，左单旋完毕之后subR仍然是子树{// 这个情况说明原本parent是一个子树，左单旋后subR也是一个子树// 这个时候就要链接上原本parent的_parent，上面存储起来是ppNode// 但是这个时候还得判断左单旋之后的subR应该是ppNode的左子树还是右子树if (ppNode->_left == parent){ppNode->_left = subR;subR->_parent = ppNode;}else{// 原来的parent是ppNode的右子树,也就是subR要变成ppNode的右子树ppNode->_right = subR;subR->_parent = ppNode;}}// 左单旋之后，还得修改平衡因子，这样才算结束subR->_bf = parent->_bf = 0;}

4.2右单旋

当节点插入较高的右子树的右侧的时候——右单旋

image-20240926220741382

因此根据上面两个进行右单旋的例子，我们可以总结出右单旋的两个重要规律

  1. subR的右孩子变成parent的左孩子
  2. parent会成为subR右孩子

有了这个规律，我们就可以用一个抽象图来表示右单旋：

image-20240926220909857

上面举的两个例子就是该抽象图中，h为0或者1的情况。

注意：

在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层

即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：

  1. 30节点的右孩子可能存在，也可能不存在

    要注意右孩子不存在时，是否存在对空指针的解引用

    如果右孩子存在，要处理其父亲指针的链接

  2. 60可能是根节点，也可能是子树

    如果是根节点，旋转完成后，要更新根节点

    如果是子树，可能是某个节点的左子树，也可能是右子树【要提前保存下parent的parent，这样才能在此时进行连接】

右单旋的代码实现：

// 右单旋
void RotateR(Node* parent)
{Node* subR = parent->_left;Node* subLR = subR->_right;// 处理节点关系的时候要注意处理其父亲指针的关系// 1.先让subR的右孩子变成parent的左孩子，再处理subR右孩子的父亲指针parent->_left = subLR;if (subLR)subLR->_parent = parent;// 处理subR右孩子的父亲指针// 2.再让parent成为subR的右孩子，再处理parent的父亲指针subR->_right = parent;Node* ppNode = parent->_parent; // 防止原来的parent是子树，不是根节点parent->_parent = subR;// 处理parent的父亲指针// 3.再处理更新后的subR的父亲指针// 这里又分两种情况// 1.一种是parent原先是根节点，subR代替之后，也会变成根节点if (_root == parent){_root = subR; // subR代替之后，变成根节点subR->_parent = nullptr;}else //2.parent是原先的一个子树，左单旋完毕之后subR仍然是子树{//原来的parent是其父亲的左子树还是右子树if (parent == ppNode->_left){// subR替代之后，是ppNode的左子树ppNode->_left = subR;subR->_parent = ppNode; //处理父亲指针}else{// sub替代之后，是ppNode的右子树ppNode->_right = subR;subR->_parent = ppNode; //处理父亲指针}}//4.处理完毕之后，还要更新平衡因子，这样右单旋才是结束了subR->_bf == parent->_bf = 0;
}

4.3左右双旋

左右双旋：其实就是先左单旋，在右单旋。

当给较高的左子树插入一个右节点，就要先左单旋，在右单旋

但是这里会有两种情况

image-20240927145625985

image-20240927151925105

这里虽然有两种情况，但是都是进行左右双旋，即先对30进行左单旋，在对90进行右单旋，规律如下：

  1. 左右双旋完毕后，两种情况下，60都为根。
  2. 并且60的b给了30的右子树。60的c给了90的左子树 【因为b肯定比60小，30大】【c肯定比60大，比90小】
  3. 旋转的情况是相同的。两种情况的旋转情况都是一样的

因此左右双旋难得不是旋转，难得是平衡因子的调节。两种情况的平衡因子是不一样的。

image-20240927155540410

并且除了上述两种情况下，还有一种情况也需要对平衡因子特殊处理：

也就是a b c d四个区域都是空的，60节点的插入本身

image-20240927170247360

一共有三种情况，这三种情况的平衡因子都需要进行不同的处理。

因此判断是那种情况并做出相应的平衡因子调节成为了一个重点

代码实现如下：

这里对parent、subL、subLR的位置给个图片，方便代码理解

image-20240927170440609

	// 左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf; // 先记载下来subLR节点的平衡因子，防止被后面的双旋进行干扰// 左右双旋 【双旋无关节点的插入情况，旋转都是一样的】RotateL(subL);Rotatel(parent);// 旋转之后需要对三种不同情况的平衡因子进行处理// 这里我们通过前面保存的subRL的平衡因子bf来区分节点是插入b还是c,还是abcd四个区域都为空。// 这里的a b c d要结合图片理解【博客或者笔记】if (bf == -1){// 节点插入b区域// 此时subLR成为了根节点或者是整棵树的其中一颗子树// parent旋转后的bf == 1, subL的bf == 0parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){// 节点插入区域c// 此时subLR成为了根节点或者是整棵树的其中一颗子树// parent旋转后bf == 0， subL的bf == 1parent->_bf = 0;subL->_bf = 1;subLR->_bf = 0;}else // bf == 0{// 此时abcd四个区域都为空。// 旋转之后三个节点的bf都为0parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}}

4.4右左双旋

左右双旋：其实就是先左单旋，在右单旋。

当给较高的右子树插入一个左节点，就要先右单旋，在左单旋

image-20240927163346290

image-20240927164341218

这里虽然有两种情况，但是都是进行右左双旋，即先对90进行右单旋，在30进行左单旋，规律如下：

  1. 右左双旋完毕后，两种情况下，60都为根。
  2. 并且60的b给了30的右子树。60的c给了90的左子树 【因为b肯定比60小，30大】【c肯定比60大，比90小】
  3. 旋转的情况是相同的。两种情况的旋转情况都是一样的

因此双旋难得不是旋转，难得是平衡因子的调节。两种情况的平衡因子是不一样的。

image-20240927164739238

并且除了上述两种情况下，还有一种情况也需要对平衡因子特殊处理：

image-20240927163144848

一共有三种情况，这三种情况的平衡因子都需要进行不同的处理。

因此判断是那种情况并做出相应的平衡因子调节成为了一个重点

代码实现如下：

这里对parent、subR、subRL的位置给个图片，方便代码理解

image-20240927162222997

	// 右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf; // 防止后面的双旋对subRL的平衡因子进行干扰// 右左双选的两种情况都是，先右单旋，再左单旋RotateR(subR);RotateL(parent);// 重点是要控制三种情况的平衡因子// 这里我们通过前面保存的subRL的平衡因子bf来区分节点是插入b还是c,还是abcd四个区域都为空。// 这里的a b c d要结合图片理解【博客或者笔记】if (bf == 1){// 节点插入c区域// 这种情况下，最后subRL成为了根节点或者是其中一个子树// 此时parent在旋转之后的平衡因子是-1，subR是0parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){// 节点插入b区域// 这个情况下，最后subRL成为了根节点或者是其中一个子树// 此时subR的平衡因子是1，parent是0parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else // 此时bf == 0{//这种情况是a、b、c、d四个区域都为空。// 刚好插入的节点构成了引发双旋的条件parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}}

5.AVLTree的验证

要验证AVLTree，需要验证两个方面：

  1. 首先是一个二叉搜索树【通过中序遍历，查看是否有序】
  2. 高度必须要平衡
  • 验证是否为一个二叉搜索树——通过中序遍历即可：
	// 中序遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ": " << root->_kv.second << " " << endl;_InOrder(root->_right);}//cpp中一般实现递归都要通过子函数// 因为外边调用这个中序遍历接口的时候没办法直接传一个_root进来，_root是私有的void InOrder(){if (_root == nullptr){cout << "该树为空" << endl;return;}_InOrder(_root);//_InOrder(this->_root); // 等价于上面的cout << endl;}
  • 验证高度是否平衡：

这里两个方案：

  1. 树的左右子树的高度差的绝对值要<2，就意味着当前树平衡。然后每个左右子树的高度差都 < 2就意味是AVLTree。

  2. 计算当前根节点的平衡因子，将其与根节点存的平衡因子对比。如果相同，就意味着当前树平衡，如果每个子树的平衡因子都不出错，就意味着是AVLTree

	int Height(Node* root){if (root == nullptr)return 0;// 记载左右子树的高度int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);//对于当前层数的根节点来说，左右子树大的那个高度+1，才是这棵树的高度return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool _IsBanlance(Node* root){if (root == nullptr)return true;// 计算出左右子树的高度int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);// 如果左右子树高度差的绝对值 < 2 并且 每个左右子树都是满足其左右子树高度差的绝对值<2的话，就是平衡的return abs(rightHeight - leftHeight) < 2 && _IsBanlance(root->_left) && _IsBanlance(root->_right);// 也可以通过判断平衡因子是否相同，rightHeight - leftHeight计算出当前根节点的平衡因子bf，将其与root->_bf对比。// 将每个子树的平衡因子都进行一个对比，如果都是对的，意味着这棵树平衡//int bf = rightHeight - leftHeight; // 自己计算的平衡因子//return bf == root->_bf && _IsBanlance(root->_left) && _IsBanlance(root->_right);}bool IsBanlance(){if (_root == nullptr){cout << "该树为空\n";return false;}return _IsBanlance(_root);}
  • 测试用例：
void test_AVLTree()
{int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int b[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> avl1;AVLTree<int, int> avl2;for (auto e : a){avl1.insert(pair<int, int>(e, e));}avl1.InOrder(); // 验证此树为二叉搜索树// 还得验证高度是否为AVLTree————是否平衡cout << avl1.IsBanlance() << endl; // 1cout << endl;for (auto e : b){avl2.insert(pair<int, int>(e, e));}avl2.InOrder(); // 验证此树为二叉搜索树// 是否平衡cout << avl2.IsBanlance() << endl; // 1
}

image-20240928170023282

6.AVLTree的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log_2 (N)。

但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。


http://www.mrgr.cn/news/38592.html

相关文章：

  • 2409vim,vim写文件有问题
  • Java语法-类和对象之抽象类和接口
  • 国产动漫论坛系统小程序的设计
  • linux网络编程实战
  • 什么是SQL注入？
  • MySQL-数据库约束
  • JSON的C实现（上）
  • LeetCode讲解篇之33. 搜索旋转排序数组
  • 哈希知识点总结：哈希、哈希表、位图、布隆过滤器
  • DMA的原理
  • FPGA-Vivado-IP核-逻辑分析仪（ILA）
  • Linux 线程互斥
  • html5 + css3
  • Python精选200Tips：181-182
  • [leetcode]5_最长回文子串
  • AAMAS 24 | 基于深度强化学习的多智能体和自适应框架用于动态组合风险管理
  • 一文理解mysql 联合索引和各种SQL语句分析
  • Python语言语法基础篇
  • 微信小程序开发系列之-实战搭建一个简单的待办事项小程序
  • Time-MoE : 时间序列领域的亿级规模混合专家基础模型