如何实现一棵红黑树

2024-08-25 00:04
文章标签 实现 红黑树 一棵

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

目录

1.什么是红黑树

2.红黑树的实现

2.1红黑树的插入

新插入的结点应该是什么颜色的呢?

插入情况的分析

​编辑插入代码如下所示

2.2红黑树的查找

2.2检测红黑树


1.什么是红黑树?

红黑树是一棵接近平衡的二叉搜索树。由于AVL树在频繁大量改变数据的情况下,需要进行很多的旋转,会降低效率,因此,需要新的方案解决AVL树的不足,于是,有大佬发明了红黑树;红黑树是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是red或black。 通过对各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。着色方式限制如下:

  • 每个结点不是红色就是黑色,但根节点必须是黑色的。
  • 如果一个节点是红色的,则它的两个孩子结点是黑色的(没有连续的红色结点)。
  • 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点(每条路径都包含相同数量的黑色结点)。
  • 注意:红黑树中的路径不是走到叶子结点,而是走到空。

为什么满足上述条件就可以保证最长路径不超过最短路径的2倍呢?极端条件下,最短路径为全黑,最长路径必须是一黑一红交替连接;此时,最长路径正好等于最短路径的2倍。

对比AVL树:AVL树高度很接近log_N,红黑树高度很接近2log_N,所以红黑树的查询效率比AVL树略差,但是几乎可以忽略不计,因为log_N足够小,所以他们之间查找的效率微乎其微。

2.红黑树的实现

(本文旨在了解红黑树,重点实现红黑树的插入)

2.1红黑树的插入

新插入的结点应该是什么颜色的呢?

红黑树的插入过程中需要保持红黑树的性质,所以,插入之前,每条路径上的黑色结点的数量是相等的,如果新插入的结点是黑色的,必然会破坏每条路径上黑色结点的数量相等的条件,需要调整;

如果插入红色结点呢?如果插入结点的父亲是黑色的,则没有破坏红黑树的性质,如果插入结点的父亲是红色的,则破坏了不能出现连续的红色结点的性质,需要调整。

总结一下就是,如果插入的结点是黑色的, 那么每次都需要调整,如果插入的结点是红色的,只有父结点是红色的,才需要调整;所以我们选择新增结点的颜色是红色的。

插入情况的分析

因为我们插入的结点的颜色是红色的,也就是上图中的cur结点,因为,插入之前的树是满足红黑树的性质的,所以,如果出现矛盾的话,p的颜色一定是红色的, g的结点一定是黑色的;此时,只剩下u结点的情况是不确定的,所以我们只需要分析u节点的情况。

情况一:u节点存在且为红色。处理方式为变色,p和u变黑g变红,如果g是根,把g变黑即可,如果g不是根,把g当成c,继续往上处理。如下图所示:

情况二:u不存在/u存在且为黑。在该情况下,又可以细分出四种情况。

  • p为g的左孩子,c为p的左孩子,以p为旋转中心进行右单旋调整。如下图所示:

  • p为g的右孩子,c为p的右孩子,以p为旋转中心进行左单旋调整。如下图所示:

  • p为g的左孩子,c为p的右孩子,以p为旋转中心进行左单旋,再以g为旋转中心进行右单旋,最后将cur变黑,将g变红。如下图所示:

  • p为g的右孩子,c为p的左孩子,以p为旋转中心进行右单旋,再以g为旋转中心进行左单旋,最后将cur变黑,将g变红。如下图所示:

插入代码如下所示

旋转操作和AVL树是相同的,此处不做讲解,不会的读者推荐阅读AVL树中有详细讲解

    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 (parent == grandfather->_left){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){//       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;} }else{Node* uncle = grandfather->_left;// 情况一:叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二:叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(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;}

2.2红黑树的查找

在红黑树查找一个值和在AVL树中查找一个值是相同的。代码如下所示:

    Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}

2.2检测红黑树

如何检测我们实现的红黑树是否正确呢?我们只需要检测该树是否满足红黑树的性质,也就是一下三点:

  • 1.根是黑色的
  • 2.没有连续的红色结点
  • 3.每条路径上的黑色结点的数量相等

检测策略:先求出一条路径上黑色结点的数量作为标准值,然后依次求每一条路径上黑色结点的数量,与标准值比较。代码如下:

bool Check(Node* cur, int blackNum, int refBlackNum){if (cur == nullptr){if (refBlackNum != blackNum){cout << "黑色节点的数量不相等" << endl;return false;}//cout << blackNum << endl;return true;}if (cur->_col == RED && cur->_parent->_col == RED){cout << cur->_kv.first << "存在连续的红色节点" << endl;return false;}if (cur->_col == BLACK)++blackNum;return Check(cur->_left, blackNum, refBlackNum)&& Check(cur->_right, blackNum, refBlackNum);}bool IsBalance(){if (_root && _root->_col == RED)return false;int refBlackNum = 0;Node* cur = _root;while (cur){if(cur->_col == BLACK)refBlackNum++;cur = cur->_left;}return Check(_root, 0, refBlackNum);}

这篇关于如何实现一棵红黑树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.