红黑树的插入及旋转操作详细解读,教你透彻了

时间:2019-05-12 11:42来源:亚洲城ca88唯一官方网站
透过上篇小说,大家早就能够见情红黑树的基本功数据结构,那么那篇文章就来剖析下,在红黑树中插入贰个结点后,内部数据结构爆发了怎么样变化。 图解集结七:红黑树概念、红黑

透过上篇小说,大家早就能够见情红黑树的基本功数据结构,那么那篇文章就来剖析下,在红黑树中插入贰个结点后,内部数据结构爆发了怎么样变化。

图解集结七:红黑树概念、红黑树的插入及旋转操作详细解读,红黑解读

原稿地址

 

初识TreeMap

事先的小说讲明了二种Map,分别是HashMap与LinkedHashMap,它们保险了以O(一)的日子复杂度举行增、删、改、查,从存款和储蓄角度思索,这二种数据结构是非凡精美的。其它,LinkedHashMap还额内地有限支撑了Map的遍历顺序能够与put顺序一致,消除了HashMap自己冬季的主题材料。

虽说,HashMap与LinkedHashMap依然有和睦的局限性----它们不享有总计性质,也许说它们的计算性质时间复杂度并不是很好才越来越纯粹,全部的计算必须遍历全数Entry,因而时间复杂度为O(N)。比方Map的Key有一、2、三、四、伍、陆、七,笔者以往要总结:

就临近这一个操作,HashMap和LinkedHashMap做得比较差,此时大家能够动用TreeMap。TreeMap的Key根据自然顺序进行排序大概依靠成立映射时提供的Comparator接口实行排序。TreeMap为增、删、改、查那个操作提供了log(N)的时间支付,从存款和储蓄角度来讲,那比HashMap与LinkedHashMap的O(一)时间复杂度要差些;然则在总计性质上,TreeMap一样能够保险log(N)的年华支付,那又比HashMap与LinkedHashMap的O(N)时间复杂度好不少。

因此计算来说:借使只须要仓库储存功用,使用HashMap与LinkedHashMap是壹种更加好的选择;假使还亟需确定保障总括性质照旧需求对Key遵照一定规则实行排序,那么使用TreeMap是1种越来越好的选项。

 

红黑树的部分基本概念

在讲TreeMap前依旧先说一下红黑树的局地基本概念,那样能够越来越好地领略之后TreeMap的源代码。

二叉查找树是在风云变幻的时候是特别轻便失衡的,产生的最坏意况就是1边倒(即唯有左子树/右子树),那样会导致树检索的频率大大下跌。(关于树和二叉查找树能够看作者事先写的1篇作品树型结构)

红黑树是为了维护2叉查找树的平衡而发出的1种树,根据维基百科的定义,红黑树有三个特点,但本身感觉讲得不太易懂,笔者要好计算一下,红黑树的特点大约有多个(换句话说,安排、删除节点后整个红黑树也非得知足上边的两日本性,假诺不满意则必须开展旋转):

上述的习性约束了红黑树的关键:从根到叶子的最长只怕路线不多于最短恐怕路线的两倍长。获得那一个结论的理由是:

那会儿(二)正好是(壹)的两倍长。结果就是这些树差不多上是平衡的,因为比方插入、删除和探求某些值这么的操作最坏意况都需求与树的惊人成比例,这一个惊人的反驳上限允许红黑树在最坏景况下都是高效的,而差别于普通的二叉查找树,最后确认保障了红黑树能够以O(log2 n) 的年月复杂度实行检索、插入、删除

上面体现一张红黑树的实例图:

图片 1

能够看来根节点到持有NULL LEAF节点(即叶子节点)所经过的天青节点都以二个。

除此以外从这张图上大家还能够拿到叁个定论:红黑树并不是可观的平衡树。所谓平衡树指的是壹棵空树或它的左右八个子树的可观差的相对值不抢先壹,但是大家看:

  • 最左边的路线00二陆-->0017-->0012-->0010-->000三-->NULL LEAF,它的可观为五
  • 最终边的路线00二六-->00四一-->0047-->NULL LEAF,它的莫斯中国科学技术大学学为三

左右子树的莫斯中国科学技术大学学差值为二,由此红黑树并不是中度平衡的,它放任了冲天平衡的表征而只追求局地抵消,这种特点下落了插入、删除时对树旋转的渴求,从而进级了树的完整品质。而别的平衡树比如AVL树即使寻找质量为质量是O(logn),然则为了掩护其平衡天性,恐怕要在插入、删除操作时张开数十次的旋转,产生异常的大的开支。

 

八个关怀点在LinkedHashMap上的答案

关 注 点 结  论
TreeMap是否允许键值对为空 Key不允许为空,Value允许为空 
TreeMap是否允许重复数据 Key重复会覆盖,Value允许重复 
TreeMap是否有序 按照Key的自然顺序排序或者Comparator接口指定的排序算法进行排序 
TreeMap是否线程安全  非线程安全

 

TreeMap基本数据结构

TreeMap基于红黑树福如东海,既然是红黑树,那么种种节点中除去Key-->Value映射之外,必然存款和储蓄了红黑树节点特有的有的内容,它们是:

TreeMap的节点Java代码定义为:

1 static final class Entry<K,V> implements Map.Entry<K,V> {
2         K key;
3         V value;
4         Entry<K,V> left = null;
5         Entry<K,V> right = null;
6         Entry<K,V> parent;
7         boolean color = BLACK;
8         ...
9 }

由于颜色唯有革命和葡萄紫二种,因而颜色可以应用布尔类型(boolean)来表示,赫色代表为true,深橙为false。

 

TreeMap增加数据流程总括

先是看一下TreeMap怎么着增添数据,测试代码为:

 1 public class MapTest {
 2 
 3     @Test
 4     public void testTreeMap() {
 5         TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();
 6         treeMap.put(10, "10");
 7         treeMap.put(85, "85");
 8         treeMap.put(15, "15");
 9         treeMap.put(70, "70");
10         treeMap.put(20, "20");
11         treeMap.put(60, "60");
12         treeMap.put(30, "30");
13         treeMap.put(50, "50");
14 
15         for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
16             System.out.println(entry.getKey()   ":"   entry.getValue());
17         }
18     }
19     
20 }

正文接下去的剧情会付给插入每条数据现在红黑树的数据结构是什么样样子的。首先看一下treeMap的put方法的代码达成:

 1 public V put(K key, V value) {
 2     Entry<K,V> t = root;
 3     if (t == null) {
 4         compare(key, key); // type (and possibly null) check
 5 
 6         root = new Entry<>(key, value, null);
 7         size = 1;
 8         modCount  ;
 9         return null;
10     }
11     int cmp;
12     Entry<K,V> parent;
13     // split comparator and comparable paths
14     Comparator<? super K> cpr = comparator;
15     if (cpr != null) {
16         do {
17             parent = t;
18             cmp = cpr.compare(key, t.key);
19             if (cmp < 0)
20                 t = t.left;
21             else if (cmp > 0)
22                 t = t.right;
23             else
24                 return t.setValue(value);
25         } while (t != null);
26     }
27     else {
28         if (key == null)
29             throw new NullPointerException();
30         Comparable<? super K> k = (Comparable<? super K>) key;
31         do {
32             parent = t;
33             cmp = k.compareTo(t.key);
34             if (cmp < 0)
35                 t = t.left;
36             else if (cmp > 0)
37                 t = t.right;
38             else
39                 return t.setValue(value);
40         } while (t != null);
41     }
42     Entry<K,V> e = new Entry<>(key, value, parent);
43     if (cmp < 0)
44         parent.left = e;
45     else
46         parent.right = e;
47     fixAfterInsertion(e);
48     size  ;
49     modCount  ;
50     return null;
51 }

