红黑树刨析(删除部分)

2024-08-30 21:52
文章标签 删除 红黑树 部分 刨析

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

文章目录

    • 红黑树删除节点情景分析
      • 情景1:删除节点左右子树都为空
        • 情景1.1:删除节点为红色
        • 情景1.2:删除节点为黑色
          • 情况1.2.1:删除节点的兄弟节点是红色
          • 情景1.2.2:删除节点的兄弟节点是黑色
            • 情景1.2.2.1:删除节点的兄弟节点是黑色,兄弟节点的右节点是红色,兄弟节点的左节点是空或者红色
            • 情景1.2.2.2:删除节点的兄弟节点是黑色,兄弟节点的左节点是红色,兄弟节点的右节点是空(右节点是红色按照情况1.2.2.1讨论就可以了)
            • 情景1.2.2.3:删除节点的兄弟节点是黑色,兄弟节点无孩子
      • 情景2:删除节点有一个子树(左子树或者右子树)
      • 情景3:删除节点有两个子树

红黑树删除节点情景分析

情景1:删除节点左右子树都为空

情景1.1:删除节点为红色

那么可以直接将p删除,不影响平衡性

暂时无法在飞书文档外展示此内容

以下这两种情况都符合

在这里插入图片描述
在这里插入图片描述

情景1.2:删除节点为黑色

删除节点为黑色的话就不太平衡了,此时我们就需要看情况讨论了

情况1.2.1:删除节点的兄弟节点是红色

将父亲节点和兄弟节点颜色互换,然后再将父亲节点左旋,此时这就变成了情景1.2.2

在这里插入图片描述

情景1.2.2:删除节点的兄弟节点是黑色

如果兄弟节点为黑色,那么只有两种情况

情景1.2.2.1:删除节点的兄弟节点是黑色,兄弟节点的右节点是红色,兄弟节点的左节点是空或者红色

此时如果我们删除黑色节点p,那么就不平衡了,我们看一下pp - ppr - pprr三个节点,这三个点在一条线上,我们可以借助pprr这个红色节点变成黑色节点来保持平衡。首先让ppppr互换颜色,然后再将pp左旋,那么删除p之后,右边没有黑色节点,直接让pprr变成黑色就行了。在这里插入图片描述

情景1.2.2.2:删除节点的兄弟节点是黑色,兄弟节点的左节点是红色,兄弟节点的右节点是空(右节点是红色按照情况1.2.2.1讨论就可以了)

直接让兄弟右旋,然后将兄弟和侄子互换颜色,就变成了情景1.2.2.1
在这里插入图片描述

情景1.2.2.3:删除节点的兄弟节点是黑色,兄弟节点无孩子

情景1.2.2.3.1:删除节点的兄弟节点是黑色,兄弟节点无孩子,父亲节点是红色

删除节点P之后,左右两边不平衡了,可以直接将父节节点变成黑色,兄弟节点变成红色,这样就平衡了。
在这里插入图片描述
情景1.2.2.3.2:删除节点的兄弟节点是黑色,兄弟节点无孩子,父亲节点是黑色

直接将兄弟节点变成红色,这样就平衡了。但是经过pp的路径上的黑色节点数会少1,这个时候在以pp作为起始点,继续平衡操作,这里可以把pp和ppr当作一个节点pp这样一直向上,直到新的起始点为根节点。
在这里插入图片描述

情景2:删除节点有一个子树(左子树或者右子树)

以下情景不满足红黑树性质不可能出现:
在这里插入图片描述
只有下面两种情况可能出现:

删除节点是黑色,子节点是红色

那么可以直接让子孩子替换p,颜色变成黑色就可以了。
在这里插入图片描述

情景3:删除节点有两个子树

首先找到删除节点的后继节点,再将后继节点和删除节点替换,问题就变成删除替换节点的问题,而且替换节点要么无子树,要么有一个节点,问题就变回了情景1或者情景2。

