拿捏红黑树(C++)

2024-06-06 07:20
文章标签 c++ 红黑树 拿捏

本文主要是介绍拿捏红黑树(C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 一、红黑树介绍
  • 二、插入操作
  • 三、验证红黑树
  • 四、红黑树与AVL性能比较与应用
  • 五、总体代码
  • 总结


前言

我们之前介绍了一种AVL的高阶数据结构,在本篇文章中,我们将会介绍一种与AVL旗鼓相当的数据结构–红黑树。
我们并且会对它的部分接口进行模拟实现

一、红黑树介绍

AVL是保证左右高度不超过1,实现平衡。
红黑树是在每个节点存储位表示颜色,包括红色和黑色,并且保证最长路径的节点个数不超过最短节点路径的两倍,我们就可以达到一种近似平衡
在这里插入图片描述

性质

🌟每个节点颜色不是红色就是黑色
🌟根节点是黑色的
🌟如果一个节点是红色,那么它的孩子必须是黑色节点(不允许出现连续的红色节点
🌟每条路径都包含相同数量的黑色节点(路径:根节点到空)
🌟空节点设置为黑色,这个节点也称为NIL节点

为什么这几条规则就可以保证最长路径的节点数量不超过最短路径节点数量的两倍呢??

我们从极端场景分析:
最短路径:全黑节点
最长路径:一黑一红

二、插入操作

我们需要一个位置表示颜色,这里我们采用枚举(enum)的方式。

我们插入到节点是插入红色呢还是黑色呢??

我们看一下主要的规则:每条路径都包含相同数量的黑色节点;不允许出现连续的红色节点。

如果我们插入黑色节点,每条路径都会受到影响,我们是很难控制调整的。
如果我们插入红色节点,不允许出现连续的红色节点。我们只是在一条路径上插入,只需要调整这条路径上的节点,保证不出现连续的红色节点就可以。

先把大框架实现。

enum Col
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Col  _col;//表示颜色pair<K, V>_kv;RBTreeNode(const pair<K, V>kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED)//初始化为红色,_kv(kv){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root = nullptr;
};

如何插入节点呢??
1.按照二叉搜索树规则找到插入节点
2.进行颜色调整

我们插入的是红色节点,如果父亲节点的颜色也是红色,我们就需要进行调整。
如果父亲节点的颜色是黑色,我们就不需要进行处理,直接退出。

调整:
我们这里的关键是看叔叔
因为我们已经知道我们插入的节点是红色,并且父亲也是红色,爷爷节点必定是黑色。
我们唯一不确定的就是叔叔节点

uncle存在且为红

在这里插入图片描述

我们分析一下具象图

当a/b/c/d/e都为空时,cur就是新插入节点。
在这里插入图片描述

我们需要把p和u变黑,同时把g变黑
在这里插入图片描述

如果这个节点是根节点,我们就把g变黑。
否则cur=g,p=g->p;继续调整。(原来根是黑色,现在变为红色)

当c/d/e是包含一个黑色节点的子树

有四种情况
在这里插入图片描述

我们选择最简单的看一下,插入的位置有四个选择。
在这里插入图片描述

我们把p和u变黑,同时g变红

下图才是我们这种去情况的具象图,这种情况是由之前的情况调整过来的。
在这里插入图片描述

把p和u变黑,同时g变红
如果这个节点是根节点,我们就把g变黑。
否则cur=g,p=g->p;继续调整。(原来根是黑色,现在变为红色)

在这里插入图片描述
我们发现g就是根节点,我们把g变黑

在这里插入图片描述

我们发现现在每条路径上黑节点的数量增加了,由原来两个黑节点变为现在3个黑节点。
黑色节点的数量增加是在根节点增加的,根节点增加就相当于每条路径都增加。

uncle不存在,或者存在且为黑

在这里插入图片描述

如果u不存在,cur就是新增加点,我们通过之前的变色已经完成不了了。
在这里插入图片描述

我们这时就需要进行旋转,旋转方式还是按照AVL树的情况。
这个场景下我们需要右旋

在这里插入图片描述
旋转完之后,进行变色,p变黑,g变红
在这里插入图片描述

如果是下面这种情况,我们就需要进行双旋之后,再进行变色
在这里插入图片描述

首先对p进行左旋
在这里插入图片描述

再对g进行右旋
在这里插入图片描述
最后进行变色,cur变为黑,g变为红
在这里插入图片描述

总结:
🌟我们新插入节点颜色是红色
🌟如果新插入节点的父亲节点是黑色,我们不进行调整,直接退出
🌟如果新插入节点的父亲节点是红色,此时关键看叔叔。
🌟如果叔叔存在且为红,将p和u变黑,g变红。判断g是否为根节点。如果为根节点,g变黑。否则继续调整。
我们不关心左右,p和u是g的左右都不收影响,cur是p的左右也不受影响。
🌟如果uncle不存在或者存在且为黑,调整完之后结束。原来根是黑色,现在根也是黑色,不影响
🌟p为g的左孩子,cur为p的左孩子,对g进行右单旋,p变黑,g变红
🌟p为g的右孩子,cur为p的右孩子,对g进行左单旋,p变黑,g变红
🌟p为g的左孩子,cur为p的右孩子,对p进行左单旋,对g进行右单旋,c变黑,g变红
🌟p为g的右孩子,cur为p的左孩子,对p进行右单旋,对g进行左单旋,c变黑,g变红

	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 (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}//存在else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//颜色调整while (parent && parent->_col == RED){//因为parent存在且不是黑色节点,则parent一定不是根,一定存在。Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在,或者存在且为黑else{//左子树的左边if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//左子树的右边else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在,或者存在且为黑else{//右子树的右边if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//右子树的左边else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}_root->_col = BLACK;}return true;}

我们有可能需要大量判断是否为根节点的情况,我们直接在结尾处加上
_root->_col = BLACK;暴力处理

三、验证红黑树

我们如何进行验证是一颗红黑树呢??
我们从主要的规则入手

🌟根节点是黑色的
🌟不允许出现连续的红色节点
🌟每条路径都包含相同数量的黑色节点

我们只需要判断这三条成立,就能保证最长路径的节点个数不超过最短节点路径的两倍,从而证明这就是一颗红黑树。

根是黑节点很好证明,其他两条呢??

不允许出现连续红色节点,判断一个节点和它的父节点是否都是红色。
这里如果判断这个节点和它的孩子节点会很复杂。

每条路径都包含相同数量的黑色节点,我们可以选择其中一条路径,计算出有多少个黑色节点,从而判断其他路径的黑色节点数量。

bool  IsBalance(){if (_root && _root->_col == RED){cout << "根节点为红色" << endl;return false;}//参考值int level = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){level++;}cur = cur->_left;}return check(_root, 0, level);}//BlackNum不能加引用
bool check(Node* root, int BlackNum, int level)
{if (root == nullptr){if (BlackNum != level){cout << "不包含相同数量的黑色节点" << endl;return false;}return true;}//判断红节点if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红节点" << endl;return false;}if (root->_col == BLACK){BlackNum++;}return check(root->_left, BlackNum, level) && check(root->_right, BlackNum, level);
}

四、红黑树与AVL性能比较与应用

性能

红黑树和AVL都是高效的平衡二叉树,增删查改的时间复杂度为·O(logN).
红黑树不追求绝对平衡,只需要保证最长路径不超过最短路径的两倍。相对而言,降低了插入和旋转次数,所以在经常进行增删的结构中比AVL更优,红黑树的实现比较简单,实际应用中红黑树更多。

AVL高度logN,红黑树高度logN*2.红黑树搜索效率相对AVL差一点,但是logN足够小,可以忽略不计。
N=10亿。logN=30.

应用:
1.C++ STL库 – map/set、mutil_map/mutil_set
2.Java 库
3. linux内核
4.其他库

五、总体代码

#pragma onceenum Col
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Col  _col;pair<K, V>_kv;RBTreeNode(const pair<K, V>kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public: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 (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}//存在else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//颜色调整while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在,或者存在且为黑else{//左子树的左边if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//左子树的右边else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//判断叔叔//叔叔存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔不存在,或者存在且为黑else{//右子树的右边if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//右子树的左边else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}_root->_col = BLACK;}return true;}//1.根节点是黑色//2.不包含连续的红色节点//3.每条路径都包含相同黑色节点bool  IsBalance(){if (_root && _root->_col == RED){cout << "根节点为红色" << endl;return false;}//参考值int level = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){level++;}cur = cur->_left;}return check(_root, 0, level);}void Inorder(){_Inorder(_root);}
private://BlackNum不能加引用bool check(Node* root, int BlackNum, int level){if (root == nullptr){if (BlackNum != level){cout << "不包含相同数量的黑色节点" << endl;return false;}return true;}//判断红节点if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红节点" << endl;return false;}if (root->_col == BLACK){BlackNum++;}return check(root->_left, BlackNum, level) && check(root->_right, BlackNum, level);}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right= subRL;if (subRL){subRL->_parent = parent;}subR->_left= parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parent == ppnode->_left){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;}subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (ppnode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}Node* _root = nullptr;
};

总结

以上就是今天要讲的内容,本文仅仅详细介绍了红黑树的特征,已经模拟实现了插入操作 。希望对大家的学习有所帮助,仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘

这篇关于拿捏红黑树(C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发;同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()?它的作用是什么?类比一下:二、join()的作用总结三、join()怎么

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的