红黑树Java实现

文章目录

  • 红黑树
    • 1. 概念性质
    • 2. 红黑树节点定义
    • 3. 红黑树的插入
      • 情况1
      • 情况2
      • 情况3
      • 其它细节问题
      • 插入代码实现
    • 4. 红黑树的验证
    • 5.性能分析


红黑树

1. 概念性质

红黑树也是一种二插搜索树,每一个节点上比普通二插搜索树都增加了一个存储位置表示节点的颜色,可以是Red或者Black.通过对任何一条从根到叶子的路径上各个节点上色的方式限制,红黑树确保没有一条路径会比其他路径长出2倍,从而得出红黑树是接近平衡的

在这里插入图片描述

红黑树的性质

  1. 每个节点不是红色就是黑色

  2. 根节点是黑色的

  3. 如果一个节点是红色的,则它的两个孩子节点是黑色的,红黑树不能有2个连续的红色节点

  4. 对于每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数目的黑色节点

  5. 每个叶子节点都是黑色的(此处的叶子节点指的是是空节点,比如上图的NIL)

通过以上几条性质就能保证最长路径中的节点个数不会超过最短路径节点个数的两倍,因为不能出现两个连续的红色节点,假设有一条路径全是黑色节点,由于每条路径的黑色节点个数是相等的,假设有一种情况是红黑交替,那么全黑节点路径就是最短路径的,而红黑交替路径就是最上路径,就可以保证长路径中的节点个数不会超过最短路径节点个数的两倍

最长路径和最短路径图:

如图最短路径

在这里插入图片描述

2. 红黑树节点定义

enum COLOR {RED,BLACK;
}
private static class RBTreeNode {int val;RBTreeNode parent;RBTreeNode left;RBTreeNode right;COLOR color;public RBTreeNode(int val) {this.val = val;this.left = null;this.right = null;// 插入节点默认为红色this.color = COLOR.RED;}
}

3. 红黑树的插入

红黑树插入节点默认应该插入红色的,因为如果默认插入的节点是黑色,因为红黑树的性质4每条路径中的黑色节点数目相同,如果默认插入的节点为黑色就需要新增节点,所以默认插入节点应该为红色

红黑树的插入步骤:

  1. 以二插搜索树的插入方式进行插入新节点
  2. 插入节点后,检测红黑树的性质是否被影响

我们约定cur为插入节点、p为插入节点的父亲节点、g为插入节点的爷爷节点、u为插入节点的叔叔节点

情况1

情况1:cur为红,p为红,g为黑,u存且为红

需要注意的是这里需要分两种情况,一种是看到的是一棵完整的树,另一种是一棵树的子树,此处为抽象图:

在这里插入图片描述

当把cur插入到红黑树当中,因为插入的节点是红色的,此时就不满足红黑树的性质3,所以此时就需要把p和u改成黑色的。

在这里插入图片描述

但是这还没完,假设g不是根节点,这棵树是另外一棵树的子树,那么g还有父节点。有可能g的父节点是红色的,也有可能是黑色的。假设g的父亲节点是黑色的,它的兄弟节点也是黑的。那么此时把p和u修改成的黑色节点,那么路径上的黑色节点就增加了,此时就需要把g修改成红色。那如果g本身就是根节点呢?这个可以放在最后再来处理,处理完所有情况后,不管g是红色和是黑色都把g改成黑色。

在这里插入图片描述

还有一种情况就是如果g父亲的节点本身就是一个红色的节点,如果g的父亲节点是红色的说明其上面肯定还有节点,因为根节点是黑色的,也就是g的父亲节点可定不是根节点。此时就以同样的方式继续向上调整。所以解决方式就是:**将p,u改为黑,g改为红,然后把g当成cur,继续向上调整 **

在这里插入图片描述

情况2

情况2:cur为红、p为红、u不存在或者u为黑

情况2抽象图如下:

在这里插入图片描述

需要注意的是情况2这种抽象图是在红黑树调整过程中产生的,因为它并不遵循红黑树的性质:每条路径上的黑色节点个数一致,那么其实p的右边其实是有黑色节点的,同样cur也应该是黑色节点,cur变成红色就是因为在调整过程中改变了颜色。

具象图如下:

我们在情况1的条件下修改完对应节点颜色后进行向上调整,发现就得到了情况2,所以说情况2是在调整过程中的到的。

在这里插入图片描述

调整情况2第一步就是进行右旋,再修改颜色。