JDK1.8中hashMap中的删除红黑树节点的源码,我做了一部分的改进,方便阅读。

 final void removeTreeNode(MyHashMap<K, V> map, Node<K, V>[] tab,boolean movable) {/*** 链表的处理*/int n;// 如果当前哈希表为空直接返回if (tab == null || (n = tab.length) == 0)return;// 计算当前节点在hash表的索引位置int index = (n - 1) & hash;// fisrt : t头节点TreeNode<K, V> first = (TreeNode<K, V>) tab[index];// 如果索引位置的红黑树为空if (first == null) {return;}// root:根节点TreeNode<K, V> root = first;// rl : root的左节点TreeNode<K, V> rl;// succ:节点的后继节点TreeNode<K, V> succ = (TreeNode<K, V>) next;// pred:节点的前驱节点TreeNode<K, V> pred = prev;// 如果根节点为空,则当前节点就是头节点,直接删除if (pred == null) {first = succ;tab[index] = succ;// 根节点不为空,当前节点为中间某个节点,删除中间节点} else {// 前驱的后继pred.next = succ;}// 后继的前驱if (succ != null) {succ.prev = pred;}// 如果root的父节点不为空,说明该节点并不是真正的红黑树根节点,需要重新查找根节点if (root.parent != null) {root = root.parent;}// 通过root节点来判断此红黑树是否太小, 如果是太小了则调用untreeify方法转为链表节点并返回// (转链表后就无需再进行下面的红黑树处理)// 太小的判定依据:根节点为null,或者根的右节点为null,或者根的左节点为null,或者根的左节点的左节点为null// 这里并没有遍历整个红黑树去统计节点数是否小于等于阈值6,而是直接判断这几种情况,// 来决定要不要转换为链表,因为这几种情况一般就涵盖了节点数小于6的情况,这样执行效率也会变高if (root == null || root.right == null ||(rl = root.left) == null || rl.left == null) {tab[index] = first.untreeify(map);  // too smallreturn;}/*** 红黑树的处理*/TreeNode<K, V> p = this;TreeNode<K, V> pl = left;TreeNode<K, V> pr = right;// replacement:替换节点TreeNode<K, V> replacement;if (pl != null && pr != null) {// 找到当前节点的后继TreeNode<K, V> s = pr;TreeNode<K, V> sl = s.left;while (sl != null) {s = sl;sl = s.left;}// 交换p和s的颜色boolean c = s.red;s.red = p.red;p.red = c;TreeNode<K, V> sr = s.right;TreeNode<K, V> pp = p.parent;// 如果p的后继节点s恰好是p的右节点,那说明pr没有左节点// 那么就可以直接将pr替换为pif (s == pr) {// 先处理pp.parent = s;p.left = null;p.right = sr;if (sr != null) {sr.parent = p;}// 处理ss.right = p;s.left = pl;pl.parent = s;s.parent = pp;if (pp == null) {root = s;} else if (p == pp.left) {pp.left = s;} else {pp.right = s;}} else {// 将p和s互换TreeNode<K, V> sp = s.parent;p.parent = sp;if (s == sp.left) {sp.left = p;} else {sp.right = p;}p.left = null;p.right = sr;if (sr != null) {sr.parent = p;}s.parent = pp;if (pp == null) {root = s;} else if (p == pp.left) {pp.left = s;} else {pp.right = s;}s.left = pl;s.right = pr;pr.parent = s;}// 如果sr不等于null,那需要p和sr替换掉if (sr != null) {replacement = sr;// 如果sr等于null,此时p无子树,直接删掉就可以} else {replacement = p;}// 走到这里说明pr为null,pl不为null} else if (pl != null) {replacement = pl;// 走到这里说明pl为null,pr不为null} else if (pr != null) {replacement = pr;}// 到这里,说明p的左右节点都为nullelse {replacement = p;}// 删掉当前节点pif (replacement != p) {TreeNode<K, V> pp = replacement.parent = p.parent;// 当p只有一个子树的时候,p的父节点可能为nullif (pp == null) {root = replacement;} else if (p == pp.left) {pp.left = replacement;} else {pp.right = replacement;}// 删掉p节点p.left = p.right = p.parent = null;}// 如果p节点是红色,那不影响树的结构TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);if (replacement == p) {TreeNode<K, V> pp = p.parent;p.parent = null;if (pp != null) {if (p == pp.left) {pp.left = null;} else {pp.right = null;}}}}static <K, V> TreeNode<K, V> balanceDeletion(TreeNode<K, V> root,TreeNode<K, V> x) {TreeNode<K, V> xp, xpl, xpr;while (true) {// 如果x为null或者是根节点,说明已经删除完了if (x == null || x == root) {return root;// 父节点为null,说明是根节点} else if ((xp = x.parent) == null) {x.red = false;return x;// 如果x是红色的,那么直接让它变成黑色的就行了// 因为父节点是黑色的,x节点直接代替他成为黑色的就行了// 这对应情景1.1或情景2} else if (x.red) {x.red = false;return root;// x既不是根节点,也不是红色// x是父亲的左节点} else if ((xpl = xp.left) == x) {// 此时对应于情景1.2.1,父兄换色,然后对x在进行一次平衡if ((xpr = xp.right) != null && xpr.red) {xpr.red = false;xp.red = true;root = rotateLeft(root, xp);xpr = (xp = x.parent) == null ? null : xp.right;}if (xpr == null) {// TODO: 这里应该不可能出现System.out.println("..........");x = xp;} else {TreeNode<K, V> sl = xpr.left, sr = xpr.right;// 此时xpr只能是黑色// 这里if判断成功的可能条件:// 1.sl == null,sr == null (对应情景1.2.2.3)// 2.sl == null,sr == black (不可能)// 3.sl == black,sr == null (不可能)// 4.sl == black,sr == black (不可能)if ((sr == null || !sr.red) &&(sl == null || !sl.red)) {xpr.red = true;x = xp;} else {// 进入这里的可能条件// 1.sl == null,sr == red (对应情景1.2.2.1)// 2.sl == red,sr == null (对应情景1.2.2.2)// 3.sl == red,sr == red (对应情景1.2.2.1)// 4.sl == black,sr == red (不存在)// 4.sl == red,sr == black (不存在)// 条件2if (sr == null) {// 情景1.2.2.2sl.red = false;xpr.red = true;root = rotateRight(root, xpr);xpr = (xp = x.parent) == null ? null : xp.right;}// 此时就变成了场景1.2.2.1if (xpr != null) {// 父兄换色xpr.red = xp.red;if ((sr = xpr.right) != null) {sr.red = false;}}if (xp != null) {xp.red = false;root = rotateLeft(root, xp);}x = root;}}} else {// 如果xpl为红色,那xp和xpl的孩子肯定为黑色if (xpl != null && xpl.red) {xpl.red = false;xp.red = true;root = rotateRight(root, xp);xpl = (xp = x.parent) == null ? null : xp.left;}if (xpl == null) {x = xp;} else {TreeNode<K, V> sl = xpl.left, sr = xpl.right;if ((sl == null || !sl.red) && (sr == null || !sr.red)) {xpl.red = true;x = xp;} else {if (sl == null) {sr.red = false;xpl.red = true;root = rotateLeft(root, xpl);xpl = (xp = x.parent) == null ?null : xp.left;}if (xpl != null) {xpl.red = xp.red;if ((sl = xpl.left) != null)sl.red = false;}if (xp != null) {xp.red = false;root = rotateRight(root, xp);}x = root;}}}}}
}

