C++进阶篇4---番外-AVL树

2023-11-08 05:20
文章标签 c++ 进阶篇 avl 番外

本文主要是介绍C++进阶篇4---番外-AVL树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者具有以下性质的二叉搜索树：
  • 它的左右子树都是AVL树
  • 左右子树的高度差(简称平衡因子)的绝对值不超过1(只能是-1/0/1)

【注意】平衡因子是用右子树的高度减去左子树的高度得到的

 

二、AVL树结点的定义

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

 三、AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。
AVL树的插入过程可以分为两步：
  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子
template<class K,class V>
class AVLTree {typedef AVLTreeNode<K, V> Node;
public:bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if(cur->_kv.first>kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_parent = parent;if (parent->_kv.first > kv.first ){parent->_left = cur;}else{parent->_right = cur;}//看树是否还保持平衡while (parent){//先调整平衡因子---因为插入的结点是叶子节点，所以父结点的平衡因子必然发生变化//在根据平衡因子的计算公式height_r - height_l，判断平衡因子的变化if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}//看是否需要调整以及如何调整//...}}
private:Node* _root = nullptr;
};

上面代码的插入逻辑和二叉搜索树很相似，这里不多讲了(忘记的或者不了解的可以去看二叉搜索树)，主要看如何判断树是否平衡以及如何调整使得树保持平衡

这里主要分三种情况：

1、父节点的平衡因子变成0，则树保持平衡，不需要变化

解释:父节点的平衡因子变成0，说明之前未正负1，只有如下两种情况

2、父节点的平衡因子变成正负1，则该子树的高度发生变化，但该子树依旧平衡，要看它的父节点所在的子树是否还能保持平衡

 

3、父结点的平衡因子变成正负2，则该子树的不能保持平衡，需要进行旋转调整

template<class K,class V>
class AVLTree {typedef AVLTreeNode<K, V> Node;
public:bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if(cur->_kv.first>kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_parent = parent;if (parent->_kv.first > kv.first ){parent->_left = cur;}else{parent->_right = cur;}//看树是否还保持平衡while (parent){//先调整平衡因子if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}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){//分4种情况:左单旋，右单旋，先左旋在右旋，先右旋在左旋//...//旋转完成后子树就平衡了=> 整个树都平衡了，直接退出循环break;}else{//如果进入这里，说明前面的代码出错assert(0);}}}
private:Node* _root = nullptr;
};

 四、旋转调整

1、新节点插入较高右子树的右侧---右右：左单旋

代码如下

	void _RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (subRL)//注意h==0的情况subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{subR->_parent = pParent;if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}}subR->_bf = parent->_bf = 0;}

2、 新节点插入较高左子树的左侧---左左：右单旋

注意事项同上。

代码如下 

void _RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (subLR)//注意h==0的情况subLR->_parent = parent;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{subL->_parent = pParent;if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}}subL->_bf = parent->_bf = 0;}

3、 新节点插入较高右子树的左侧---右左：先右单旋再左单旋

代码如下

	void _RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//提前记录，防止在旋转时被修改_RotateR(parent->_right);_RotateL(parent);if (bf == 0){parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = subRL->_bf = 0;}else{subR->_bf = 1;parent->_bf = subRL->_bf = 0;}}

