研究jdk关于TreeMap 红黑树算法实现

时间:2022-03-10 21:34:45

因为TreeMap的实现方式是用红黑树这种数据结构进行存储的,所以呢我主要通过分析红黑树的实现在看待TreeMap,侧重点也在于如何实现红黑树,因为网上已经有非常都的关于红黑树的实现。我也看了些,但是有的说的不是很清楚,有的解释的也很清晰。这边主要是我的思路的总结。因为之前在研究HashMap和CurrentHashMap源码的时候有涉及到,文章是探索HashMap实现原理及其在jdk8数据结构的改进和另一篇探索jdk8之ConcurrentHashMap 的实现机制,但是关于插入和删除分析的还不是很仔细。所以有了这篇文章。

红黑色几点性质:

1、节点是红色或黑色。

2、根是黑色。

3、所有叶子都是黑色(叶子是NIL节点)。

4、每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

5、从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

预报知识:在讲解红黑树之前需要对数的数据结构有所了解,对二叉树结构以及实现由所了解,对二叉查找树ADT结构以及实现有所理解。如果对这些基础知识不是很清楚的话,一开始就看java的jdk关于红黑树的实现就会很吃力。如果对这些知识已经遗忘的话建议大学教材关于树的那张在看看。或者参看《数据结构与算法-java语言描述》这边是关于树和高级数据结构及实现这两章来理解。

本文只重点分析下插入和删除这两种比较复杂的情况。

关于插入

自定向上插入

插入分为几种情况:1、节点为黑色就直接插入;2、如果节点为红色那么插入红色就回违反性质4,如果插入黑色就回违反性质5。

那么如果是情况2要怎么处理呢?首先插入红色是肯定的,因为如果你插入黑色就会导致不平衡。那么插入红色后违反了性质4怎么办?就要旋转,如AVL树一样。

研究jdk关于TreeMap 红黑树算法实现

上图只是一般情况。如果X节点父类节点P的兄弟节点S是红色的,那么我们旋转后就回变成G-S是两个相连的红色节点,违反了性质4。那么怎么处理呢?那就涉及到自顶向下的红黑树。

上滤过程修复红黑树

修复红黑树,其实是一种上滤的过程,因为你插入的时候每次都循环修复这个过程,后面插入的就是一个向上的过程。接上面,如果出现了G-S红红的节点怎么处理?那么如果是这种情况的话我们是这样处理的,因为P的兄弟节点S也是红色的,我们会先执行一次颜色翻转。翻转后P和S就变成了黑色而G变成了红色,然后在旋转。

下面关于insert的操作,代码来着java的TreeMap,我觉得这个代码的实现方式是最简答明了的

