jdk源码分析红黑树——插入篇1.插入root2.父黑3.父红4.父红,叔红5.1父红,叔黑,外侧子孙5.2父红,叔黑,内侧子孙

红黑树是自平衡的排序树,自平衡的优点是减少遍历的节点,所以效率会高。如果是非平衡的二叉树,当顺序或逆序插入的时候,查找动作很可能会遍历n个节点

红黑树的规则很容易理解,但是维护这个规则难。

一、规则

1.每个节点要么是红色、要么是黑色

2.根节点一定是黑色

3.红色节点不可以连续出现(父节点、子节点不可同时为红)

4.从任意节点出发,到树底的所有路线,途径的黑节点数量必须相同

在修改红黑树的时候,切记要维护这个规则。一般默认插入红色节点(除非是root节点),插入后再进行旋转和颜色变换

二、旋转、变换技巧

关于旋转和颜色变换有几种情况:

1.插入root

不会违反规则

2.父黑

插入节点的父节点是黑色,不会违反规则

3.父红

插入节点的父节点是红色,一定违反规则(违反规则3)(因为默认插入红色节点),此时就需要修复红黑树了。这种情况下又细分为几种情况

4.父红,叔红

父节点和叔节点均为红色(违反规则3)

这种情况下就把父节点和叔节点都改成黑色,然后曾节点改为红色

可是此时,如果曾节点是根节点的话,那么必须将曾节点转为黑色。

所以一般在修补红黑树的方法的最后,会强制将根节点转为黑色

这种情况可能又会导致5.1的情况

5.1父红,叔黑,外侧子孙

父节点是红色,叔节点是黑色或者null,且新增节点是曾节点的外侧子孙(违反规则3)

外侧子孙:A点是B点的左-左-....-左或者右-右-..-右,那么A是B的外侧子孙,否则A是B的内侧子孙

符号解释:

N:新插入的节点,P:父节点,G:曾节点,U:叔节点

此时就需要将G点旋转,这里是右旋

不过此时颜色还有冲突,还要调整一下颜色

将P与G的颜色对调,既P变为黑色,G变为红色

总结一下,5.1的步骤:

step1:P->黑

step2:G->红

step3:将G旋转

5.1.1关于旋转的方向

旋转有左旋右旋,具体是看父节点是曾节点的左节点还是右节点

P是G的左节点,那么就将G右旋(因为要把P移动到G的位置)

P....G....右节点.....................G左旋

5.2父红,叔黑,内侧子孙

父节点是红色,叔节点是黑色或者null,且新增节点是曾节点的内侧子孙(违反规则3)

外侧子孙:A点是B点的左-左-....-左或者右-右-..-右,那么A是B的外侧子孙,否则A是B的内侧子孙

5.2跟5.1只有一个内侧外侧的区别。

内侧子孙比外侧要多做一次旋转。目的是把内侧子孙旋转成外侧子孙来做

这里的N就是G的内侧子孙,现在要把N变成G的外侧子孙。

将P旋转(这里是左旋),让N旋转到P的位置

之后的步骤就是和5.1处理外侧子孙的一样了。

5.2.1内侧转外侧的旋转方向

根据P点和N的相对位置,当N是P的右节点,则将P左旋,否则将P右旋

目的是让N旋转到P的位置

总结情况:

1.插入的是根节点,不违反规则

2.插入点的父节点是黑色,不违反规则

3.插入点的父、叔节点是红色,将父、叔转成黑色,然后将曾节点转成红色

4.插入点的父是红色、叔节点是黑色或者null,通过旋转和转变颜色,注意内侧外侧子孙!

三、分析TreeMap源码

jdk中的红黑树实现是TreeMap。

每次put之后,都会调用这个方法去维护红黑树的规则

    private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED;

        while (x != null && x != root && x.parent.color == RED) {//父节点是红色
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//父节点是曾节点的左节点
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {//父、叔节点都是红色,情况4
	                //将父节点和叔节点变为黑色,曾节点变为红色
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {//父节点是红色,叔节点是黑色或者null
                    if (x == rightOf(parentOf(x))) {//内侧子孙
                        x = parentOf(x);
                        rotateLeft(x);//旋转成外侧子孙
                    }
                    setColor(parentOf(x), BLACK);
                    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;//强制将根节点转成黑色
	}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 275. H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending orde...

2954
来自专栏xingoo, 一个梦想做发明家的程序员

在Java Web中使用Spark MLlib训练的模型

模型下载到本地,重新命名为xml。 可以看到默认四个特征分别叫做feild_0,field_1...目标为target

1832
来自专栏图形学与OpenGL

机械版CG 实验4 裁剪

了解二维图形裁剪的原理(点的裁剪、直线的裁剪、多边形的裁剪),利用VC+OpenGL实现直线的裁剪算法。

1841
来自专栏hanlp学习笔记

hanlp源码解析之中文分词算法

词图指的是句子中所有词可能构成的图。如果一个词A的下一个词可能是B的话,那么A和B之间具有一条路径E(A,B)。一个词可能有多个后续,同时也可能有多个前驱,它们...

1702
来自专栏数据结构与算法

BZOJ5249: [2018多省省队联测]IIIDX(线段树 贪心)

不难发现题目给出的是一个树,其中\(\frac{i}{K}\)是\(i\)的父亲节点

911
来自专栏章鱼的慢慢技术路

Direct3D 11 Tutorial 7:Texture Mapping and Constant Buffers_Direct3D 11 教程7:纹理映射和常量缓冲区

在上一个教程中,我们为项目引入了照明。 现在我们将通过向我们的立方体添加纹理来构建它。 此外,我们将介绍常量缓冲区的概念,并解释如何使用缓冲区通过最小化带宽使用...

1034
来自专栏计算机视觉与深度学习基础

Leetcode 130 Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions su...

2025
来自专栏Jack-Cui

Day4、Python

题目     一个数如果恰好等于它的因子之和,这个数就成为“完数”。例如6=1+2+3。编程找出1000以内的所有完数。 程序分析     完全数(...

2530
来自专栏数据结构与算法

Splay详解(三)

前言 上一节我们学习了splay所能解决的基本问题,这节我来讲一下splay怎么搞区间问题 实现 splay搞区间问题非常简单,比如我们要在区间l,r上搞事情,...

2957
来自专栏漫漫深度学习路

tensorflow自定义op:梯度

tensorflow自定义op,梯度 tensorflow 是 自动微分的,但是如果你不给它定义微分方程的话,它啥也干不了 在使用 tensorflow 的时...

7677

扫码关注云+社区

领取腾讯云代金券