[数据结构 - C++] 红黑树RBTree

2024-01-22 18:44

本文主要是介绍[数据结构 - C++] 红黑树RBTree,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

文章目录

  • 1、前言
  • 2、红黑树的概念
  • 3、红黑树的性质
  • 4、红黑树节点的定义
  • 5、红黑树的插入Insert
  • 6、红黑树的验证
  • 7、红黑树与AVL树的比较
  • 附录:

1、前言

我们在学习了二叉搜索树后,在它的基础上又学习了AVL树,知道了AVL树是靠平衡因子来调节左右高度差,从而让树变得平衡的。本篇我们再来学习一个依靠另一种平衡规则来控制的二叉搜索树——红黑树。

2、红黑树的概念

红黑树,是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
在这里插入图片描述

3、红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
红色不能连续,黑色可以连续
4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

概念中,说到没有一条路径会比其他路径长出俩倍,性质3与性质4相互牵制就可以保证这一点。

4、红黑树节点的定义

我们定义节点依然是三叉链,与AVL树不同的是红黑树没有平衡因子,而是保存一个代表节点颜色的属性。

enum Color
{RED,BLACK
};template <class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Color _col;RBTreeNode(const pair<K, V>& _kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};

这里我们定义的红黑树节点,颜色默认给的红色,但是这里是给红色还是黑色合适呢?
当插入的时候,我们新插入的节点颜色是黑色时,就会破坏性质3,新插入节点的这条路径的黑色节点数一定会比其他路径的黑色节点多一个,影响整棵树。
如果是红色,那插入的时候她的父节点可能是黑色,没有影响,可能是红色,那么就会出现连续的红色节点,但是它只会影响这一条路径。
这两种颜色插入,黑色是一定会影响,红色是可能会影响的,且黑色影响整棵树,红色影响它这一条路径,两害取其轻,我们选择红色,调整的话也比较容易调整。下面我们就来尝试看插入怎么写:

5、红黑树的插入Insert

红黑树的插入是在二叉搜索树插入基础上来修改的,因此大的方向分两步走:
1、找到插入的位置;
2、插入节点后,根据性质来调节平衡。

bool Insert(const pair<K, V>& kv)
{if (nullptr == _root){_root = new Node(data);_root->_col = BLACK; // 性质2:根节点是黑色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;}}// 新增插入节点是红色只会影响父节点,如果是黑色影响所有路径// 所以 new 的节点为红色cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 维护处理 ...
}

当来到这块时,已经插入了,要做的就是按照性质来检查和维护这棵树了。
1、当父亲是黑色,那么就不用维护,就结束了;
2、当父亲是红色,那么就违反了性质3(不能存在连续的红色节点),这时就需要调整了,调整也是要分情况讨论(约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点)。
情况一:cur是红色,p为红色,g为黑色,u存在且为红色
这里看到的这棵树可能是完整的,也可能是子树:
在这里插入图片描述

如果是完整的树,那么改完之后,需要将g的颜色改为黑色。
如果g是子树,那么g就有父节点,这时g的颜色改为红色,父节点颜色可能也是红色,这时急需要继续向上调整了。
将p,u改为黑,g改为红,然后把g当作cur,继续向上调整。
情况二:cur是红色,p为红色,g为黑色,u不存在/u存在且为黑色
在这里插入图片描述

这里u有两种颜色,我们分开讨论:

  • 如果u不存在,那么cur一定是新增。因为u不存在g也是有一条右边路径的,这条路径就两个黑色节点空结点也是黑色,那么c就不存在,a、b都不存在,如果存在就是黑色节点,那么就打破了性质3。
  • 如果存在且为黑,那么这个抽象图就不全。因为父节是红色,叔叔为黑色,每条路径的黑色节点个数要相同,因此推测出cur之前应该是黑色,那么a、b就应该是红色,新增节点在a/b的孩子位置。
    整体就为下图:
    在这里插入图片描述

它会先经过情况一的调整方式,调整完变为情况二这样,然后再继续调整:
在这里插入图片描述

此时,就 以g为基点先右旋,然后将父节点颜色变为黑色,祖父节点颜色变为红色。(旋转不清楚的同学可以看看AVL树的)
情况三:cur是红色,p为红色,g为黑色,u不存在/u存在且为黑色
在这里插入图片描述

  • u不存在,cur是新增。因为每条路径的黑色节点个数相同,u不存在,u这条路径上两个黑色节点空结点也是黑色),推测出a、b、c都是不存在的,那么cur就是新增,如果存在只能是黑色节点,那么就打破了性质3。
  • 如果存在且为黑,这个抽象图依然是不完整的。因为父节点是红色,叔叔为黑色,每条路径的黑色节点相同,因此推测出a为黑色,cur之前也应该为黑色,那么b、c就应该是红色,新增节点在b/c的孩子位置。

