深读源码-java集合之TreeMap源码分析（三）

2023-11-07 09:32
文章标签 java 分析 源码 集合 深读 treemap

本文主要是介绍深读源码-java集合之TreeMap源码分析（三），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

删除元素

删除元素本身比较简单，就是采用二叉树的删除规则。

（1）如果删除的位置有两个叶子节点，则从其右子树中取最小的元素放到删除的位置，然后把删除位置移到替代元素的位置，进入下一步。

（2）如果删除的位置只有一个叶子节点（有可能是经过第一步转换后的删除位置），则把那个叶子节点作为替代元素，放到删除的位置，然后把这个叶子节点删除。

（3）如果删除的位置没有叶子节点，则直接把这个删除位置的元素删除即可。

（4）针对红黑树，如果删除位置是黑色节点，还需要做再平衡。

（5）如果有替代元素，则以替代元素作为当前节点进入再平衡。

（6）如果没有替代元素，则以删除的位置的元素作为当前节点进入再平衡，平衡之后再删除这个节点。

public V remove(Object key) {// 获取节点Entry<K,V> p = getEntry(key);if (p == null)return null;V oldValue = p.value;// 删除节点deleteEntry(p);// 返回删除的valuereturn oldValue;
}private void deleteEntry(Entry<K,V> p) {// 修改次数加1modCount++;// 元素个数减1size--;if (p.left != null && p.right != null) {// 如果当前节点既有左子节点，又有右子节点// 取其右子树中最小的节点Entry<K,V> s = successor(p);// 用右子树中最小节点的值替换当前节点的值p.key = s.key;p.value = s.value;// 把右子树中最小节点设为当前节点p = s;// 这种情况实际上并没有删除p节点，而是把p节点的值改了，实际删除的是p的后继节点}// 如果原来的当前节点（p）有2个子节点，则当前节点已经变成原来p的右子树中的最小节点了，也就是说其没有左子节点了// 到这一步，p肯定只有一个子节点了// 如果当前节点有子节点，则用子节点替换当前节点Entry<K,V> replacement = (p.left != null ? p.left : p.right);if (replacement != null) {// 把替换节点直接放到当前节点的位置上（相当于删除了p，并把替换节点移动过来了）replacement.parent = p.parent;if (p.parent == null)root = replacement;else if (p == p.parent.left)p.parent.left  = replacement;elsep.parent.right = replacement;// 将p的各项属性都设为空p.left = p.right = p.parent = null;// 如果p是黑节点，则需要再平衡if (p.color == BLACK)fixAfterDeletion(replacement);} else if (p.parent == null) {// 如果当前节点就是根节点，则直接将根节点设为空即可root = null;} else {// 如果当前节点没有子节点且其为黑节点，则把自己当作虚拟的替换节点进行再平衡if (p.color == BLACK)fixAfterDeletion(p);// 平衡完成后删除当前节点（与父节点断绝关系）if (p.parent != null) {if (p == p.parent.left)p.parent.left = null;else if (p == p.parent.right)p.parent.right = null;p.parent = null;}}
}

删除再平衡

经过上面的处理，真正删除的肯定是黑色节点才会进入到再平衡阶段。

因为删除的是黑色节点，导致整颗树不平衡了，所以这里我们假设把删除的黑色赋予当前节点，这样当前节点除了它自已的颜色还多了一个黑色，那么：

（1）如果当前节点是根节点，则直接涂黑即可，不需要再平衡；

（2）如果当前节点是红+黑节点，则直接涂黑即可，不需要平衡；

（3）如果当前节点是黑+黑节点，则我们只要通过旋转把这个多出来的黑色不断的向上传递到一个红色节点即可，这又可能会出现以下四种情况：

（假设当前节点为父节点的左子节点）

情况策略
1）x是黑+黑节点，x的兄弟是红节点（1）将兄弟节点设为黑色；
（2）将父节点设为红色；
（3）以父节点为支点进行左旋；
（4）重新设置x的兄弟节点，进入下一步；
2）x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的两个子节点都是黑色（1）将兄弟节点设置为红色；
（2）将x的父节点作为新的当前节点，进入下一次循环；
3）x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的右子节点为黑色，左子节点为红色（1）将兄弟节点的左子节点设为黑色；
（2）将兄弟节点设为红色；
（3）以兄弟节点为支点进行右旋；
（4）重新设置x的兄弟节点，进入下一步；
3）x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的右子节点为红色，左子节点任意颜色（1）将兄弟节点的颜色设为父节点的颜色；
（2）将父节点设为黑色；
（3）将兄弟节点的右子节点设为黑色；
（4）以父节点为支点进行左旋；
（5）将root作为新的当前节点（退出循环）；

（假设当前节点为父节点的右子节点，正好反过来）

情况策略
1）x是黑+黑节点，x的兄弟是红节点（1）将兄弟节点设为黑色；
（2）将父节点设为红色；
（3）以父节点为支点进行右旋；
（4）重新设置x的兄弟节点，进入下一步；
2）x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的两个子节点都是黑色（1）将兄弟节点设置为红色；
（2）将x的父节点作为新的当前节点，进入下一次循环；
3）x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的左子节点为黑色，右子节点为红色（1）将兄弟节点的右子节点设为黑色；
（2）将兄弟节点设为红色；
（3）以兄弟节点为支点进行左旋；
（4）重新设置x的兄弟节点，进入下一步；
3）x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的左子节点为红色，右子节点任意颜色（1）将兄弟节点的颜色设为父节点的颜色；
（2）将父节点设为黑色；
（3）将兄弟节点的左子节点设为黑色；
（4）以父节点为支点进行右旋；
（5）将root作为新的当前节点（退出循环）；