  • 对g节点进行右单旋
  • 修改p的颜色为黑色、修改g的颜色为红色

在这里插入图片描述

此处讨论的是grandFather.left == parent,如果是grandFather.right == parent那么就要是左单旋g节点

情况3

情况3:cur为红,p为红,g为黑,u不存在或者u为黑

情况3也是和情况2类似也是在红黑树的调整过程中产生的,在调整过程中cur变成了红色。抽象图如下:

在这里插入图片描述

再来看一个对应的具象图:

在这里插入图片描述

对应情况3我们先要将p节点进行左单旋。

在这里插入图片描述

对p节点进行左单旋后,发现此时的树节点的颜色情况和情况2非常相似,只是引用不一致。我们回想一下情况2的条件:

  • 情况2:cur为红、p为红、u不存在或者u为黑
  • 对比情况2只是p和cur的指向不一样入下图所示

在这里插入图片描述

所以对于情况3我们只需要左旋后将p和cur的引用进行交换,再以情况2的方式进行处理即可。

还有一种情况grandFather.right == parent,此时的判断又不一样了,此时的条件是cur == parent.left,且是对parent进行右单旋,再修改指向。

其它细节问题

  • 注意每次插入后都要将根节点root的颜色修改为黑色,避免调整时root被修改成红色,从而导致问题
  • 情况2和情况3,要分两种情况讨论
    • grandFather.right == parentgrandFather.left == parent
    • grandFather.left == parent的时候情况2是对grandFather进行右单旋,当grandFather.right == parent的时候情况2是对grandFather进行左单旋
    • grandFather.left == parent情况3判断的是cur == parent.right并且对parent进行左单旋,如果是grandFather.right == parent情况3判断的是cur == parent.left并且对parent进行右单旋
    • 但情况1是不需要区分的

插入代码实现


/*** 插入节点* @param val*/
public void insert(int val) {RBTreeNode node = new RBTreeNode(val);if (root == null) {root = node;// 根节点是黑色的root.color = COLOR.BLACK;return;}// 以搜索树树的方式进行插入RBTreeNode cur = root;RBTreeNode parent = cur;while (cur != null) {parent = cur;if (cur.val > val) {cur = parent.left;} else if (cur.val < val) {cur = parent.right;} else {System.out.println("元素: "+val+"+已经存在,插入失败!");return;}}if (parent.val > val) {parent.left = node;} else {parent.right = node;}// 修改指向node.parent = parent;cur = node;//调整红黑树// 如果parent为红色说明,parent一定不是根节点while (parent != null && parent.color == COLOR.RED) {RBTreeNode grandFather = parent.parent;if (grandFather.left == parent) {RBTreeNode uncle = grandFather.right;// 情况1if (uncle != null && uncle.color == COLOR.RED) {parent.color = COLOR.BLACK;uncle.color = COLOR.BLACK;grandFather.color = COLOR.RED;// 继续向上调整cur = grandFather;parent = cur.parent;} else {//uncle不存在 或者 uncle是黑色的// 情况3:把情况3修改成情况2if (cur == parent.right) {rotateLeft(parent);// 修改引用指向RBTreeNode tmp = cur;cur = parent;parent = tmp;}// 情况2rotateRight(grandFather);parent.color = COLOR.BLACK;grandFather.color = COLOR.RED;}} else {// grandFather.right == parentRBTreeNode uncle = grandFather.left;// 情况1if (uncle != null && uncle.color == COLOR.RED) {parent.color = COLOR.BLACK;uncle.color = COLOR.BLACK;grandFather.color = COLOR.RED;// 继续向上调整cur = grandFather;parent = cur.parent;} else {//uncle不存在 或者 uncle是黑色的// 情况3:把情况3修改成情况2if (cur == parent.left) {rotateRight(parent);// 修改引用指向RBTreeNode tmp = cur;cur = parent;parent = tmp;}// 情况2:rotateLeft(grandFather);parent.color = COLOR.BLACK;grandFather.color = COLOR.RED;}}}// 关键一步,防止向上调整的时候把根节点的颜色给修改了root.color = COLOR.BLACK;
}/*** 对grandFather节点进行右单旋* @param grandFather*/
private void rotateRight(RBTreeNode grandFather) {// 定义相关节点RBTreeNode gLeft = grandFather.left;RBTreeNode gLR = gLeft.right;RBTreeNode gParent = grandFather.parent;// 修改引用grandFather.left = gLR;grandFather.parent = gLeft;gLeft.right = grandFather;if (gLR != null) {gLR.parent = gParent;}// 判断g是否是根节点if (grandFather == root) {gLeft.parent = null;root = gLeft;} else {// 如果不是根节点那么就分时gParent的左节点和右节点if (gParent.left == grandFather) {gParent.left = gLeft;} else {gParent.right = gLeft;}gLeft.parent = gParent;}}/*** 对parent节点进行左旋* @param parent*/
private void rotateLeft(RBTreeNode parent) {// 记录对应节点RBTreeNode parentR = parent.right;RBTreeNode parentRL = parentR.left;RBTreeNode pParent = parent.parent;// 修改节点parent.right = parentRL;// 如果parentRL存在if (parentRL != null) {parentRL.parent = parent;}parent.parent = parentR;parentR.left = parent;// 如果旋转的是根节点if (parent == root) {root = parentR;parentR.parent = null;} else {// 如果旋转的不是根节点就判断旋转的是pParent的左子树还是右子树if (pParent.left == parent) {pParent.left = parentR;} else {pParent.right = parentR;}parentR.parent = pParent;}
}

4. 红黑树的验证

根据红黑树的性质编写代码验证:

  1. 每个节点不是红色就是黑色

  2. 根节点是黑色的

  3. 如果一个节点是红色的,则它的两个孩子节点是黑色的,红黑树不能有2个连续的红色节点

  4. 对于每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数目的黑色节点

  5. 再对红黑树进行中序遍历验证

/*** 判断当前是否红黑树* @return*/
public boolean isRBTree() {if (root == null) {return true;}// 1.根节点为黑色if (root.color != COLOR.BLACK) {System.out.println("根节点不为黑色!");return false;}// 计算某一条黑色节点个数int checkNum = 0;RBTreeNode cur = root;while (cur != null) {if (cur.color == COLOR.BLACK) {checkNum++;}cur = cur.left;}// 中序遍历inorderTraversal(root);// 红黑树不能有两个连续的红色节点&& 每条路径的黑色节点个数一致return checkRedColor(root) && checkBlackNum(root,0,checkNum);
}/*** 判断是否有两个连续红色节点* @param node* @return*/
private boolean checkRedColor(RBTreeNode node) {if (node == null) {return true;}if (node.color == COLOR.RED) {if (node.left != null && node.left.color == COLOR.RED) {return false;}if (node.right !=  null && node.right.color == COLOR.RED) {return false;}}return checkRedColor(node.left) && checkRedColor(node.right);
}/*** 判断每条路径上的黑色节点个数* @param root* @param count* @param checkNum* @return*/
private boolean checkBlackNum(RBTreeNode root,int count,int checkNum) {if (root == null) {return true;}if (root.color == COLOR.BLACK) {count++;}if (root.left == null && root.right == null && count != checkNum) {System.out.println("每条路径黑色节点个数不一致");return false;}return checkBlackNum(root.left,count,checkNum) && checkBlackNum(root.right,count,checkNum);
}
private void inorderTraversal(RBTreeNode root) {if (root == null) return;inorderTraversal(root.left);System.out.print(root.val+" ");inorderTraversal(root.right);
}

5.性能分析

红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是 O ( l o g n ) O(logn) O(logn)

  • AVL树通过左旋右旋来保证树的绝对平衡(左右子树的高度差不超过1),所以旋转的次数比较多

  • 红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,通过修改颜色来降低旋转的次数。

  • 红黑树对比AVL树,其通过修改颜色大大减低了旋转的次数,在增删的场景中使用红黑树更优,而AVL树只是适合查找,所以红黑树在实际运用更多的是红黑树,比如说TreeMap和TreeSet。


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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【已解决】ubuntu 16.04安装最新版本google chrome出错, 旧版本chrome浏览器安装流程

ubuntu 16.04 按照常规的Chrome 安装流程总是出错如下&#xff1a; Selecting previously unselected package google-chrome-stable. (Reading database ... 231747 files and directories currently installed.) Preparing to unpack google-chrome-stable_current_amd64.de…

自己写过比较蠢的代码:从失败中学习的经验

文章目录 引言1. 代码没有注释2. 长函数和复杂逻辑3. 不恰当的变量名4. 重复的代码5. 不适当的异常处理6. 硬编码的敏感信息7. 没有单元测试结论 &#x1f389; 自己写过比较蠢的代码&#xff1a;从失败中学习的经验 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨博客主页&a…

msvcr71.dll、msvcp71.dll丢失怎么办?快速修复方法分享

msvcr71.dll 是一个动态链接库文件&#xff0c;它包含了 C 运行时库的一些函数和类&#xff0c;例如全局对象、异常处理、内存管理、文件操作等。它是 Visual Studio 2003 及以上版本中的一部分&#xff0c;用于支持 C 应用程序的运行。如果 msvcr71.dll 丢失或损坏&#xff0c…

新手学习:ArcGIS对shp文件裁剪

新手学习&#xff1a;ArcGIS对SHP文件裁剪 新手学习 记录每个步骤&#xff0c;因为有很多控件可能刚开始还不熟悉&#xff0c;根本不知道在哪里&#xff0c;所以写的比较详细。 1.添加要裁剪的shp文件 2.查看shp文件的地理坐标系 双击shp文件&#xff0c;就可以查看shp文件的…

倒置字符串(牛客)

一、题目 二、代码 #include <iostream> #include<string> using namespace std;int main() {string s;getline(cin, s);string s2;int i s.length() - 1;int prev i;int next 0;while (i > 0 && prev > 0) { //从字符串的最后往前遍历if (s[pre…

React+Node——next.js 构建前后端项目

一、安装全局依赖 npm i -g create-next-app二、创建next项目 create-next-app react-next-demo //或 create-next-app react-next-demo --typescript三、加载mysql依赖 npm i -S mysql2四、运行项目 npm run dev五、创建db文件目录&#xff0c;目录下创建index.ts import…

HTML常用基本元素总结

<!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title> biao qian</title> </head> <body><h1>这是标题1</h1> <h2>这是标题2</h2> <h3>这是标题3</h3><p> 这…

负载均衡 —— SpringCloud Netflix Ribbon

Ribbon 简介 Ribbon 是 Netfix 客户端的负载均衡器&#xff0c;可对 HTTP 和 TCP 客户端的行为进行控制。为 Ribbon 配置服务提供者地址后&#xff0c;Ribbon 就可以基于某种负载均衡算法自动帮助服务消费者去请求。Ribbon 默认提供了很多负载均衡算法&#xff0c;例如轮询、随…

IAP固件升级分几步?(Qt上位机、)

前言 这周一直想做一个IAP固件升级的上位机&#xff0c;然后把升级流程全都搞懂 有纰漏请指出&#xff0c;转载请说明。 学习交流请发邮件 1280253714qq.com IAP原理 IAP的原理我就不多赘述了&#xff0c;这里贴上几位大佬的文章 STM32CubeIDE IAP原理讲解&#xff0c;及U…

学会使用Git 和 GitHub

Git 和 GitHub 都是程序员每天都要用到的东西 —— 前者是目前最先进的 版本控制工具&#xff0c;拥有最多的用户&#xff0c;且管理着地球上最庞大的代码仓库&#xff1b;而后者是全球最大 同性交友 代码托管平台、开源社区。 在没有这两个工具时&#xff0c;编程可能是这样的…

驱动代码整理

一&#xff0c;控制LED灯控制实验 头文件 #ifndef __HEAD_H__ #define __HEAD_H__#define LED1_MODER 0X50006000 #define LED1_ODR 0X50006014 #define LED1_RCC 0X50000A28#endif 驱动 #include <linux/init.h> #include <linux/module.h> #include &l…

洛谷刷题入门篇:分支结构

今天又来了&#xff0c;刷题刷题&#xff0c;我爱刷题&#xff0c;题单链接如下&#xff1a; https://www.luogu.com.cn/training/101#problems 一、【深基1-2】小学数学 N 合一 题目如下&#xff1a;https://www.luogu.com.cn/problem/P2433 题目描述 问题 1 请输出 I lov…

【C语言】指针经典笔试题(上)

C语言的一大重头戏就是指针。 对于指针有一些认识&#xff1a; 1.指针是存放变量的地址&#xff0c;一般说的指针和指针变量是一个概念。 2.地址的单位是字节&#xff0c;大小在不同编译器环境下有所不同&#xff0c;32位机器是4个字节&#xff0c;64位机器是8个字节。 3.数组名…

C# ref 学习1

ref 关键字用在四种不同的上下文中&#xff1b; 1.在方法签名和方法调用中&#xff0c;按引用将参数传递给方法。 2.在方法签名中&#xff0c;按引用将值返回给调用方。 3.在成员正文中&#xff0c;指示引用返回值是否作为调用方欲修改的引用被存储在本地&#xff0c;或在一般…

大厂面试-16道面试题

1 java集合类有哪些&#xff1f; List是有序的Collection&#xff0c;使用此接口能够精确的控制每个元素的插入位置&#xff0c;用户能根据索引访问List中元素。常用的实现List的类有LinkedList&#xff0c;ArrayList&#xff0c;Vector&#xff0c;Stack。 ArrayList是容量…

C语言内存函数的使用、剖析及模拟实现

目录 一、内存拷贝函数——memcpy 1.函数声明&#xff1a; 注意&#xff1a; 2.函数使用用例&#xff1a; 3.memcpy函数的模拟实现&#xff1a; 二、内存拷贝函数2——memmove 1.函数声明&#xff1a; 2.memmove函数的模拟实现 三、内存比较函数——memcmp 1.函数声明…

卸载Visual Studio 2010学习版 —— 卸载VCExpress

目录 最初安装Visual Studio 2010学习版是因为计算机二级 C语言考试而装&#xff0c;现如今考完试后便可卸载掉了&#xff0c;安装简便而卸载却没有uninstall.exe文件。故本文提供卸载方式。 进入到程序目录&#xff0c;找到setup.exe文件&#xff0c;也可以在程序目录搜索set…

【lesson10】进程状态

文章目录 认识进程状态新建运行阻塞挂起 Linux具体的进程状态RSDtTXZ是什么为什么 认识进程状态 上面就是各种进程状态&#xff0c;上面都是理论进程状态理论进程状态放在哪个操作系统中都是正确的&#xff0c;但是具体的操作系统实现可能又会有所不同。 下面我们来理解进程状态…

springBoot对接多个mq并且实现延迟队列---未完待续

mq调用流程 创建消息转换器 package com.wd.config;import org.springframework.amqp.support.converter.Jackson2JsonMessageConverter; import org.springframework.amqp.support.converter.MessageConverter; import org.springframework.context.annotation.Bean; import o…