public V put(K key, V value)
{
Entry<K,V> t = root;
// 一个空链表
if (t == null)
{
root = new Entry<K,V>(key, value, null);
size = 1;
// 记录修改次数为 1
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
// 采用定制排序
if (cpr != null)
{
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else
{
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 将新插入的节点作为 parent 节点的子节点
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 修复红黑树
fixAfterInsertion(e);
size++;
modCount++;
return null;
}

TreeMap 为插入节点后的修复操作由 fixAfterInsertion(Entry<K,V> x) 方法提供,该方法的源代码如下

private void fixAfterInsertion(Entry<K,V> x)
{
x.color = RED;
// 直到 x 节点的父节点不是根,且 x 的父节点不是红色
while (x != null && x != root
&& x.parent.color == RED)
{
// x 的父节点是其父节点的左子节点
if (parentOf(x) == leftOf(parentOf(parentOf(x))))
{
// 获取 x 的父节点的兄弟节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// 如果 x 的父节点的兄弟节点是红色(需要颜色翻转)
if (colorOf(y) == RED)
{
// 将 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 将 x 的父节点的兄弟节点设为黑色
setColor(y, BLACK);
// 将 x 的父节点的父节点设为红色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
// 如果 x 的父节点的兄弟节点是黑色(需要旋转)
else
{
// 如果 x 是其父节点的右子节点
if (x == rightOf(parentOf(x)))
{
// 将 x 的父节点设为 x
x = parentOf(x);
rotateLeft(x);
}
// 把 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 把 x 的父节点的父节点设为红色
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
}
// 以下的操作是上面操作的对称,就不做分析了
else
{
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED)
{
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
else
{
if (x == leftOf(parentOf(x)))
{
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
// 将根节点设为黑色
root.color = BLACK;
}

关于删除

如果理解了上面的插入操作的话,那么红黑树也已经理解了一半了,删除操作也是比较难的一部分。它难在哪里呢?因为我们是删除操作,但是我们又是绕到删除的操作。

删除的修复操作其实是一个不断的上滤过程。这上滤过程跟添加的修复操作是一个道理。删除操作表面上包含三种情况:

1、节点没有儿子的

2、节点有一个儿子的

3、节点有两个孩子的

我们队红黑树删除的操作,每一件事情都归咎于能够删除树叶。这是因为要删除带有两个孩子节点的可以用右子树的最小节点代替它。其他1和2情况直接删除就可以了。

下面用一张图片来说明,q(5)为要删除的节点,q有两个节点3和5,取最右节点的最左节点8和5的key和value交换,并把q指向节点8,那么现在的操作是不是变成删除节点8了。

因为8是最右子树的最左节点,所以它肯定没有左孩子。最多只有一个右孩子。那么删除的节点有两个儿子,那么问题可以被转化成删除另一个只有一个儿子的节点的问题

研究jdk关于TreeMap 红黑树算法实现

如下面代码的第9到12行,successor函数是找最右子树的最小节点。但是删除节点8肯定不会违反性质4(从每个叶子到根的所有路径上不能有两个连续的红色节点),但是如果8是黑色的,那么很肯能违反性质5,因为一条路径上少了一个黑色节点。那么久只能修复了。红黑树的修复是一个上滤的过程,就是一直修复直到根节点(root)或者直到被替换的节点为红色。下面的删除操作deleteEntry。关键部分在修复函数fixAfterDeletion

private void deleteEntry(Entry<K,V> p)
{
modCount++;
size--;
// 如果被删除节点的左子树、右子树都不为空
if (p.left != null && p.right != null)
{
// 用 p 节点的中序后继节点代替 p 节点
Entry<K,V> s = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}
// 如果 p 节点的左节点存在,replacement 代表左节点;否则代表右节点。
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null)
{
replacement.parent = p.parent;
// 如果 p 没有父节点,则 replacemment 变成父节点
if (p.parent == null)
root = replacement;
// 如果 p 节点是其父节点的左子节点
else if (p == p.parent.left)
p.parent.left = replacement;
// 如果 p 节点是其父节点的右子节点
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
// 修复红黑树
if (p.color == BLACK)
fixAfterDeletion(replacement); // ①
}
// 如果 p 节点没有父节点
else if (p.parent == null)
{
root = null;
}
else
{
if (p.color == BLACK)
// 修复红黑树
fixAfterDeletion(p); // ②
if (p.parent != null)
{
// 如果 p 是其父节点的左子节点
if (p == p.parent.left)
p.parent.left = null;
// 如果 p 是其父节点的右子节点
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}

下面是修复方法。上滤的过程中分为四种情况:

1、N的兄弟节点W为红色

2、N的兄弟w是黑色的,且w的俩个孩子都是黑色的。

3、N的兄弟w是黑色的,w的左孩子是红色,w的右孩子是黑色。

4、N的兄弟w是黑色的,且w的右孩子时红色的。

其中第一种情况可以转为2、3、4,其他三种也可以互相转换

// 删除节点后修复红黑树
private void fixAfterDeletion(Entry<K,V> x)
{
// 直到 x 不是根节点,且 x 的颜色是黑色
while (x != root && colorOf(x) == BLACK)
{
// 如果 x 是其父节点的左子节点
if (x == leftOf(parentOf(x)))
{
// 获取 x 节点的兄弟节点
Entry<K,V> sib = rightOf(parentOf(x));
// 如果 sib 节点是红色
if (colorOf(sib) == RED)
{
// 将 sib 节点设为黑色
setColor(sib, BLACK);
// 将 x 的父节点设为红色
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
// 再次将 sib 设为 x 的父节点的右子节点
sib = rightOf(parentOf(x));
}
// 如果 sib 的两个子节点都是黑色
if (colorOf(leftOf(sib)) == BLACK
&& colorOf(rightOf(sib)) == BLACK)
{
// 将 sib 设为红色
setColor(sib, RED);
// 让 x 等于 x 的父节点
x = parentOf(x);
}
else
{
// 如果 sib 的只有右子节点是黑色
if (colorOf(rightOf(sib)) == BLACK)
{
// 将 sib 的左子节点也设为黑色
setColor(leftOf(sib), BLACK);
// 将 sib 设为红色
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
// 设置 sib 的颜色与 x 的父节点的颜色相同
setColor(sib, colorOf(parentOf(x)));
// 将 x 的父节点设为黑色
setColor(parentOf(x), BLACK);
// 将 sib 的右子节点设为黑色
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
}
// 下面是上面的对称操作就不做具体分析了
else
{
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED)
{
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK
&& colorOf(leftOf(sib)) == BLACK)
{
setColor(sib, RED);
x = parentOf(x);
}
else
{
if (colorOf(leftOf(sib)) == BLACK)
{
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}

参考

《数据结构与算法-java语言描述》

https://zh.wikipedia.org/wiki/红黑树#C.2B.2B.E7.A4.BA.E4.BE.8B.E4.BB.A3.E7.A0.81

https://www.ibm.com/developerworks/cn/java/j-lo-tree/

http://cmsblogs.com/?p=1013

研究jdk关于TreeMap 红黑树算法实现的更多相关文章

  1. 通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

    本文转载自http://www.ibm.com/developerworks/cn/java/j-lo-tree/ 目录: TreeSet 和 TreeMap 的关系 TreeMap 的添加节点 Tr ...

  2. 通过分析 JDK 源代码研究 TreeMap 红黑树算法实现--转

    TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员,其中 TreeMap 是 Map 接口的常用实现类,而 TreeSet 是 Set 接口的常 ...

  3. 通过分析 JDK 源代码研究 TreeMap 红黑树算法实

    TreeMap和TreeSet是Java Collection Framework的两个重要成员,其中TreeMap是Map接口的常用实现类,而TreeSet是Set接口的常用实现类.虽然HashMa ...

  4. 红黑树&mdash&semi;&mdash&semi;算法导论&lpar;15&rpar;

    1. 什么是红黑树 (1) 简介     上一篇我们介绍了基本动态集合操作时间复杂度均为O(h)的二叉搜索树.但遗憾的是,只有当二叉搜索树高度较低时,这些集合操作才会较快:即当树的高度较高(甚至一种极 ...

  5. TreeMap红黑树

    Java TreeMap实现了SortedMap接口,也就是说会按照key的大小顺序对Map中的元素进行排序,key大小的评判可以通过其本身的自然顺序(natural ordering),也可以通过构 ...

  6. TreeMap 红黑树实现

    TreeMap 是一个有序的key-value集合,它是通过 红黑树 实现的. TreeMap 继承于AbstractMap,所以它是一个Map,即一个key-value集合. TreeMap 实现了 ...

  7. 【Java深入研究】10、红黑树

    一.红黑树介绍 红黑树是二叉查找树,红黑树的时间复杂度为: O(lgn) 红黑树的特性:(1)每个节点或者是黑色,或者是红色.(2)根节点是黑色.(3)每个叶子节点(NIL)是黑色. [注意:这里叶子 ...

  8. 53 容器(八)——TreeMap 红黑树

    红黑树是比较难以理解的一种数据结构.它能从10亿数据中进行10几次比较就能查找到需要的数据.效率非常高. 理解起内部结构也难. 现阶段我们知道有这种东西就行了. 参考文章: https://www.j ...

  9. 红黑树-算法大神的博客-以及java多线程酷炫的知识

    http://www.cnblogs.com/skywang12345/p/3245399.html 解释第5条:从 ->根节点(或者任意个结点)到->所有的末端节点的路径中 ->黑 ...

随机推荐

  1. python笔记1:python函数的使用

    一.函数:len() 1:作用:返回字符串.列表.字典.元组等长度 2:语法:len(str) 3:参数: str:要计算的字符串.列表.字典.元组等 4:返回值:字符串.列表.字典.元组等元素的长度 ...

  2. eclipse智能提示

    原文地址:http://www.cnblogs.com/myitm/archive/2010/12/17/1909194.html Windows→Preferences→Java→Editor→Co ...

  3. C&num; 字符串详细使用

    转自 http://www.cnblogs.com/candywyq/archive/2007/07/24/830021.html 1.Convert.ToInt32与Int32.Parse的恩恩怨怨 ...

  4. Java实现RC4加解密

    package com.vrv.paw.utils; public class RC4Util { public static String decry_RC4(byte[] data, String ...

  5. &lbrack;SVN&rsqb; 分支同步、合入主干操作分享

    冲突的解决原则 不是自己修改的地方就使用主干的. 需要特别注意的是: 分支同步主干时,远端(theirs)是主干,本地(mine/working)的是分支: 分支合入主干时,本地(mine/worki ...

  6. hdu 4932 Miaomiao&amp&semi;&num;39&semi;s Geometry&lpar;暴力&rpar;

    题目链接:hdu 4932 Miaomiao's Geometry 题目大意:在x坐标上又若干个点,如今要用若干条相等长度的线段覆盖这些点,若一个点被一条线段覆盖,则必须在这条线的左端点或者是右端点, ...

  7. go&period;js remove 特定part

    我想删除一个实际上是背景的部分. 假设这是我添加part的方式 myDiagram.add( scope.gj(go.Part,//此Part未绑定到任何模型数据 { layerName:“Backg ...

  8. python爬虫学习笔记(一)——环境配置(windows系统)

    在进行python爬虫学习前,需要进行如下准备工作: python3+pip官方配置 1.Anaconda(推荐,包括python和相关库)   [推荐地址:清华镜像] https://mirrors ...

  9. comparable和comparator

    Comparable Comparable可以认为是一个内部比较器,实现了Comparable接口的类有一个特点,就是这些类是可以和自己比较的,在compareTo方法中指定具体的比较方法. comp ...

  10. Wildcard Matching leetcode java

    题目: Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single charact ...