让我们来看看TreeMap中的实现：

/*** 删除再平衡*（1）每个节点或者是黑色，或者是红色。*（2）根节点是黑色。*（3）每个叶子节点（NIL）是黑色。（注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！）*（4）如果一个节点是红色的，则它的子节点必须是黑色的。*（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。*/
private void fixAfterDeletion(Entry<K,V> x) {// 只有当前节点不是根节点且当前节点是黑色时才进入循环while (x != root && colorOf(x) == BLACK) {if (x == leftOf(parentOf(x))) {// 如果当前节点是其父节点的左子节点// sib是当前节点的兄弟节点Entry<K,V> sib = rightOf(parentOf(x));// 情况1）如果兄弟节点是红色if (colorOf(sib) == RED) {// （1）将兄弟节点设为黑色setColor(sib, BLACK);// （2）将父节点设为红色setColor(parentOf(x), RED);// （3）以父节点为支点进行左旋rotateLeft(parentOf(x));// （4）重新设置x的兄弟节点，进入下一步sib = rightOf(parentOf(x));}if (colorOf(leftOf(sib))  == BLACK &&colorOf(rightOf(sib)) == BLACK) {// 情况2）如果兄弟节点的两个子节点都是黑色// （1）将兄弟节点设置为红色setColor(sib, RED);// （2）将x的父节点作为新的当前节点，进入下一次循环x = parentOf(x);} else {if (colorOf(rightOf(sib)) == BLACK) {// 情况3）如果兄弟节点的右子节点为黑色// （1）将兄弟节点的左子节点设为黑色setColor(leftOf(sib), BLACK);// （2）将兄弟节点设为红色setColor(sib, RED);// （3）以兄弟节点为支点进行右旋rotateRight(sib);// （4）重新设置x的兄弟节点sib = rightOf(parentOf(x));}// 情况4）// （1）将兄弟节点的颜色设为父节点的颜色setColor(sib, colorOf(parentOf(x)));// （2）将父节点设为黑色setColor(parentOf(x), BLACK);// （3）将兄弟节点的右子节点设为黑色setColor(rightOf(sib), BLACK);// （4）以父节点为支点进行左旋rotateLeft(parentOf(x));// （5）将root作为新的当前节点（退出循环）x = root;}} else { // symmetric// 如果当前节点是其父节点的右子节点// sib是当前节点的兄弟节点Entry<K,V> sib = leftOf(parentOf(x));// 情况1）如果兄弟节点是红色if (colorOf(sib) == RED) {// （1）将兄弟节点设为黑色setColor(sib, BLACK);// （2）将父节点设为红色setColor(parentOf(x), RED);// （3）以父节点为支点进行右旋rotateRight(parentOf(x));// （4）重新设置x的兄弟节点sib = leftOf(parentOf(x));}if (colorOf(rightOf(sib)) == BLACK &&colorOf(leftOf(sib)) == BLACK) {// 情况2）如果兄弟节点的两个子节点都是黑色// （1）将兄弟节点设置为红色setColor(sib, RED);// （2）将x的父节点作为新的当前节点，进入下一次循环x = parentOf(x);} else {if (colorOf(leftOf(sib)) == BLACK) {// 情况3）如果兄弟节点的左子节点为黑色// （1）将兄弟节点的右子节点设为黑色setColor(rightOf(sib), BLACK);// （2）将兄弟节点设为红色setColor(sib, RED);// （3）以兄弟节点为支点进行左旋rotateLeft(sib);// （4）重新设置x的兄弟节点sib = leftOf(parentOf(x));}// 情况4）// （1）将兄弟节点的颜色设为父节点的颜色setColor(sib, colorOf(parentOf(x)));// （2）将父节点设为黑色setColor(parentOf(x), BLACK);// （3）将兄弟节点的左子节点设为黑色setColor(leftOf(sib), BLACK);// （4）以父节点为支点进行右旋rotateRight(parentOf(x));// （5）将root作为新的当前节点（退出循环）x = root;}}}// 退出条件为多出来的黑色向上传递到了根节点或者红节点// 则将x设为黑色即可满足红黑树规则setColor(x, BLACK);
}

删除元素举例

假设我们有下面这样一颗红黑树。

treemap-delete1

我们删除6号元素，则从右子树中找到了最小元素7，7又没有子节点了，所以把7作为当前节点进行再平衡。

我们看到7是黑节点，且其兄弟为黑节点，且其兄弟的两个子节点都是红色，满足情况4），平衡之后如下图所示。

treemap-delete2

我们再删除7号元素，则从右子树中找到了最小元素8，8有子节点且为黑色，所以8的子节点9是替代节点，以9为当前节点进行再平衡。

我们发现9是红节点，则直接把它涂成黑色即满足了红黑树的特性，不需要再过多的平衡了。

treemap-delete3

这次我们来个狠的，把根节点删除，从右子树中找到了最小的元素5，5没有子节点，所以把5作为当前节点进行再平衡。

我们看到5是黑节点，且其兄弟为红色，符合情况1），平衡之后如下图所示，然后进入情况2）。

treemap-delete4

对情况2）进行再平衡后如下图所示。

treemap-delete5

然后进入下一次循环，发现不符合循环条件了，直接把x涂为黑色即可，退出这个方法之后会把旧x删除掉（见deleteEntry()方法），最后的结果就是下面这样。

treemap-delete6

未完待续，下一节我们一起探讨红黑树遍历元素的操作。

原文链接：https://www.cnblogs.com/tong-yuan/p/10657620.html

这篇关于深读源码-java集合之TreeMap源码分析（三）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/362742。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2