【C++】AVL树 红黑树

AVL树

AVL树也是二叉搜索树的一种。因为对于普通的二叉搜索树，当插入的数据在有序或接近有序的情况下，二叉搜索树很可能退化成单支树，导致查找效率低下。而AVL树就很好的解决了这个问题。
首先，AVL树是一棵二叉搜索树。同时对于AVL树中每个节点，它的左右子树高度之差的绝对值不超过1。
对于有n个节点的AVL树，其搜索时间复杂度可以稳定的保持在 O ( l o g 2 n ) O(log_2 n) O(log2​n)。
为了保证向AVL树中插入节点，仍保持其高度的平衡，可以引入平衡因子（平衡因子：右子树的高度 - 左子树的高度）来处理。

// AVL树节点的定义
template<class K, class V>
class AVLTreeNode
{
public:AVLTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; //  balance factor
};

因为AVL树仍是二叉搜索树，所以AVL树的插入可以分两步进行：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整平衡因子
// AVL树的插入
template<class K, class V>
class AVLTree
{
private:typedef AVLTreeNode<K, V> Node;
public:AVLTree(Node* root = nullptr): _root(root){}bool Insert(const pair<K, V>& kv){/* * 1.按照二叉搜索树的方式插入新节点*/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->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 直接插入cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;/** 2.调整平衡因子*/while (parent){// 新增在右，parent->_bf++; 新增在左，parent->_bf--;if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}// 调整后，parent->_bf == 0, 说明parent插入前的平衡因子是 1 or -1，说明插入前左右子树一边高一边低，插入后两边一样高，// 即插入填上了矮的一边，插入后parent所在子树高度不变，不需要继续往上调整if (parent->_bf == 0){break;}// 调整后，parent->_bf == 1 or -1, 说明parent插入前的平衡因子是0，插入前左右子树高度相等，插入后有一边变高了，// parent高度变了，需要继续往上更新else if (abs(parent->_bf) == 1){parent = parent->_parent;cur = cur->_parent;}// 调整后，parent->_bf == 2 or -2, 说明parent插入前的平衡因子是 1 or -1，已经是平衡临界值，// 插入后变成了 2 or -2，打破平衡，parent所在子树需要进行 旋转处理else if (abs(parent->_bf) == 2){// 根据节点插入位置的不同，AVL树的旋转分为四种// 新节点插入在较高右子树的右侧（右右）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);}else{assert(false);}break;}// 调整后，不可能出现parent->_bf > 2 or < -2，否则一定出bug了else{assert(abs(parent->_bf) <= 2);}}return true;}
private:// 左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}// 保存parent的双亲节点Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;// parent作为整棵树的根存在if (_root == parent){_root = subR;subR->_parent = nullptr;}// parent作为子树的根存在else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;}// 右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}// 左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;// 保存subLR当前的平衡因子int bf = subLR->_bf;// 先左单旋RotateL(parent->_left);// 再右单旋RotateR(parent);// 此处对于平衡因子的调整，建议画图分析subLR->_bf = 0;if (bf == 1){parent->_bf = 0;subL->_bf = -1;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;}else if(bf == 0){parent->_bf = 0;subL->_bf = 0;}else{assert(false);}}// 右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);subRL->_bf = 0;if (bf == 1){parent->_bf = -1;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;}else{assert(false);}}
private:Node* _root;
};

RotateL左单旋示意图：
在这里插入图片描述
RotateR右单旋示意图：
在这里插入图片描述
RotateLR左右双旋示意图：
在这里插入图片描述
在这里插入图片描述
RotateRL右左双旋示意图：
在这里插入图片描述
可以通过下面程序对AVL树的正确性做一个验证。

template<class K, class V>
class AVLTree
{
private:typedef AVLTreeNode<K, V> Node;
public:// 1.验证其为二叉搜索树void InOrderTraversal(){_InOrderTraversal(_root);}// 2.验证其为平衡树bool IsBalance(){return _IsBalance(_root);}
private:// 如果中序遍历为有序序列，则说明为二叉搜索树void _InOrderTraversal(Node* root){if (root == nullptr){return;}_InOrderTraversal(root->_left);cout << root->_kv.first << " : " << root->_kv.second << endl;_InOrderTraversal(root->_right);}// 要求每个节点的子树高度差的绝对值不超过1，并且高度差要和平衡因子相等bool _IsBalance(Node* root){// 空树也算AVL树if (root == nullptr){return true;}int leftHt = Height(root->_left);int rightHt = Height(root->_right);int diff = rightHt - leftHt;if (diff != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(diff) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}int Height(Node* root){if (root == nullptr)return 0;int leftHt = Height(root->_left);int rightHt = Height(root->_right);return max(leftHt, rightHt) + 1;}
private:Node* _root;
};

红黑树

红黑树也是二叉搜索树的一种。
在这里插入图片描述
红黑树的性质要求如下：

  1. 每个节点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子节点必须是黑色的（或者说不允许存在父子节点同时为红色）
  4. 对于每个节点，从该节点到其后代叶节点的所有简单路径上，都只包含相同数量的黑色节点
  5. 所有的叶节点都是黑色的（叶节点指的是NIL节点）

通过以上5条性质的约束，就可以确保红黑树中 最长路径 ≤ 2 × 最短路径 最长路径 \leq 2 \times 最短路径 最长路径≤2×最短路径，从而来保证了红黑树的平衡性能。
虽然红黑树的平衡性能比AVL的略差些，但插入同样的数据，红黑树旋转更少。

// 红黑树节点的定义
enum Colour
{RED,BLACK
};template<class K, class V>
class RBTreeNode
{
public:RBTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;
};

因为红黑树仍是二叉搜索树，所以红黑树的插入可以分两步进行：

  1. 按照二叉搜索树的方式插入新节点
  2. 检测插入新节点后，红黑树的性质是否受到破坏，并做变色或旋转调整
template<class K, class V>
class RBTree
{
private:typedef RBTreeNode<K, V> Node;
public:RBTree(Node* root = nullptr): _root(root){}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);// 根节点是黑色的_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 直接插入新节点cur = new Node(kv);// 对于插入的新节点赋为红色cur->_col = RED;if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 如果父节点存在且为黑，没有破坏红黑树的规则，不需要调整// 如果父节点存在且为红，破坏了性质3while (parent && parent->_col == RED){// 此时祖父节点一定存在且为黑Node* grandparent = parent->_parent;assert(grandparent);assert(grandparent->_col == BLACK);// 关键看叔叔(节点)// parent 为 grandparent 的左孩子if (parent == grandparent->_left){Node* uncle = grandparent->_right;// 情况一 uncle存在且为红if (uncle && uncle->_col == RED){// 将 parent 和 uncle 改为黑，grandparent 改为红，parent->_col = uncle->_col = BLACK;grandparent->_col = RED;// 然后把 grandparent 当成 cur，继续向上调整cur = grandparent;parent = cur->_parent;}// 情况二三 uncle不存在，或uncle存在且为黑else{// parent 为 grandparent 的左孩子，且 cur 为 parent 的左孩子if (cur == parent->_left){// 右单旋RotateR(grandparent);// 变色: parent 变黑，grandparent 变红parent->_col = BLACK;grandparent->_col = RED;}// parent 为 grandparent 的左孩子，且 cur 为 parent 的右孩子else{// 左右双旋RotateL(parent);RotateR(grandparent);// 变色: parent 变黑，grandparent 变红cur->_col = BLACK;grandparent->_col = RED;}break;}}// parent 为 grandparent 的右孩子else{Node* uncle = grandparent->_left;// 情况一 uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}// 情况二三 uncle不存在，或uncle存在且为黑else{// parent 为 grandparent 的右孩子，且 cur 为 parent 的右孩子if (cur == parent->_right){RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}// parent 为 grandparent 的右孩子，且 cur 为 parent 的左孩子else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return true;}
private:void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}
private:Node* _root;
};