从这段代码,先计算一下TreeMap增多数据的几个步骤:

第1~第五步都尚未什么样难题,红黑树最宗旨的相应是第5步插入数据之后进展的修复职业,对应的Java代码是TreeMap中的fixAfterInsertion方法,下边看一下put种种数据之后TreeMap都做了怎么样操作,借此来理清TreeMap的贯彻原理。

 

put(10, "10")

先是是put(拾, "10"),由于此时TreeMap中未有任何节点,因而拾为根且根节点为深湖蓝节点,put(10, "10")之后的数据结构为:

图片 2

 

put(85, "85")

随正是put(八五, "八伍"),这一步也简单,8伍比拾大,由此在10的右节点上,然则由于八伍不是根节点,因而会执行fixAfterInsertion方法实行数据立异,看一下fixAfterInsertion方法代码完毕:

 1 private void fixAfterInsertion(Entry<K,V> x) {
 2     x.color = RED;
 3 
 4     while (x != null && x != root && x.parent.color == RED) {
 5         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
 6             Entry<K,V> y = rightOf(parentOf(parentOf(x)));
 7             if (colorOf(y) == RED) {
 8                 setColor(parentOf(x), BLACK);
 9                 setColor(y, BLACK);
10                 setColor(parentOf(parentOf(x)), RED);
11                 x = parentOf(parentOf(x));
12             } else {
13                 if (x == rightOf(parentOf(x))) {
14                     x = parentOf(x);
15                     rotateLeft(x);
16                 }
17                 setColor(parentOf(x), BLACK);
18                 setColor(parentOf(parentOf(x)), RED);
19                 rotateRight(parentOf(parentOf(x)));
20             }
21         } else {
22             Entry<K,V> y = leftOf(parentOf(parentOf(x)));
23             if (colorOf(y) == RED) {
24                 setColor(parentOf(x), BLACK);
25                 setColor(y, BLACK);
26                 setColor(parentOf(parentOf(x)), RED);
27                 x = parentOf(parentOf(x));
28             } else {
29                 if (x == leftOf(parentOf(x))) {
30                     x = parentOf(x);
31                     rotateRight(x);
32                 }
33                 setColor(parentOf(x), BLACK);
34                 setColor(parentOf(parentOf(x)), RED);
35                 rotateLeft(parentOf(parentOf(x)));
36             }
37         }
38     }
39     root.color = BLACK;
40 }

小编们看第二行的代码,它将默许的插入的百般节点着色成为墨绛红,这很好了然:

根据红黑树的性质(3),红黑树要求从根节点到叶子所有叶子节点上经过的黑色节点个数是相同的,因此如果插入的节点着色为黑色,那必然有可能导致某条路径上的黑色节点数量大于其他路径上的黑色节点数量,因此默认插入的节点必须是红色的,以此来维持红黑树的性质(3)

本来插入节点着色为革命节点后,有非常的大或然导致的主题素材是违背性质(二),即出现接二连三三个革命节点,那就须求经过旋转操作去改动树的社团,化解那一个主题素材。

紧接着看第五行的判断,前多少个条件都知足,可是因为八伍这么些节点的父节点是根节点的,根节点是紫色节点,由此那么些规范不满意,while循环不进来,直接实施二遍30行的代码给根节点着色为木色(因为在转动进度中有希望导致根节点为赤褐,而红黑树的根节点必须是墨蓝,由此最后不管根节点是还是不是米黄,都要重新上色确定保障根节点是湖蓝的)。

那么put(八伍, "捌五")之后,整个树的布局变为:

图片 3

 

fixAfterInsertion方法流程

在看put(一5, "1五")以前,须要求先过一下fixAfterInsertion方法。第4行~第1一行的代码和第3壹行~第二8行的代码是同样的,无非3个是操作左子树另一个是操作右子树而已,由此就看前十分之五:

 1 while (x != null && x != root && x.parent.color == RED) {
 2     if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
 3         Entry<K,V> y = rightOf(parentOf(parentOf(x)));
 4         if (colorOf(y) == RED) {
 5             setColor(parentOf(x), BLACK);
 6             setColor(y, BLACK);
 7             setColor(parentOf(parentOf(x)), RED);
 8             x = parentOf(parentOf(x));
 9         } else {
10             if (x == rightOf(parentOf(x))) {
11                 x = parentOf(x);
12                 rotateLeft(x);
13             }
14             setColor(parentOf(x), BLACK);
15             setColor(parentOf(parentOf(x)), RED);
16             rotateRight(parentOf(parentOf(x)));
17         }
18     }
19     ....
20 }

第1行的论断注意一下,用言语叙述出来正是:剖断当前节点的父节点与眼下节点的父节点的父节点的左子节点是不是同1个节点。翻译一下正是:此时此刻节点是不是左子节点插入,关于这些不知情的本人就不表明了,能够团结多思量一下。对那整段代码作者用流程图描述一下:

图片 4

此地有3个左子树内侧插入与左子树点外侧插入的概念,小编用图表示一下:

图片 5

里头左边的是左子树外侧插入,右侧的是左子树内侧插入,能够从地点的流程图上看出,对于那三种插入情势的拍卖是不一致的,分化是后者也便是左子树内侧插入多一步左旋操作

能看出,红黑树的插入最多只须求进行三回旋转,至于红黑树的旋转,前面结合代码举办教学。

 

put(15, "15")

看完fixAfterInsertion方法流程之后,继续累加数据,此次增多的是put(1五, "壹5"),一伍比10大且比捌5小,由此15聊起底应该是8伍的左子节点,暗许插入的是新民主主义革命节点,因而首先将15当做革命节点插入八伍的左子节点后的构造应当是:

图片 6

可是显著这里违反了红黑树的性质(二),即接二连三出现了五个革命节点,因而此时必须开始展览旋转。回放后边fixAfterInsertion的流程,上边演示的是左子树插入流程,右子树同样,能够观望那是右子树内侧插入,供给进行两回旋转操作:

旋转是红黑树中最难驾驭也是最基本的操作,右旋和左旋是对称的操作,小编个人的明亮,以右旋为例,对有些节点x举办右旋,其实质是:

  • 下落左子树的冲天,增添右子树的万丈
  • 将x变为当前岗位的右子节点

左旋是一律的道理,在打转的时候势须求牢记那两句话,那将会支持我们精晓地明白在不一致的现象下旋转如何进展。

先看一下(一)也便是"对新插入节点的父节点进行一遍右旋操作",源代码为rotateRight方法:

 1 private void rotateRight(Entry<K,V> p) {
 2     if (p != null) {
 3         Entry<K,V> l = p.left;
 4         p.left = l.right;
 5         if (l.right != null) l.right.parent = p;
 6         l.parent = p.parent;
 7         if (p.parent == null)
 8            root = l;
 9         else if (p.parent.right == p)
10             p.parent.right = l;
11         else p.parent.left = l;
12         l.right = p;
13         p.parent = l;
14     }
15 }