图跟情况二中,u存在且为黑差不多:
在这里插入图片描述

会先经过情况一调整,变为情况三这样,然后进行调整:
在这里插入图片描述

此时,先以p为基点左旋,再以g为基点右旋,然后将cur节点变为黑色,祖父节点变为红色。
如果新增的父节点在右,叔叔节点在左,那么也是分以上三种情况,调整方式也是对应三种方式差不多,这里就不过多赘述,直接上代码:

bool Insert(const pair<K, V>& kv)
{if (nullptr == _root){_root = new Node(data);_root->_col = BLACK; // 性质2:根节点是黑色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;}}// 新增插入节点是红色只会影响父节点,如果是黑色影响所有路径// 所以 new 的节点为红色cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 不断向上调整的,所以得用whilewhile (parent && parent->_col == RED){// 父节点是祖父节点的左//      g//    p   u//  c Node* grandfather = parent->_parent;// 1、父节点在祖父的左,即叔叔在右if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 1.1 叔叔存在并且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 向上调整cur = grandfather;parent = cur->_parent;}// 1.2 叔叔不存在 / 叔叔存在且为黑,处理方法一样else{if (cur == parent->_left) // 左边高的情况{// 右单旋//     g//   p   u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // 左边高右边高的情况{// 双旋//     g//  p     u//    cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}// 2、父节点在祖父的右,即叔叔在祖父的左else // parent == grandfather->_right{//     g//   u   p//         cNode* uncle = grandfather->_left;// 2.1 叔叔存在且叔叔为红色if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 向上调整cur = grandfather;parent = cur->_parent;}// 2.2 叔叔不存在 / 叔叔存在且颜色为黑,处理方法一样else{if (cur == parent->_right) // 右边高的情况{//     g//   u   p//         cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // 右边高,左边高{//     g//  u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}}// 最后将根节点变为黑色_root->_col = BLACK;return true;
}// 左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (_root == parent) // 父节点就是根节点{_root = subR;subR->_parent = nullptr;}else // 子树情况{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}
}// 右单旋
void RotateR(Node* parent)
{Node* parentParent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (_root == parent) // 父节点是根节点{_root = subL;subL->_parent = nullptr;}else // 子树情况{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}
}

6、红黑树的验证

红色树的验证本质就是验证两方面:
1、是否为二叉搜索树(中序遍历是否有序);
2、是否满足5条性质。

void _InOrder(Node* pRoot)
{if (pRoot == nullptr)return;_InOrder(pRoot->_left);cout << pRoot->_data << " ";_InOrder(pRoot->_right);
}bool IsBalance()
{if (_root == nullptr) return true;if (_root->_col == RED) return false;// 参考值int refValue = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK) refValue++;cur = cur->_left;}// 检查每条路径黑色节点个数// 思路:以上面参考值为主,对比每条路径的黑色节点个数// 当走到空就说明该路径走完了,那么这个过程中记录下黑色节点个数,到空时与refValue对比// 这里传进去blacknum只能是传值,这样就不会影响上一层的blacknum了int blacknum = 0;// 检查连续红色节点与每条路径黑色节点个数return Check(_root, blacknum, refValue);
}
bool Check(Node* root, int blacknum, const int& refValue)
{if (root == nullptr){if (blacknum != refValue){cout << "存在黑色节点不相等的路径" << endl;return false;}return true;}// 反向检查,查看当前与父结点为红色(当前节点为红色就说明不是根节点,即存在父节点)if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK) blacknum++;return Check(root->_left, blacknum, refValue)&& Check(root->_right, blacknum, refValue);
}