uncle存在且为红：
在这里插入图片描述
可以通过下面程序对红黑树的正确性做一个验证。

template<class K, class V>
class RBTree
{
private:typedef RBTreeNode<K, V> Node;
public:// 1.验证其为二叉搜索树void InOrderTraversal(){_InOrderTraversal(_root);}// 2. 通过红黑树的性质验证其平衡性bool IsBalance(){// 空树也算红黑树if (_root == nullptr){return true;}// 验证性质2if (_root->_col == RED){cout << "根节点不是黑色" << endl;return false;}// benchmark作为每条路径上黑色节点数量的基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++benchmark;}cur = cur->_left;}return PrevCheck(_root, 0, benchmark);	}
private:// 如果中序遍历为有序序列，则说明为二叉搜索树void _InOrderTraversal(Node* root){if (root == nullptr){return;}_InOrderTraversal(root->_left);cout << root->_kv.first << " : " << root->_kv.second << endl;_InOrderTraversal(root->_right);}bool PrevCheck(Node* root, int blackNum, int benchmark){if (root == nullptr){// 验证性质4if (blackNum != benchmark){cout << "路径上黑色节点数量不相等" << endl;return false;}else{return true;}}// 验证性质3if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){++blackNum;}return PrevCheck(root->_left, blackNum, benchmark)&& PrevCheck(root->_right, blackNum, benchmark);}
private:Node* _root;
};

