【C++】平衡二叉树(AVL树)的实现

2024-06-22 11:52
文章标签 二叉树 c++ 实现 平衡 avl

本文主要是介绍【C++】平衡二叉树(AVL树)的实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 一、AVL树的概念
  • 二、AVL树的实现
    • 1、AVL树的定义
    • 2. 平衡二叉树的插入
      • 2.1 按照二叉排序树的方式插入并更新平衡因子
      • 2.2 AVL树的旋转
        • 2.2.1 新节点插入较高左子树的左侧(LL平衡旋转)
        • 2.2.2 新节点插入较高右子树的右侧(RR平衡旋转)
        • 2.2.3 新节点插入较高左子树的右侧(LR平衡旋转)
        • 2.2.4 新节点插入较高右子树的左侧(RL平衡旋转)
        • 2.2.5 总结
    • 3 平衡二叉树的删除(了解即可)
    • 4 平衡二叉树的验证
  • 三、平衡二叉树的效率分析

一、AVL树的概念

二叉排序树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。
为了避免树的高度增长过快,降低二叉排序树的性能,规定在插入和删除结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树,也称AVL树。

一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)在这里插入图片描述

二、AVL树的实现

1、AVL树的定义

AVL树结点的定义:

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;		// 使用三叉链方便后续处理,但要记得维护pair<K, V> _kv;					// 保存键值对int _bf;						// 平衡因子
};

2. 平衡二叉树的插入

2.1 按照二叉排序树的方式插入并更新平衡因子

AVL树就是在二叉排序树的基础上加上了平衡因子,因此AVL树也可以看成是二叉排序树。那么AVL树的插入过程可以分为两步:
(1) 按照二叉排序树的方法插入新结点
(2) 调整结点的平衡因子

bool Insert(const pair<K, V>& kv)
{// 先按照二叉排序树的方法进行结点插入if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while(cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 新结点插入后,AVL树的平衡性可能会遭到破坏,此时就需要更新平衡因子,并检测是否// 破坏了AVL树的平衡性while (parent){/*cur插入后,parent的平衡因子一定需要调整,在插入之前,parent的平衡因子分为三种情况:-1,0, 1, 分以下两种情况:1. 如果cur插入到parent的左侧,只需给parent的平衡因子-1即可2. 如果cur插入到parent的右侧,只需给parent的平衡因子+1即可*/if (parent->_left == cur){--parent->_bf;}else{++parent->_bf;}/*此时:parent的平衡因子可能有三种情况:0,正负1, 正负21. 如果parent的平衡因子为0,说明插入之前parent的平衡因子为正负1,插入后被调整成0,此时满足AVL树的性质,插入成功2. 如果parent的平衡因子为正负1,说明插入前parent的平衡因子一定为0,插入后被更新成正负1,此时以parent为根的树的高度增加,需要继续向上更新3. 如果parent的平衡因子为正负2,则parent的平衡因子违反平衡树的性质,需要对其进行旋转处理*/if (0 == parent->_bf){break;}else if (1 == parent->_bf || -1 == parent->_bf){cur = cur->_parent;parent = parent->_parent;}else if (2 == parent->_bf || -2 == parent->_bf){// 旋转处理}else{// 如果平衡因子不是以上几种情况,说明代码逻辑错误assert(false);}}return true;
}

2.2 AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡化。根据节点插入位置的不同,AVL树的旋转分为四种:LL平衡旋转(右旋),RR平衡旋转(左旋),LR平衡旋转(先左旋后右旋),RL平衡旋转(先右旋后左旋)

2.2.1 新节点插入较高左子树的左侧(LL平衡旋转)

在这里插入图片描述
上图在插入前,AVL树是平衡的,新节点插入到30的左子树(注意:此处不是左孩子)中,30左子树增加了一层,导致以60为根的二叉树不平衡,要让60平衡,只能将60左子树的高度减少一层,右子树增加一层,即将左子树往上提,这样60转下来,因为60比30大,只能将其放在30的右子树,而如果30有右子树,右子树根的值一定大于30,小于60,只能将其放在60的左子树,旋转完成后,更新节点的平衡因子即可。

在旋转过程中,有以下几种情况需要考虑:

  1. 30节点的右孩子可能存在,也可能不存在
  2. 60可能是根节点,也可能是子树
    如果是根节点,旋转完成后,要更新根节点
    如果是子树,可能是某个节点的左子树,也可能是右子树