右旋流程用流程图画一下其流程:

图片 7

再用一张示例图表示一下右旋各节点的改换,旋转不会转移节点颜色,这里就不区分海蓝节点和黄铜色节点了,a是索要举行右旋的节点:

图片 8

左旋与右旋是二个对称的操作,我们能够实施看把右图的b节点实行左旋,就形成了左图了。这里多说一句,旋转一定要注脚是对哪些节点开始展览旋转,网络看多数小说讲左旋、右旋都以一向说旋转之后如何怎样,小编认为脱离实际的节点讲旋转是平素不其余意义的。

此处也许会有的三个标题是:b有左右多个子节点分别为d和e,为什么右旋的时候要将右子节点e获得a的左子节点而不是b的左子节点d?

二个异常的粗略的解释是:一旦将b的左子节点d得到a的左子节点,那么b右旋后右子节点指向a,b原来的右子节点e就形成了3个游离的节点,游离于整个数据结构之外

回到实际的例子,对捌5那一个节点举行右旋之后还有三次着色操作(2),分别是将x的父节点着色为铁黑,将x的祖父节点着色为草绿,那么此时的树形结构应当为:

图片 9

接下来对节点十开始展览三回左旋操作(三),左旋之后的组织为:

图片 10

说起底不管根节点是否红色,都将根节点着色为紫酱色,那么插入一伍从此的数据结构就改为了上海体育地方,知足红黑树的叁条特色。

 

put(70, "70")

put(70, "70")就很轻松了,70是八5的左子节点,由于70的父节点以及叔父节点都以新民主主义革命节点,因而一向将70的父节点85、将70的叔父节点十着色为油红就能够,70以此节点着色为金棕,即知足红黑树的风味,插入70随后的协会图为:

图片 11

 

put(20, "20")

put(20, "20"),插入的职责应该是70的左子节点,私下认可插入桃红,插入之后的结构图为:

图片 12

题材很明显,出现了连接三个大青节点,20的插入地点是1种左子树外侧插入的场景,因而只供给张开着色 对节点85张开3次右旋就能够,着色 右旋之后数据结构变为:

图片 13

 

put(60, "60")

上面实行put(60, "60")操作,节点60安排的职分是节点20的右子节点,由于节点60的父节点与叔父节点都是革命节点,因而只需求将节点60的父节点与叔父节点着色为黑灰,将节点60的组父节点着色为革命就可以。

那就是说put(60, "60")之后的组织为:

图片 14

 

put(30, "30")

put(30, "30"),节点30相应为节点60的左子节点,由此插入节点30过后应该是那般的:

图片 15

旗帜明显这里违反了红黑树性质(二)即再三再四出现了四个青黄节点,因而这里要举行旋转。

put(30, "30")的操作和put(一伍, "15")的操作看似,同样是右子树内侧插入的意况,那么须求举办三遍旋转:

右旋 着色 左旋之后,put(30, "30")的结果应当为:

图片 16

 

put(50, "50")

下3个操作是put(50, "50"),节点50是节点60的左子节点,由于节点50的生父节点与叔父节点都是蛋青节点,因而只须求将节点50的老爸节点与叔父节点着色为深草绿,将节点50的公公节点着色为革命就能够:

图片 17

节点50的父节点与叔父节点都以新民主主义革命节点(注意不要被上海体育场合迷糊了!上航海用体育场合是双重上色之后的布局而不是双重上色在此以前的结构,重新上色在此之前的构造为上上海体育场面),因而插入节点4十三头须要开始展览着色,本人那样的操作是从未其他难点的,但难点的关键在于,着色之后现身了连接的革命节点,即节点30与节点70。那正是怎么fixAfterInsertion方法的方法体是while循环的案由:

1 private void fixAfterInsertion(Entry<K,V> x) {
2     x.color = RED;
3 
4     while (x != null && x != root && x.parent.color == RED) {
5     ...
6     }
7 }

因为这种着色格局是将插入节点的四伯节点着色为革命,因而着色之后必须将方今节点指向插入节点的太爷节点,剖断祖父节点与父节点是还是不是一而再海军蓝的节点,是就开始展览旋转,重新让红黑树平衡。

接下去的标题正是怎么旋转了。大家得以把节点15-->节点70-->节点30连起来看,是否很熟识?那就是地方重复了一次的右子树内侧插入的场景,那么首先对节点70拓展右旋,右旋后的结果为:

图片 18

下一步,节点70的父节点着色为普鲁士蓝,节点70的三伯节点着色为卡其色(这一步不精通依然忘了为何的,能够去看一下事先对于fixAfterInsertion方法的解读),重新上色后的组织为:

图片 19

末段一步,对节点70的父节点节点一五开始展览2回左旋,左旋之后的布局为:

图片 20

再度上升红黑树的习性:

 

后记

正文通过持续向红黑树的右子树插入数据,演示了红黑树左侧插入时恐怕出现的各类意况且相应怎样管理那些情状,左边插入同理。

红黑树还是有一些难,因而笔者个人建议在读书红黑树的时候鲜明要多画(像本身个人就画了3张MA汉兰达CH纸) 多想,那样本事越来越好地领略红黑树的法则,极度是旋转的原理。

TreeMap的插入操作和旋转操作已经讲完,后文种着重于TreeMap的去除操作以及部分总括操作(比如找到节点比50大的兼具节点)是何等落到实处的。

原来的书文地址...

原稿链接

 

2叉查找树

由于红黑树本质上正是一棵2叉查找树,所以在询问红黑树在此以前,我们先来看下2叉查找树。

2叉查找树(Binary Search Tree),也称有序2叉树(ordered binary tree),排序二叉树(sorted binary tree),是指壹棵空树只怕具有下列性质的二叉树:

  • 若任性结点的左子树不空,则左子树上全数结点的值均小于它的根结点的值;
  • 若任性结点的右子树不空,则右子树上全数结点的值均高于它的根结点的值;
  • 随意结点的左、右子树也各自为二叉查找树。
  • 尚无键值相等的结点(no duplicate nodes)。

因为,一棵由n个结点,随机构造的2叉查找树的冲天为lgn,所以顺理成章,一般操作的试行时间为O(lgn).(至于n个结点的二叉树中度为lgn的表明,可参看算法导论 第一贰章 贰叉查找树 第叁2.4节)。

但贰叉树若退化成了一棵具备n个结点的线性链后,则此些操作最坏情形运营时刻为O(n)。后边我们会合到1种基于贰叉查找树-红黑树,它通过有个别属性使得树相对平衡,使得最终查找、插入、删除的年华复杂度最坏情况下照旧为O(lgn)。

TreeMap插入有个别结点的源码解析

红黑树

后面大家已经说过,红黑树,本质上来说正是一棵贰叉查找树,但它在贰叉查找树的基础上加码了着色和连锁的性情使得红黑树相对平衡,从而确定保障了红黑树的找出、插入、删除的大运复杂度最坏为O(log n)。

但它是什么确认保障1棵n个结点的红黑树的万丈始终维持在h = logn的吧?那就引出了红黑树的五条性质:

1)每个结点要么是红的,要么是黑的。  
2)根结点是黑的。  
3)每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。  
4)如果一个结点是红的,那么它的俩个儿子都是黑的。  
5)对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。  

便是红黑树的那伍条性质,使得1棵n个结点是红黑树始终维持了logn的中度,从而也就分解了地点大家所说的“红黑树的追寻、插入、删除的小时复杂度最坏为O(log n)”这一定论的原因。

如下图所示,就是1颗红黑树(下图引自wikipedia:http://t.cn/hgvH1l):

image.png

上文中大家所说的 "叶结点" 或"NULL结点",它不分包数据而只负责树在此结束的指令,那么些结点以及它们的父结点,在绘图中都会时常被总结。

图片 21图片 22

树的转动知识

当大家在对红黑树举行插队和删除等操作时,对树做了修改,那么或者会违反红黑树的习性。

为了承袭维持红黑树的习性,大家能够透过对结点举办重复上色,以及对树举行相关的旋转操作,即修改树中或多或少结点的颜色及指针结构,来完结对红黑树进行插队或删除结点等操作后,继续保持它的性质或平衡。

树的转动,分为左旋和右旋,以下借助图来做形象的解释和介绍:

1.左旋

image.png

如上图所示:

当在有些结点pivot上,做左旋操作时,我们假若它的右孩子y不是NIL[T],pivot可感觉任何不是NIL[T]的左孩子结点。

左旋以pivot到y之间的链为“支轴”进行,它使y成为该孩子树新的根,而y的左孩子b则变为pivot的右孩子。

左旋操作的参照代码如下所示(以x替代上述的pivot):

 LEFT-ROTATE(T, x)  
1  y ← right[x] ▹ Set y.  
2  right[x] ← left[y]      ▹ Turn y's left subtree into x's right subtree.  
3  p[left[y]] ← x  
4  p[y] ← p[x]             ▹ Link x's parent to y.  
5  if p[x] = nil[T]  
6     then root[T] ← y  
7     else if x = left[p[x]]  
8             then left[p[x]] ← y  
9             else right[p[x]] ← y  
10  left[y] ← x             ▹ Put x on y's left.  
11  p[x] ← y  

2.右旋

右旋与左旋差不离,再此不做详细介绍。

image.png

对于树的旋转,能保持不改变的唯有原树的探寻性质,而原树的红黑性质则无法维系,在红黑树的数据插入和删除后可采取旋转和颜色重涂来平复树的红黑性质。

 1     /**
 2      * 插入节点,并平衡红黑树的操作
 3      * 如果原先map中已经有该key对应的键值对,则替换原先该key对应的value为新的value
 4      * 如果原先map中没有该key对应的键值对,则在map中新插入一个该key和value对应的键值对
 5      *
 6      * @param key 键
 7      * @param value 新值
 8      *
 9      * @return 返回原先的值 或者 null
10      * 
11      * @throws ClassCastException 如果用户传入了一个不可和其他key比较的key(违反泛型约定),则抛出该异常
12      * @throws NullPointerException key传入了null,则报此异常
13      */
14     public V put(K key, V value) {
15         Entry<K,V> t = root;   //获取根节点
16         if (t == null) {  //如果根节点为空,则当前的树还没有初始化
17             compare(key, key); // 检查key的类型以及是否为null
18 
19             root = new Entry<>(key, value, null); //根据key和value创建一个黑色新节点作为树的根节点
20             size = 1;  //结点总数 1
21             modCount  ;
22             return null;  //直接返回
23         }
24         //根节点不为空
25         int cmp;  //结点的比较结果  >0 OR <0 OR =0
26         Entry<K,V> parent;
27         // 区分是使用key的自然排序进行结点比较 还是 使用用户传入的比较器进行结点的比较
28         Comparator<? super K> cpr = comparator;
29         if (cpr != null) {  //如果用户传入了自定义比较器
30             do {
31                 parent = t;  //每次进行比较的节点,一开始t变量保存的是树的根节点
32                 cmp = cpr.compare(key, t.key); //使用自定义比较器的compare方法,对传入的结点和当前遍历到结点的key进行比较
33                 if (cmp < 0)  //如果传入节点的key比当前遍历到节点的key小
34                     t = t.left;  //把下次进行比较的节点设置为当前遍历到的节点的左子节点
35                 else if (cmp > 0)  //如果传入节点的key比当前遍历到节点的key大
36                     t = t.right; //把下次进行比较的节点设置为当前遍历到的节点的右子节点
37                 else  //如果传入节点的key和当前遍历到节点的key一样大
38                     return t.setValue(value);  //说明这是一个替换原有key对应的value的操作,替换完成后直接返回(不需要再进行下面的插入操作)
39             } while (t != null);  //直到遍历到某一个叶子结点才结束,最终t变量保存的是当前遍历到的叶子节点
40         }
41         else {  //没有自定义比较器,使用key的自然排序进行比较
42             if (key == null)
43                 throw new NullPointerException();  //如果传入key为null,则报异常
44                 Comparable<? super K> k = (Comparable<? super K>) key;
45             do {
46                 parent = t;  //每次进行比较的节点,一开始t变量保存的是树的根节点
47                 cmp = k.compareTo(t.key); //使用Comparable接口的compareTo方法,对传入的结点和当前遍历到结点的key进行比较
48                 if (cmp < 0)  //以下步骤和上面if的步骤完全相同,不再赘述
49                     t = t.left;
50                 else if (cmp > 0)
51                     t = t.right;
52                 else
53                     return t.setValue(value);
54             } while (t != null);
55         }
56         //执行到这里说明遍历了整个树后没有发现存在与传入key相同的键值对,则需要将传入的键值对插入到树中
57         Entry<K,V> e = new Entry<>(key, value, parent);  //根据当前传入的key和value新建一个黑色节点
58         if (cmp < 0)  //如果之前最后一次比较的结果是传入的key比当时叶子结点的key小
59             parent.left = e;  //那么就将当时叶子结点的左子结点设置为当前传入的结点,当前传入的结点变为新的叶子节点
60         else  //如果之前最后一次比较的结果是传入的key比当时叶子结点的key大
61             parent.right = e;  //那么就将当时叶子结点的右子结点设置为当前传入的结点,当前传入的结点变为新的叶子节点
62         
63         fixAfterInsertion(e);  //红黑树的核心方法:在插入后通过左旋、右旋、变色将当前树变成符合红黑树规定的树
64         
65         size  ;  //节点总数 1
66         modCount  ;
67         return null;  //返回null
68     }

红黑树的插入

要确实精晓红黑树的插入和删除,还得先清楚二叉查找树的插入和删除。磨刀不误砍柴工,大家再来分别精晓下2叉查找树的插入和删除。

View Code

贰叉查找树的插入

假诺要在贰叉查找树中插入二个结点,首先要查找到结点插入的岗位,然后进行插队,如果插入的结点为z的话,插入的伪代码如下:

TREE-INSERT(T, z)
 1  y ← NIL
 2  x ← root[T]
 3  while x ≠ NIL
 4      do y ←  x
 5         if key[z] < key[x]
 6            then x ← left[x]
 7            else x ← right[x]
 8  p[z] ← y
 9  if y = NIL
10     then root[T] ← z              ⊹ Tree T was empty
11     else if key[z] < key[y]
12             then left[y] ← z
13             else right[y] ← z

能够见到,上述第壹-7行代码就是在二叉查找树中追寻z待插入的任务,若是插入结点z小于当前遍历到的结点,则到最近结点的左子树中继续搜寻,借使z大于当前结点,则到近日结点的右子树中继续寻找,第柒-1三行代码找到待插入的岗位,倘诺z依然比此刻遍历到的新的日前结点小,则z作为当前结点的左孩子,不然作为当下结点的右孩子。

逻辑依然比较轻巧的,只要区分两点就能够:

红黑树的插入和插入修复

现行反革命咱们明白了贰叉查找树的插入,接下去,大家便来具体领会红黑树的插入操作。红黑树的插入也等于在2叉查找树插入的根基上,为了重新回涨平衡,继续做了插入修复操作。

设若插入的结点为z,红黑树的插入伪代码具体如下所示:

RB-INSERT(T, z)  
 1  y ← nil[T]  
 2  x ← root[T]  
 3  while x ≠ nil[T]  
 4      do y ← x  
 5         if key[z] < key[x]  
 6            then x ← left[x]  
 7            else x ← right[x]  
 8  p[z] ← y  
 9  if y = nil[T]  
10     then root[T] ← z  
11     else if key[z] < key[y]  
12             then left[y] ← z  
13             else right[y] ← z  
14  left[z] ← nil[T]  
15  right[z] ← nil[T]  
16  color[z] ← RED  
17  RB-INSERT-FIXUP(T, z)  

大家把地点这段红黑树的插入代码,跟我们事先看到的二叉查找树的插入代码,能够观察,RB-INSERT(T, z)前边的第三-壹3行代码基本便是2叉查找树的插入代码,然后第壹肆-16行代码把z的左孩子、右孩子都赋为叶结点nil,再把z结点着为革命,最终为确认保障红黑性质在插入操作后依然维持,调用贰个帮扶程序RB-INSERT-FIXUP来对结点进行再度上色,并旋转。

换言之

  • 假若插入的是根结点,因为原树是空树,此景况只会违反性质二,所以直接把此结点涂为金黄。
  • 假如插入的结点的父结点是水草地绿,由于此不会背离性质二和性质4,红黑树未有被毁坏,所以那时候也是何许也不做。

但当境遇下述三种情景时:

  • 插入修复情状一:假如当前结点的父结点是新民主主义革命且祖父结点的另三个子结点(岳丈结点)是革命
  • 插入修复情状二:当前结点的父结点是新民主主义革命,三叔结点是浅豆绿,当前结点是其父结点的右子
  • 布署修复景况三:当前结点的父结点是革命,四叔结点是铁青,当前结点是其父结点的左子

又该怎么调治呢?答案正是依照红黑树插入代码RB-INSERT(T, z)最后一行调用的RB-INSERT-FIXUP(T,z)所示操作进行,具体如下所示:

RB-INSERT-FIXUP(T,z)
 1 while color[p[z]] = RED  
 2     do if p[z] = left[p[p[z]]]  
 3           then y ← right[p[p[z]]]  
 4                if color[y] = RED  
 5                   then color[p[z]] ← BLACK                    ▹ Case 1  
 6                        color[y] ← BLACK                       ▹ Case 1  
 7                        color[p[p[z]]] ← RED                   ▹ Case 1  
 8                        z ← p[p[z]]                            ▹ Case 1  
 9                   else if z = right[p[z]]  
10                           then z ← p[z]                       ▹ Case 2  
11                                LEFT-ROTATE(T, z)              ▹ Case 2  
12                           color[p[z]] ← BLACK                 ▹ Case 3  
13                           color[p[p[z]]] ← RED                ▹ Case 3  
14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3  
15           else (same as then clause  
                         with "right" and "left" exchanged)  
16 color[root[T]] ← BLACK  

上面,大家来分别管理上述3种插入修复景况。

布置修复景况1:当前结点的父结点是辛酉革命且祖父结点的另3个子结点(公公结点)是新民主主义革命。

即如下代码所示:

 1 while color[p[z]] = RED  
 2     do if p[z] = left[p[p[z]]]  
 3           then y ← right[p[p[z]]]  
 4                if color[y] = RED  

此刻父结点的父结点一定期存款在,不然插入前就已不是红黑树。
再者,又分为父结点是外公结点的左子依旧右子,对于对称性,大家借使解开3个倾向就足以了。

在此,大家只思量父结点为岳丈左子的景观。
再者,还足以分为当前结点是其父结点的左子依然右子,不过管理形式是一律的。我们将此归为同一类。

计谋:将方今结点的父结点和伯父结点涂黑,祖父结点涂红,把近期结点指向曾祖父结点,从新的脚下结点重新起首算法。即如下代码所示:

 5                   then color[p[z]] ← BLACK                    ▹ Case 1  
 6                        color[y] ← BLACK                       ▹ Case 1  
 7                        color[p[p[z]]] ← RED                   ▹ Case 1  
 8                        z ← p[p[z]]                            ▹ Case 1  

本着情状一,变化前(图片来自:saturnman)[眼下结点为四结点]:

image.png

变化后:

image.png

插入修复意况二:当前结点的父结点是新民主主义革命,叔伯结点是灰色,当前结点是其父结点的右子
机关:当前结点的父结点做为新的此时此刻结点,以新当前结点为支点左旋。即如下代码所示:

 9                   else if z = right[p[z]]
10                           then z ← p[z]                       ▹ Case 2
11                                LEFT-ROTATE(T, z)              ▹ Case 2

正如图所示,变化前[当下结点为7结点]:

image.png

变化后:

image.png

插入修复情状3:当前结点的父结点是新民主主义革命,二叔结点是茶色,当前结点是其父结点的左子
解法:父结点变为威尼斯绿,祖父结点变为灰白,在伯公结点为支点右旋,操作代码为:

12                           color[p[z]] ← BLACK                 ▹ Case 3
13                           color[p[p[z]]] ← RED                ▹ Case 3
14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3

最后,把根结点涂为鲜蓝,整棵红黑树便再次恢复生机了平衡。

如下图所示[近期结点为二结点]

image.png

变化后:

image.png

一.相比较规则是利用key的自然排序举行比较依旧选拔用户自定义的排序规则实行比较。

红黑树的删减

ok,接下去,大家最终来打听,红黑树的删减操作。

"我们删除的结点的秘技与平常二叉寻找树中删除结点的章程是同样的,假诺被剔除的结点不是有双非空子女,则直接删除这几个结点,用它的唯一子结点顶替它的任务,若是它的子结点都是空结点,这就用空结点顶替它的职位,如若它的双子全为非空,大家就把它的一贯后继结点内容复制到它的地方,之后以同样的法子删除它的后继结点,它的后继结点不恐怕是双子非空,由此此传递进程最两只进行3遍。”

二.原来的红黑树中是或不是业已存在此次插入结点key对应的结点?若是是,则此番操作实际是创新旧值的操作;不然便是骤增贰个结点的操作。

2叉查找树的去除

三番五次上课在此以前,补充表达下2叉树结点删除的三种情况,待删除的结点依照外甥的个数能够分为两种:

  1. 从不外孙子,即为叶结点。直接把父结点的相应外孙子指针设为NULL,删除了这一个之外孙子结点就OK了。
  2. 只有1个幼子。那么把父结点的附和外孙子指针指向外甥的独生子,删除儿子结点也OK了。
  3. 有七个孙子。那是最麻烦的状态,因为你剔除结点之后,还要确定保障满意找出2叉树的布局。其实也比较易于,大家能够挑选左外甥中的最大意素大概右孙子中的最小成分放到待删除结点的岗位,就能够保障结构的不变。当然,你要记得调度子树,终归又现身了结点删除。习贯上海大学家挑选左外甥中的最大意素,其实选用右孙子的纤维成分也同样,未有任何差距,只是人人习于旧贯从左向右。这里大家也选拔左外甥的最大因素,将它放到待删结点的地点。左外孙子的最大意素其实很好找,只要本着左外孙子不断的去搜寻右子树就能够了,直到找到三个尚未右子树的结点。那就是最大的了。

二叉查找树的删减代码如下所示:

TREE-DELETE(T, z)
 1  if left[z] = NIL or right[z] = NIL
 2      then y ← z
 3      else y ← TREE-SUCCESSOR(z)
 4  if left[y] ≠ NIL
 5      then x ← left[y]
 6      else x ← right[y]
 7  if x ≠ NIL
 8      then p[x] ← p[y]
 9  if p[y] = NIL
10      then root[T] ← x
11      else if y = left[p[y]]
12              then left[p[y]] ← x
13              else right[p[y]] ← x
14  if y ≠ z
15      then key[z] ← key[y]
16           copy y's satellite data into z
17  return y

此间有个要求重视掌握的不贰秘诀,在第 63 行的  fixAfterInsertion(e)  方法。那些方法是红黑树新添三个结点的主导措施。

红黑树的删除和删除修复

OK,回到红黑树上来,红黑树结点删除的算法实现是:

RB-DELETE(T, z) 单纯删除结点的总操作

 1 if left[z] = nil[T] or right[z] = nil[T]  
 2    then y ← z  
 3    else y ← TREE-SUCCESSOR(z)  
 4 if left[y] ≠ nil[T]  
 5    then x ← left[y]  
 6    else x ← right[y]  
 7 p[x] ← p[y]  
 8 if p[y] = nil[T]  
 9    then root[T] ← x  
10    else if y = left[p[y]]  
11            then left[p[y]] ← x  
12            else right[p[y]] ← x  
13 if y ≠ z  
14    then key[z] ← key[y]  
15         copy y's satellite data into z  
16 if color[y] = BLACK  
17    then RB-DELETE-FIXUP(T, x)  
18 return y  

“在剔除结点后,原红黑树的品质恐怕被更换,借使剔除的是丁丑革命结点,那么原红黑树的习性依然维持,此时并非做考订操作,假若除去的结点是深绿结点,原红黑树的天性可能会被改成,大家要对其做核查操作。那么哪些树的品质会产生变化呢,如若去除结点不是树唯1结点,那么删除结点的那些支的到各叶结点的肉桂色结点数会产生变化,此时品质5被弄坏。要是被删结点的独步天下非空子结点是石绿,而被删结点的父结点也是辛丑革命,那么性质四被毁坏。假若被删结点是根结点,而它的无与伦比非空子结点是革命,则删除后新根结点将成为米白,违背性质二。”

RB-DELETE-FIXUP(T, x) 苏醒与维持红黑性质的劳作

 1 while x ≠ root[T] and color[x] = BLACK  
 2     do if x = left[p[x]]  
 3           then w ← right[p[x]]  
 4                if color[w] = RED  
 5                   then color[w] ← BLACK                        ▹  Case 1  
 6                        color[p[x]] ← RED                       ▹  Case 1  
 7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1  
 8                        w ← right[p[x]]                         ▹  Case 1  
 9                if color[left[w]] = BLACK and color[right[w]] = BLACK  
10                   then color[w] ← RED                          ▹  Case 2  
11                        x ← p[x]                                ▹  Case 2  
12                   else if color[right[w]] = BLACK  
13                           then color[left[w]] ← BLACK          ▹  Case 3  
14                                color[w] ← RED                  ▹  Case 3  
15                                RIGHT-ROTATE(T, w)              ▹  Case 3  
16                                w ← right[p[x]]                 ▹  Case 3  
17                         color[w] ← color[p[x]]                 ▹  Case 4  
18                         color[p[x]] ← BLACK                    ▹  Case 4  
19                         color[right[w]] ← BLACK                ▹  Case 4  
20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4  
21                         x ← root[T]                            ▹  Case 4  
22        else (same as then clause with "right" and "left" exchanged)  
23 color[x] ← BLACK  

“上面包车型大巴修复景况看起来有一点点复杂,下边我们用叁个解析技艺:大家从被删结点后来代替它的老大结点起首调解,并以为它有额外的一重蓝灰。这里额外一重浅莲红是何等意思呢,大家不是把红黑树的结点加上巳红与黑的另1种颜色,这里只是1种借使,大家感觉大家当下本着它,由此空有额外1种黑褐,能够以为它的天青是从它的父结点被剔除后承接给它的,它未来得以包容三种颜色,假使它原本是辛巳革命,那么未来是红 黑,若是原先是橄榄绿,那么它未来的水彩是黑 黑。有了那重额外的浅浅米灰,原红黑树性质5就能够保险不改变。未来壹旦复苏其余性质就能够了,做法照旧尽量向根移动和穷举全数望。"--saturnman。

若果是以下情形,苏醒比较轻巧:

  • a)当前结点是红 水泥灰
    解法,直接把当前结点染成卡其色,截止此时红黑树性质全体过来。
  • b)当前结点是黑 黑且是根结点,
    解法:什么都不做,结束。