红黑树相比AVL树不追求绝对的平衡，其只需保证最长路径不超过最短路径的2倍即可，所以相对而言红黑树减少了插入时旋转的次数，在经常需要进行增删的结构中性能比AVL树更优，实际运用中也是红黑树更多。

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

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

相关文章

二十二，加上各种贴图

二十二，加上各种贴图

使用pbr的各种贴图&#xff0c;albedo,金属度&#xff0c;ao,法线&#xff0c;粗糙度&#xff0c;可以更好的控制各个片元 1&#xff0c;先加上纹理坐标 texCoords->push_back(osg::Vec2(xSegment, ySegment)); geom->setVertexAttribArray(3, texCoords, osg::Array::BI…
阅读更多...
Linux基本指令（上）——“Linux”

Linux基本指令（上）——“Linux”

各位CSDN的uu们好呀&#xff0c;今天&#xff0c;小雅兰的内容是Linux啦&#xff01;&#xff01;&#xff01;主要是Linux的一些基本指令和Linux相关的基本概念&#xff08;系统层面&#xff09;&#xff0c;下面&#xff0c;让我们进入Linux的世界吧&#xff01;&#xff01;…
阅读更多...
Linux基本指令介绍系列第四篇

Linux基本指令介绍系列第四篇

文章目录 前言一、Linux基本指令介绍1、more指令2、less指令3、head指令4、tail指令5、bc指令6、管道文件介绍7、与时间相关的指令 总结 前言 本文介绍Linux使用时的部分指令&#xff0c;读者如果想了解更多基本指令的使用&#xff0c;可以关注博主的后续的文章。 博主使用的实…
阅读更多...
Sentinel安装

Sentinel安装

Sentinel 微服务保护的技术有很多&#xff0c;但在目前国内使用较多的还是Sentinel&#xff0c;所以接下来我们学习Sentinel的使用。 1.介绍和安装 Sentinel是阿里巴巴开源的一款服务保护框架&#xff0c;目前已经加入SpringCloudAlibaba中。官方网站&#xff1a; 首页 | Se…
阅读更多...
数据源报表

数据源报表

1.新建报表 2.新建数据集 3.维护数据源 支持的数据库还是蛮多哈 4.选择数据源表 5.编写sql 编码&#xff1a;SQL数据集的标识 注&#xff1a;避免特殊字符和_名称&#xff1a;SQL数据集的名称是否集合&#xff1a;否为单数据&#xff1b;是为多数据列表&#xff0c;如果多条数据…
阅读更多...
怎么通过docker/portainer部署vue项目

怎么通过docker/portainer部署vue项目

这篇文章分享一下如何通过docker将vue项目打包成镜像文件&#xff0c;并使用打包的镜像在docker/portainer上部署运行&#xff0c;写这篇文章参考了vue-cli和docker的官方文档。 首先&#xff0c;阅读vue-cli关于docker部署的说明&#xff0c;上面提供了关键的几个步骤。 从上面…
阅读更多...
opencv图像数组坐标系

opencv图像数组坐标系

在OpenCV的Python接口&#xff08;cv2&#xff09;中&#xff0c;加载的图像数组遵循以下坐标系和方向约定&#xff1a; 1. **坐标系&#xff1a;** OpenCV的坐标系遵循数学中的坐标系&#xff0c;原点&#xff08;0, 0&#xff09;位于图像的左上角。横轴&#xff08;X轴&…
阅读更多...
国庆发生的那些事儿------编写了炫酷的HTML动态鼠标特效，超级炫酷酷酷！

国庆发生的那些事儿------编写了炫酷的HTML动态鼠标特效，超级炫酷酷酷！

文章目录 前言具体操作总结 前言 国庆假期的欢乐&#xff0c;当然少不了编码爱好者&#xff01;假期编写了炫酷的HTML动态鼠标特效&#xff0c;超级炫酷酷酷&#xff01;让你的页面变得更加炫酷&#xff0c;让你的小伙伴们羡慕的大神编码&#xff01;快来看看大神是如何编写的…
阅读更多...
英伟达NVIDIA驱动安装

英伟达NVIDIA驱动安装

一般&#xff0c;我们新的显卡上机或者新系统可能就需要重新安装显卡驱动。或者是我们在配置深度学习环境时候&#xff0c;需要手动安装驱动。 官网地址&#xff1a;官方高级驱动搜索 | NVIDIA 我们选择好自己需要的驱动后直接安装即可 下载的时候&#xff0c;选择自己需要的驱…
阅读更多...
基于SpringBoot的网上超市系统