void RotateR(Node* parent)
{// subL:parent的左孩子// subLR:parent的左孩子的右孩子,注意:该点可能不存在Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;Node* ppnode = parent->_parent;		// 记录parent的父结点,用于连接新的子树parent->_parent = subL;if (subLR){subLR->_parent = parent;}if (ppnode == nullptr){_root = subL;_root->_parent = nullptr;}else {if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}// 根据调整后的结构更新部分节点的平衡因子subL->_bf = parent->_bf = 0;
}
2.2.2 新节点插入较高右子树的右侧(RR平衡旋转)

在这里插入图片描述
具体实现参考右旋即可。

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;subR->_left = parent;parent->_right = subRL;Node* ppnode = parent->_parent;		// 记录parent的父结点parent->_parent = subR;if (subRL){subRL->_parent = parent;}if (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = subR->_bf = 0;
}
2.2.3 新节点插入较高左子树的右侧(LR平衡旋转)

在这里插入图片描述
将双旋变成单旋后再旋转,即:先对30进行左单旋,然后再对90进行右单旋,旋转完成后再考虑平衡因子的更新。

void RotateLR(Node* parent)
{// subL:parent的左孩子// subLR:parent的左孩子的右孩子,注意:该点可能不存在Node* subL = parent->_left;Node* subLR = subL->_right;// 旋转之前,保存pSubLR的平衡因子,旋转完成之后,需要根据该平衡因子来调整其他节点的平衡因子int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (1 == bf){subL->_bf = -1;}else if (-1 == bf){parent->_bf = 1;}
}
2.2.4 新节点插入较高右子树的左侧(RL平衡旋转)

在这里插入图片描述
参考右左双旋。

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (1 == bf){parent->_bf = -1;}else if (-1 == bf){subR->_bf = 1;}
}
2.2.5 总结

假如以parent为根的子树不平衡,即parent的平衡因子为2或者-2,分以下情况考虑:

  1. parent的平衡因子为2,说明parent的右子树高,设parent的右子树的根为subR
    当subR的平衡因子为1时,执行左单旋
    当subR的平衡因子为-1时,执行右左双旋
  2. parent的平衡因子为-2,说明parent的左子树高,设parent的左子树的根为subL
    当subL的平衡因子为-1是,执行右单旋
    当subL的平衡因子为1时,执行左右双旋

旋转完成后,原parent为根的子树个高度降低,已经平衡,不需要再向上更新。

3 平衡二叉树的删除(了解即可)

因为AVL树也是二叉排序树,可按照二叉排序树的方式将节点删除,然后再更新平衡因子,只不错与删除不同的时,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。
平衡二叉树删除操作的具体步骤:

  1. 先按照二叉排序树的方式删除结点
  2. 一路向上找到最小不平衡子树,找不到就结束
  3. 找最小不平衡子树下,最高的儿子和孙子
  4. 根据孙子的位置,调整平衡
    • 孙子在LL:右单旋
    • 孙子在RR:左单旋
    • 孙子在LR:先左旋再右旋
    • 孙子再RL:先右旋再左旋
  5. 如果不平衡向上传导,继续第二步
    • 对最小不平衡子树的旋转可能导致树变矮,从而导致上层祖先不平衡

4 平衡二叉树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:

  1. 验证其为二叉搜索树
    如果中序遍历可得到一个有序的序列,就说明为二叉搜索树
  2. 验证其为平衡树
    • 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
    • 节点的平衡因子是否计算正确
// 求二叉树的高度
int _Height(Node* root)
{if (root == nullptr){return 0;}int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;
}
// 验证平衡树
bool _Isbalance(Node* root)
{if (root == nullptr){return true;}int leftH = _Height(root->_left);int rightH = _Height(root->_right);if (rightH - leftH != root->_bf){cout << root->_kv.first << "结点平衡因子异常" << endl;return false;}return rightH - leftH < 2&& _Isbalance(root->_left)&& _Isbalance(root->_right);
}

三、平衡二叉树的效率分析

在平衡二叉树上进行查找的过程与二叉排序树相同。因此,在查找过程中,进行关键字的比较次数不超过树的深度。假设以 n h n_h nh表示深度为h的平衡二叉树中含有的最少结点数。 n 0 = 0 , n 1 = 1 , n 2 = 2 n_0=0,n_1=1,n_2=2 n0=0,n1=1,n2=2,并且有 n h = n h − 2 + n h − 1 + 1 n_h=n_{h-2}+n_{h-1}+1 nh=nh2+nh1+1含有n个结点的平衡二叉树的最大深度为 O ( l o g 2 n ) O(log_2n) O(log2n),因此平均查找效率为 O ( l o g 2 n ) O(log_2n) O(log2n)
但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。

这篇关于【C++】平衡二叉树(AVL树)的实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1084218

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount