红黑树刨析(删除部分)

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

相关文章

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语

一文详解Git中分支本地和远程删除的方法

《一文详解Git中分支本地和远程删除的方法》在使用Git进行版本控制的过程中,我们会创建多个分支来进行不同功能的开发,这就容易涉及到如何正确地删除本地分支和远程分支,下面我们就来看看相关的实现方法吧... 目录技术背景实现步骤删除本地分支删除远程www.chinasem.cn分支同步删除信息到其他机器示例步骤

python删除xml中的w:ascii属性的步骤

《python删除xml中的w:ascii属性的步骤》使用xml.etree.ElementTree删除WordXML中w:ascii属性,需注册命名空间并定位rFonts元素,通过del操作删除属... 可以使用python的XML.etree.ElementTree模块通过以下步骤删除XML中的w:as

Navicat数据表的数据添加,删除及使用sql完成数据的添加过程

《Navicat数据表的数据添加,删除及使用sql完成数据的添加过程》:本文主要介绍Navicat数据表的数据添加,删除及使用sql完成数据的添加过程,具有很好的参考价值,希望对大家有所帮助,如有... 目录Navicat数据表数据添加,删除及使用sql完成数据添加选中操作的表则出现如下界面,查看左下角从左

如何在Mac上彻底删除Edge账户? 手动卸载Edge浏览器并清理残留文件技巧

《如何在Mac上彻底删除Edge账户?手动卸载Edge浏览器并清理残留文件技巧》Mac上的Edge账户里存了不少网站密码和个人信息,结果同事一不小心打开了,简直尴尬到爆炸,想要卸载edge浏览器并清... 如果你遇到 Microsoft Edge 浏览器运行迟缓、频繁崩溃或网页加载异常等问题,可以尝试多种方

Java实现删除文件中的指定内容

《Java实现删除文件中的指定内容》在日常开发中,经常需要对文本文件进行批量处理,其中,删除文件中指定内容是最常见的需求之一,下面我们就来看看如何使用java实现删除文件中的指定内容吧... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细介绍3.1 Ja

Redis过期删除机制与内存淘汰策略的解析指南

《Redis过期删除机制与内存淘汰策略的解析指南》在使用Redis构建缓存系统时,很多开发者只设置了EXPIRE但却忽略了背后Redis的过期删除机制与内存淘汰策略,下面小编就来和大家详细介绍一下... 目录1、简述2、Redis http://www.chinasem.cn的过期删除策略(Key Expir

使用C#删除Excel表格中的重复行数据的代码详解

《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍... 目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元

Python对PDF书签进行添加,修改提取和删除操作

《Python对PDF书签进行添加,修改提取和删除操作》PDF书签是PDF文件中的导航工具,通常包含一个标题和一个跳转位置,本教程将详细介绍如何使用Python对PDF文件中的书签进行操作... 目录简介使用工具python 向 PDF 添加书签添加书签添加嵌套书签Python 修改 PDF 书签Pytho