但万1是以下情状吗?:

  • 除去修复景况1:当前结点是黑 黑且兄弟结点为革命(此时父结点和兄弟结点的子结点分为黑)
  • 除去修复景况二:当前结点是黑加黑且兄弟是藏蓝且兄弟结点的七个子结点全为浅莲灰
  • 除去修复情状三:当前结点颜色是黑 黑,兄弟结点是墨紫,兄弟的左子是革命,右子是深珍珠白
  • 除去修复情状四:当前结点颜色是黑-黄绿,它的汉子儿结点是深草绿,但是兄弟结点的右子是乙酉革命,兄弟结点左子的颜料放肆

那时,大家须求调用RB-DELETE-FIXUP(T, x),来苏醒与维持红黑性质的行事。

上面,大家便来分别管理那四种删除修复情状。

去除修复情形1:当前结点是黑 黑且兄弟结点为灰湖绿(此时父结点和兄弟结点的子结点分为黑)。

解法:把父结点染成鹅黄,把兄弟结点染成花青,之后又一次进入算法(大家只谈谈当前结点是其父结点左孩未时的景观)。此调换后原红黑树性质5不改变,而把难题转化为小伙子结点为青绿的情状(注:变化前,原本就未违反性质5,只是为了把标题转化为兄弟结点为青黄的景况)。 即如下代码操作:

//调用RB-DELETE-FIXUP(T, x) 的1-8行代码
 1 while x ≠ root[T] and color[x] = BLACK
 2     do if x = left[p[x]]
 3           then w ← right[p[x]]
 4                if color[w] = RED
 5                   then color[w] ← BLACK                        ▹  Case 1
 6                        color[p[x]] ← RED                       ▹  Case 1
 7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1
 8                        w ← right[p[x]]                         ▹  Case 1

变化前:

image.png

变化后:

image.png

除去修复意况二:当前结点是黑加黑且兄弟是湖蓝且兄弟结点的五个子结点全为威尼斯红。

解法:把当下结点和兄弟结点中抽出壹重卡其色追加到父结点上,把父结点当成新的目前结点,重新进入算法。(此转变后性质5不变),即调用RB-INSERT-FIXUP(T, z) 的第九-拾行代码操作,如下:

//调用RB-DELETE-FIXUP(T, x) 的9-11行代码
9                if color[left[w]] = BLACK and color[right[w]] = BLACK
10                   then color[w] ← RED                          ▹  Case 2
11                        x p[x]                                  ▹  Case 2

变化前:

image.png

变化后:

image.png

剔除修复景况3:当前结点颜色是黑 黑,兄弟结点是墨浅绛红,兄弟的左子是甲辰革命,右子是深藕红。