 4.新节点插入较高左子树的右侧---左右：先左单旋再右单旋

这个留给读者思考 

附：

//完整版代码
template<class K,class V>
struct AVLTreeNode {AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;pair<K, V> _kv;int _bf;AVLTreeNode(const pair<K,V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr),_kv(kv),_bf(0){}
};template<class K,class V>
class AVLTree {typedef AVLTreeNode<K, V> Node;
public:bool insert(const pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_parent = parent;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}while (parent){if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0)//为0，说明之前_bf=-1/1,即子树的高度没有发生变化{break;}	else if (parent->_bf == 1 || parent->_bf == -1)//为正负1，说明之前_bf=0，即子树的高度发生变化，并且会影响到上层祖宗结点{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//为正负2，树明显不平衡，需要旋转调整{if (parent->_bf == 2 && cur->_bf == 1)//如果该子树的严格右边高，则左单旋{_RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1)//如果该子树的严格左边高，则右单旋{_RotateR(parent);}else if (parent->_bf == -2 && cur->_bf == 1)//左右旋{_RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//右旋左旋{_RotateRL(parent);}break;//旋转之后整个树就平衡了，直接跳出循环}else{//这种情况不可能发生，如果发生就说明程序出错assert(false);}}return true;}void _RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;_RotateL(parent->_left);_RotateR(parent);if (bf == 1){subL->_bf = -1;subLR->_bf = parent->_bf = 0;}else if(bf == -1){parent->_bf = 1;subL->_bf = subLR->_bf = 0; }else//bf==0，插入的结点就是subLR{parent->_bf = subL->_bf = subLR->_bf = 0;}}void _RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;_RotateR(parent->_right);_RotateL(parent);if (bf == 1){parent->_bf = -1;subR->_bf = subRL->_bf = 0;}else if(bf == -1){subR->_bf = 1;parent->_bf = subRL->_bf = 0;}else //bf==0，插入的结点就是subLR{parent->_bf = subR->_bf = subRL->_bf = 0;}}//右单旋void _RotateR(Node*parent){Node* subL = parent->_left;//找到要作为新根的结点Node* pParent = parent->_parent;//找到该子树的父亲结点Node* subLR = subL->_right;subL->_right = parent;parent->_parent = subL;parent->_left = subLR;if (subLR)subLR->_parent = parent;if (_root == parent)//如果是根{_root = subL;subL->_parent = nullptr;}else{subL->_parent = pParent;if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}}parent->_bf = subL->_bf = 0;}//左单旋void _RotateL(Node* parent){Node* subR = parent->_right;//找到要作为新根的结点Node* pParent = parent->_parent;//找到该子树的父亲结点Node* subRL = subR->_left;//找到要被"过继"的孩子结点subR->_left = parent;if (subRL)//如有"过继"结点subRL->_parent = parent;parent->_parent = subR;parent->_right = subRL;if (_root == parent)//如果是根{_root = subR;subR->_parent = nullptr;}else{subR->_parent = pParent;if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}}parent->_bf = subR->_bf = 0;}bool Isbalance(){return _Isbalance(_root);//return _Isbalance(_root) >= 0;}bool _Isbalance(Node*root){if (root == nullptr)return true;int left = _Height(root->_left);int right = _Height(root->_right);if (abs(right - left) > 1){cout << root->_kv.first << ":" << root->_kv.second << endl;return false;}if (right - left != root->_bf){cout << root->_kv.first << ":"<< "平衡因子出错" << endl;return false;}return _Isbalance(root->_left) && _Isbalance(root->_right);}size_t size(){return _size(_root);}size_t Height(){return _Height(_root);}private:size_t _Height(Node*root){if (root == nullptr)return 0;return max(_Height(root->_left),_Height(root->_right)) + 1;}size_t _size(Node* root){if (root == nullptr)return 0;return 1 + _size(root->_left) + _size(root->_right);}//如果单纯判断是否平衡可以这么写，-1表示不平衡，>=0表示平衡//int _Isbalance(Node* root)//{//	if (root == nullptr)//		return 0;//	int left = _Isbalance(root->_left);//	if (left < 0) return -1;//	int right = _Isbalance(root->_right);//	if (right < 0) return -1;//	if (abs(right - left) > 1 || right - left != root->_bf)//	{//		return -1;//	}//	return max(left, right) + 1;//}
private:Node* _root = nullptr;
};

这篇关于C++进阶篇4---番外-AVL树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/368037。

相关文章

【C++ Primer Plus习题】13.4

【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++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

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

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

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

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

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...
c++的初始化列表与const成员

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量，在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员，因为执行构造函数时，类对象已经创建完成，只有类对象创建完成才能调用成员函数，构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化，该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面，主要用于给
阅读更多...
2024/9/8 c++ smart

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2