红黑树刨析(删除部分)

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

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

笔记整理—内核!启动!—kernel部分(2)从汇编阶段到start_kernel

kernel起始与ENTRY(stext),和uboot一样,都是从汇编阶段开始的,因为对于kernel而言,还没进行栈的维护,所以无法使用c语言。_HEAD定义了后面代码属于段名为.head .text的段。         内核起始部分代码被解压代码调用,前面关于uboot的文章中有提到过(eg:zImage)。uboot启动是无条件的,只要代码的位置对,上电就工作,kern

如何恢复回收站中已删除/清空的文件

回收站清空后如何恢复已删除的文件?是否可以恢复永久删除的文件?或者最糟糕的是,如果文件直接被删除怎么办?本文将向您展示清空回收站后恢复已删除数据的最佳方法。 回收站清空后如何恢复已删除的文件? “回收站清空后我还能恢复已删除的文件吗?” 答案是肯定的,但是在这种情况下您将需要一个  回收站恢复工具 来从回收站中检索文件: 错误/永久删除回收站或任何数字存储设备中的文件 直接删除的文件/

项目实战系列三: 家居购项目 第四部分

购物车 🌳购物车🍆显示购物车🍆更改商品数量🍆清空购物车&&删除商品 🌳生成订单 🌳购物车 需求分析 1.会员登陆后, 可以添加家居到购物车 2.完成购物车的设计和实现 3.每添加一个家居,购物车的数量+1, 并显示 程序框架图 1.新建src/com/zzw/furns/entity/CartItem.java, CartItem-家居项模型 /***

码蹄集部分题目(2024OJ赛9.4-9.8;线段树+树状数组)

1🐋🐋配对最小值(王者;树状数组) 时间限制:1秒 占用内存:64M 🐟题目思路 MT3065 配对最小值_哔哩哔哩_bilibili 🐟代码 #include<bits/stdc++.h> using namespace std;const int N=1e5+7;int a[N],b[N],c[N],n,q;struct QUERY{int l,r,id;}que

Linux 删除 当前下的 mysql-8.0.31 空文件夹

在Linux中,如果你想要删除当前目录下的名为mysql-8.0.31的空文件夹(即该文件夹内没有任何文件或子文件夹),你可以使用rmdir命令。但是,如果mysql-8.0.31文件夹并非完全为空(即它包含文件或子文件夹),rmdir命令会失败。 如果你的目标是删除mysql-8.0.31文件夹及其内部的所有内容(无论是否为空),你应该使用rm命令结合-r(或-R,它们是等价的)选项来递归地删

如何删除不小心上传到git远程仓库中的.idea .iml文件

如果在开始的时候不配置,gitignore文件或者文件配置不正确,初始化上传的时候就会有一些不必要的信息上传上去 如果已经存在了一些文件在git远程仓库中,如。idea,.iml文件等。 首先在项目中定义一个  .gitignore文件,简单的实例如下也可以用idea中的gitignore插件 .DS_Storeclasses/*.settings/target/.classpath

关于断言的部分用法

1、带变量的断言  systemVerilog assertion 中variable delay的使用,##[variable],带变量的延时(可变延时)_assertion中的延时-CSDN博客 2、until 的使用 systemVerilog assertion 中until的使用_verilog until-CSDN博客 3、throughout的使用   常用于断言和假设中的