解法:把兄弟结点染红,兄弟左子结点染黑,之后再在兄弟结点为支点解右旋,之后再也进入算法。此是把如今的情事转化为意况四,而性质伍足以维持,即调用RB-INSERT-FIXUP(T, z) 的第二二-16行代码,如下所示:

//调用RB-DELETE-FIXUP(T, x) 的第12-16行代码
12                   else if color[right[w]] = BLACK
13                           then color[left[w]] ← BLACK          ▹  Case 3
14                                color[w] ← RED                  ▹  Case 3
15                                RIGHT-ROTATE(T, w)              ▹  Case 3
16                                w ← right[p[x]]                 ▹  Case 3

变化前:

image.png

变化后:

image.png

剔除修复情形肆:当前结点颜色是黑-宝石蓝,它的小家伙结点是暗蓝,不过兄弟结点的右子是深灰蓝,兄弟结点左子的水彩率性。

解法:把兄弟结点染成当下结点父结点的水彩,把当下结点父结点染成深蓝,兄弟结点右子染成深翠绿,之后以近期结点的父结点为支点举行左旋,此时算法截至,红黑树全体性质调度正确,即调用RB-INSERT-FIXUP(T, z)的第一7-21行代码,如下所示:

//调用RB-DELETE-FIXUP(T, x) 的第17-21行代码
17                         color[w] ← color[p[x]]                 ▹  Case 4
18                         color[p[x]] ← BLACK                    ▹  Case 4
19                         color[right[w]] ← BLACK                ▹  Case 4
20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4
21                         x ← root[T]                            ▹  Case 4

变化前:

image.png

变化后:

image.png

要明了这些艺术,首先供给先领悟一些预备知识。

正文参谋

本文参谋了算法导论、STL源码分析、Computer程序设计艺术等材料,并引入阅读这个PDF:Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, Wadern, 德文y, February, 2010.
下载地址:http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf。

 

有关树的转动

事先曾经说过,因为红黑树自个儿的性状,其在插入和删除结点后还要经过旋转、着色的操作来使整个树的定义符合红黑树的概念。

着色很好驾驭,无非正是改动结点为革命或浅豆绿,那么关于树的旋转操作,我们是或不是还记得上海南大学学学时先生在黑板上画了诸多树的左旋、右旋图呢?

自个儿在那时候就有一些介绍下树的旋转相关的学问吧。

 

以树的右旋转为例,先看一张图:

 图片 23

图中讲述的是本着a结点的3回右旋操作。

 

然后是右旋操作的源码:

 1     /** 树的右旋操作 */
 2     private void rotateRight(Entry<K,V> p) {
 3         if (p != null) {   //如果待右旋节点p不为空
 4             Entry<K,V> l = p.left;  //获取待右旋节点p的左子节点l
 5             p.left = l.right;  //将p的左子节点指向l的右子节点
 6             //l的右子节点不为空
 7             if (l.right != null) l.right.parent = p; //l的右子节点的父节点指向p(p与l的右子节点建立父子节点关系)
 8             l.parent = p.parent;  //l的父节点指向p的父节点(相当于l取代p的位置)
 9             if (p.parent == null) //p父节点是否为空?
10                 root = l;  //p就是根节点,则将当前根节点变更为l
11             else if (p.parent.right == p) //p是否为其父节点的右子节点?
12                 p.parent.right = l;  //p的父节点的右子节点指向l
13             else p.parent.left = l;   //p的父节点的左子节点指向l
14             l.right = p;  //l的右子节点指向p
15             p.parent = l;  //p的父节点指向l
16         }
17     }

源码中的P变量正是上海体育场合的a结点,l变量正是上海教室的b结点,大家能够相比源码和图,在纸团长图中的节点一步一步根据源码的操作画出来,那样比较轻巧领会。

 

左旋的操作和右旋是相似的,就不再啰嗦了,大家能够把上海教室中的右旋后的树作为根基,左旋后拿走的正是原先的树。左旋源码如下:

 1     /** 树的左旋操作 */
 2     private void rotateLeft(Entry<K,V> p) {
 3         if (p != null) {
 4             Entry<K,V> r = p.right;
 5             p.right = r.left;
 6             if (r.left != null)
 7                 r.left.parent = p;
 8             r.parent = p.parent;
 9             if (p.parent == null)
10                 root = r;
11             else if (p.parent.left == p)
12                 p.parent.left = r;
13             else
14                 p.parent.right = r;
15             r.left = p;
16             p.parent = r;
17         }
18     }

 

掌握树的旋转操作之后,还索要领会2个小知识。因为红黑树本人是一棵贰叉树,2叉树的各种结点最多有多少个子结点(左子结点和右子结点)

那正是说在插入三个结点时,大概插入的结点是左子结点,也说不定插入的是右子结点,如下图:

图片 24

因为结点三和结点八都是在根结点十的左子结点下插入的,所以这种插入情势称之为左子树插入。

上海体育场所中左边插入的结点三是结点陆的左子结点,这种意况大家誉为左子树外侧插入;

而左边的结点八是结点6的右子结点,这种场合我们誉为左子树内侧插入。

当然,右子树插入,右子树外侧、内侧插入,聪明如大家,应该轻易自行推导出来吧~~

 

OK,到那边境海关于红黑树插入结点的放置知识已经介绍完结,接下去就要剖析插入结点的主干源码了 : )

 

 

红黑树插入结点主题措施源码剖析

图片 25图片 26

 1     /**  平衡树的相关操作  */
 2     
 3     /**  返回当前节点的颜色,如果节点为空则默认返回黑色 */
 4     private static <K,V> boolean colorOf(Entry<K,V> p) {
 5         return (p == null ? BLACK : p.color);
 6     }
 7 
 8     /**  返回当前节点的父节点,没有父节点则返回空 */
 9     private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