这篇关于红黑树刨析(删除部分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

SQL Server清除日志文件ERRORLOG和删除tempdb.mdf

《SQLServer清除日志文件ERRORLOG和删除tempdb.mdf》数据库再使用一段时间后,日志文件会增大,特别是在磁盘容量不足的情况下,更是需要缩减,以下为缩减方法:如果可以停止SQLSe... 目录缩减 ERRORLOG 文件(停止服务后)停止 SQL Server 服务:找到错误日志文件:删除

mysql删除无用用户的方法实现

《mysql删除无用用户的方法实现》本文主要介绍了mysql删除无用用户的方法实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 1、删除不用的账户(1) 查看当前已存在账户mysql> select user,host,pa

MySQL InnoDB引擎ibdata文件损坏/删除后使用frm和ibd文件恢复数据

《MySQLInnoDB引擎ibdata文件损坏/删除后使用frm和ibd文件恢复数据》mysql的ibdata文件被误删、被恶意修改,没有从库和备份数据的情况下的数据恢复,不能保证数据库所有表数据... 参考:mysql Innodb表空间卸载、迁移、装载的使用方法注意!此方法只适用于innodb_fi

shell脚本自动删除30天以前的文件(最新推荐)

《shell脚本自动删除30天以前的文件(最新推荐)》该文章介绍了如何使用Shell脚本自动删除指定目录下30天以前的文件,并通过crontab设置定时任务,此外,还提供了如何使用Shell脚本删除E... 目录shell脚本自动删除30天以前的文件linux按照日期定时删除elasticsearch索引s

docker如何删除悬空镜像

《docker如何删除悬空镜像》文章介绍了如何使用Docker命令删除悬空镜像,以提高服务器空间利用率,通过使用dockerimage命令结合filter和awk工具,可以过滤出没有Tag的镜像,并将... 目录docChina编程ker删除悬空镜像前言悬空镜像docker官方提供的方式自定义方式总结docker