7、红黑树与AVL树的比较

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

附录:

enum Color
{RED,BLACK
};template <class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Color _col;RBTreeNode(const pair<K, V>& _kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};template <class K, class V>
class RBTree
{typedef RBTreeNode<K,V> Node;
public:bool Insert(const pair<K, V>& kv){if (nullptr == _root){_root = new Node(data);_root->_col = BLACK; // 性质2:根节点是黑色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;}}// 新增插入节点是红色只会影响父节点,如果是黑色影响所有路径// 所以 new 的节点为红色cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 不断向上调整的,所以得用whilewhile (parent && parent->_col == RED){// 父节点是祖父节点的左//      g//    p   u//  c Node* grandfather = parent->_parent;// 1、父节点在祖父的左,即叔叔在右if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 1.1 叔叔存在并且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 向上调整cur = grandfather;parent = cur->_parent;}// 1.2 叔叔不存在 / 叔叔存在且为黑,处理方法一样else{if (cur == parent->_left) // 左边高的情况{// 右单旋//     g//   p   u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // 左边高右边高的情况{// 双旋//     g//  p     u//    cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}// 2、父节点在祖父的右,即叔叔在祖父的左else // parent == grandfather->_right{//     g//   u   p//         cNode* uncle = grandfather->_left;// 2.1 叔叔存在且叔叔为红色if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 向上调整cur = grandfather;parent = cur->_parent;}// 2.2 叔叔不存在 / 叔叔存在且颜色为黑,处理方法一样else{if (cur == parent->_right) // 右边高的情况{//     g//   u   p//         cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // 右边高,左边高{//     g//  u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}}// 最后将根节点变为黑色_root->_col = BLACK;return true;}bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return true;}bool IsBalance(){if (_root == nullptr) return true;if (_root->_col == RED) return false;// 参考值int refValue = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK) refValue++;cur = cur->_left;}// 检查每条路径黑色节点个数// 思路:以上面参考值为主,对比每条路径的黑色节点个数// 当走到空就说明该路径走完了,那么这个过程中记录下黑色节点个数,到空时与refValue对比// 这里传进去blacknum只能是传值,这样就不会影响上一层的blacknum了int blacknum = 0;// 检查连续红色节点与每条路径黑色节点个数return Check(_root, blacknum, refValue);}size_t Height(){return _Height(_root);}void InOrder(){_InOrder(_root);cout << endl;}private:bool Check(Node* root, int blacknum, const int& refValue){if (root == nullptr){if (blacknum != refValue){cout << "存在黑色节点不相等的路径" << endl;return false;}return true;}// 反向检查,查看当前与父结点为红色(当前节点为红色就说明不是根节点,即存在父节点)if (root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK) blacknum++;return Check(root->_left, blacknum, refValue)&& Check(root->_right, blacknum, refValue);}// 左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (_root == parent) // 父节点就是根节点{_root = subR;subR->_parent = nullptr;}else // 子树情况{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}// 右单旋void RotateR(Node* parent){Node* parentParent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (_root == parent) // 父节点是根节点{_root = subL;subL->_parent = nullptr;}else // 子树情况{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}void _InOrder(Node* pRoot){if (pRoot == nullptr)return;_InOrder(pRoot->_left);cout << pRoot->_data << " ";_InOrder(pRoot->_right);}size_t _Height(Node* pRoot){if (pRoot == nullptr)return 0;int leftHeight = _Height(pRoot->_left);int rightHeight = _Height(pRoot->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}private:Node* _root = nullptr;
};

这篇关于[数据结构 - C++] 红黑树RBTree的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

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最为重要的

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决