10         return (p == null ? null: p.parent);
11     }
12 
13     /**  给当前结点设置颜色  */
14     private static <K,V> void setColor(Entry<K,V> p, boolean c) {
15         if (p != null)
16             p.color = c;
17     }
18 
19     /**  返回当前节点的左子节点,没有左子节点则返回空 */
20     private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
21         return (p == null) ? null: p.left;
22     }
23 
24     /**  返回当前节点的右子节点,没有右子节点则返回空 */
25     private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
26         return (p == null) ? null: p.right;
27     }
28 
29 
30    /**
31      * 树插入一个新结点后,将其根据红黑树的规则进行修正
32      * @param x   当前插入树的节点
33      */
34     private void fixAfterInsertion(Entry<K,V> x) {
35         //默认将当前插入树的节点颜色设置为红色,为什么???
36         //因为红黑树有一个特性: "从根节点到所有叶子节点上的黑色节点数量是相同的"
37         //如果当前插入的节点是黑色的,那么必然会违反这个特性,所以必须将插入节点的颜色先设置为红色
38         x.color = RED;
39         //第一次遍历时,x变量保存的是当前新插入的节点
40         //为什么要用while循环?
41         //因为在旋转的过程中可能还会出现父子节点均为红色的情况,所以要不断往上遍历直至整个树都符合红黑树的规则
42         while (x != null && x != root && x.parent.color == RED) { //如果当前节点不为空且不是根节点,并且当前节点的父节点颜色为红色
43             if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //如果当前节点的父节点等于当前节点父节点的父节点的左子节点(即当前节点为左子树插入)
44                 
45                 Entry<K,V> y = rightOf(parentOf(parentOf(x)));  //获取当前节点的叔父节点(和当前插入节点的父节点同辈的另外那个节点)
46                 if (colorOf(y) == RED) {  //如果叔父节点的颜色为红色
47                     //以下4步用来保证不会连续出现两个红色节点
48                     setColor(parentOf(x), BLACK);  //将当前节点的父节点设置为黑色
49                     setColor(y, BLACK);  //将当前节点的叔父节点设置为黑色
50                     setColor(parentOf(parentOf(x)), RED);  //将当前节点的祖父节点设置为红色
51                     x = parentOf(parentOf(x));  //当前遍历节点变更为当前节点的祖父节点
52                 } else {  //如果叔父节点的颜色为黑色,或没有叔父节点
53                     if (x == rightOf(parentOf(x))) {  //如果当前节点为左子树内侧插入
54                         x = parentOf(x);  //将x变更为当前节点的父节点
55                         rotateLeft(x);  //对当前节点的父节点进行一次左旋操作(旋转完毕后x对应的就是最左边的叶子节点)
56                     }
57                     //如果当前节点为左子树外侧插入
58                     setColor(parentOf(x), BLACK); //将当前节点的父节点设置为黑色
59                     setColor(parentOf(parentOf(x)), RED); //将当前节点的祖父节点设置为红色
60                     rotateRight(parentOf(parentOf(x)));  //对当前节点的祖父节点进行一次右旋
61                 }
62             } else {  //当前节点为右子树插入
63                 Entry<K,V> y = leftOf(parentOf(parentOf(x)));  //以下步骤与上面基本相似,只是旋转方向相反,不再赘述
64                 if (colorOf(y) == RED) {
65                     setColor(parentOf(x), BLACK);
66                     setColor(y, BLACK);
67                     setColor(parentOf(parentOf(x)), RED);
68                     x = parentOf(parentOf(x));
69                 } else {
70                     if (x == leftOf(parentOf(x))) {
71                         x = parentOf(x);
72                         rotateRight(x);
73                     }
74                     setColor(parentOf(x), BLACK);
75                     setColor(parentOf(parentOf(x)), RED);
76                     rotateLeft(parentOf(parentOf(x)));
77                 }
78             }
79         }
80         root.color = BLACK;//注意在旋转的过程中可能将根节点变更为红色的,但红黑树的特性要求根节点必须为黑色,所以无论如何最后总要执行这行代码,将根节点设置为黑色
81     }

View Code

中心措施是   fixAfterInsertion(Entry<K,V> x),简单描述下该措施的逻辑:

从插入的结点开端,往上遍历父结点直到根结点,对每一回遍历到的结点判别是左子树插入照旧右子树插入

下一场再剖断当前遍历到结点的叔父结点的颜色为革命可能红棕,不相同颜色有例外的操作来使红黑树符合其自己性质,最终遍历到根结点时,就平衡了一棵红黑树。

 

光看源码比较难知晓,上面作者举多少个插入结点的事例,结合上方的源码,大家能够在纸少校每一遍插入结点的操作一步一步和下边包车型客车源码举行认证,那样能够更加好的知道那壹进程:

图片 27

咱俩假使1开头只有3个结点十,其为根结点,且因红黑树性质决定了根结点必须为深黑。

 

下一场,我们插入第叁个结点八伍。因为八五比10大,所以八伍确定为拾的右子结点。

由源码第2八行可见,私下认可插入结点的颜色为革命,而由第陆二行的while循环可见,当前布置的革命结点八伍它的父结点为10,十为根结点必定为深绿,所以不合乎while的大循环条件,直接退出方式。

此时红黑树的协会如下图所示:

图片 28

 

然后我们插入第壹个结点 一伍.因为壹五比十大,但又比八第五小学,所以应当是右子树内侧插入。

因为暗许插入结点为革命,所以此时红黑树结构如下图所示:

图片 29

而因为红黑树自个儿特点要求无法有连接四个结点都以新民主主义革命,所以要进行平衡树的相关操作

因为根结点10尚无左子结点,所以不满意第4四行的if判别,转而走第4玖行的else部分的代码。

而又因为一五结点是捌伍结点的左子结点,所以会走第玖0行的if语句,将新添结点的指针从一5结点移动到捌伍结点并做右旋操作,然后走下一行代码将15结点更改青黑

那时红黑树的组织如下图所示:

图片 30

下一场实践7伍、76两行代码,将拾结点变为葡萄紫,再以十结点为规范做左旋操作,全体成就后此时红黑树如下图所示:

图片 31

 

咱们在纸上校每一步的操作能够思考后总体画下来,自然能够很明显的收看每一步发生的改换。

 

接下去插入70结点,70比壹五大又比八五小,所以依然是右子树内侧插入。

因为八5结点是丙戌革命的,所以此时走第54行的if代码,通过if中的4行代码将10结点、八伍结点变为水草绿,将15结点变为石磨蓝。

别忘了最后还会实行一句  root.color = BLACK 会将根结点壹伍变为蓝色。全体操作达成后,红黑树结构如下图:

图片 32

 

接下去再插入结点就不再像上面一步步剖析了,作者会把每便插入结点关键的中间状态以及成就插入的情状图贴上,大家能够活动参照他事他说加以考察: )

 

接下去插入20结点,中间状态图如下所示:

1. 图片 33

 

2.图片 34

 

接下去插入60结点:

图片 35

 

接下去插入30结点:

1.图片 36

 

2.图片 37

 

最终插入50结点:

1.图片 38

 

2.图片 39

 

3.图片 40

 

注:本篇小说全部图片出处均为  新浪——1月的仓颉

 

到此地treeMap的插入结点操作已经整整教学实现,下壹篇小说会深入分析treeMap删除结点的长河。

 

编辑:亚洲城ca88唯一官方网站 本文来源:红黑树的插入及旋转操作详细解读,教你透彻了

关键词: 亚洲城ca88