基于SpringBoot的网上超市系统

基于SpringBoot的网上超市系统的设计与实现 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBootMyBatis工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 【主要功能】 角色&#xff1a;用户、管理员 管理员&#xff1a;个人中心、用户管理、商品分类…
阅读更多...
BIRCH算法全解析：从原理到实战

BIRCH算法全解析：从原理到实战

目录 一、引言什么是BIRCH算法BIRCH算法的应用场景文章目标和结构概述 二、BIRCH算法基础CF&#xff08;Clustering Feature&#xff09;树的概念数据点簇簇的合并和分裂 BIRCH的时间复杂度和空间复杂度BIRCH vs K-means和其他聚类算法 三、BIRCH算法的技术细节CF树的构建节点和…
阅读更多...
计算机毕设 大数据工作岗位数据分析与可视化 - python flask

计算机毕设 大数据工作岗位数据分析与可视化 - python flask

文章目录 0 前言1 课题背景2 实现效果3 项目实现3.1 概括 3.2 Flask实现3.3 HTML页面交互及Jinja2 4 **完整代码**5 最后 0 前言 &#x1f525; 这两年开始毕业设计和毕业答辩的要求和难度不断提升&#xff0c;传统的毕设题目缺少创新和亮点&#xff0c;往往达不到毕业答辩的要…
阅读更多...
word 多级目录的问题

word 多级目录的问题

一、多级标题自动编号 --> 制表符 -> 空格 网址&#xff1a; 【Word技巧】2 标题自动编号——将多级列表链接到样式 - YouTube 二、多级列表 --> 正规形式编号 网址&#xff1a;Word 教学 - 定框架&#xff1a;文档格式与多级标题&#xff01; - YouTube 三、目…
阅读更多...
osg实现鼠标框选

osg实现鼠标框选

目录 1. 需求的提出 2. 具体实现 2.1. 禁止场景跟随鼠标转动 2.2. 矩形框前置绘制 3. 附加说明 3.1. 颜色设置说明 3.2.矩形框显示和隐藏的另一种实现 1. 需求的提出 有时需要在屏幕通过按住键盘上的某个键如Ctrl键且按住鼠标左键&#xff0c;拖出一个矩形&#xff0c;实现框…
阅读更多...
[Machine learning][Part3] numpy 矢量矩阵操作的基础知识

[Machine learning][Part3] numpy 矢量矩阵操作的基础知识

很久不接触数学了&#xff0c;machine learning需要用到一些数学知识&#xff0c;这里在重温一下相关的数学基础知识 矢量 矢量是有序的数字数组。在表示法中&#xff0c;矢量用小写粗体字母表示。矢量的元素都是相同的类型。例如&#xff0c;矢量不包含字符和数字。数组中元…
阅读更多...
vertx的学习总结7

vertx的学习总结7

这里我就简单的聊几句&#xff0c;如何用vertx web来搞一个web项目的 1、首先先引入几个依赖&#xff0c;这里我就用maven了&#xff0c;这个是kotlinvertx web <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apac…
阅读更多...
Modelsim测试覆盖率操作说明

Modelsim测试覆盖率操作说明

1、打开Project窗口界面 2、在project界面下&#xff0c;选中所有需要测试覆盖率的.v文件&#xff08;不包括tb文件&#xff09;&#xff0c;鼠标点击右键&#xff0c;在Properties选项中选择Coverage选项&#xff0c;选择需要测试的覆盖率类型 3、重新编译所有的源文件&#x…
阅读更多...
(三) Markdown插入互联网或本地视频解决方案

(三) Markdown插入互联网或本地视频解决方案

前言 不论博客系统是WordPress还是Typecho&#xff0c;绕不开的是两种书写语言&#xff0c;一种称之为富文本&#xff0c;一种叫做Markdown。 Markdown有很多好处&#xff0c;也有很多坏处&#xff0c;比如Markdown本身不具备段落居中的功能&#xff0c;以及Markdown也不具有…
阅读更多...
Java架构师职责和技能

Java架构师职责和技能

目录 1 架构师简介2 架构师职责2.1 架构师是技术领导架构设计做决策2.2 架构师可以是团队或者组织2.3 架构师必须掌握足够的技术知识2.4 架构师必须掌握足够的架构设计技能2.5 架构师必须具备很好的编程能力2.6 架构师必须深入理解业务及其业务的领域知识2.7架构师应该具备很好…
阅读更多...
基于Java的驾校收支管理可视化平台设计与实现(源码+lw+部署文档+讲解等)

基于Java的驾校收支管理可视化平台设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作…
阅读更多...
最新文章

Copyright @ 2022~2023