二叉树我们都知道,就是一棵树,红黑二叉树是满足特殊条件的二叉树,这棵树是一颗有颜色,而且符合一定规则的树,规则如下:
- 根节点必须是黑色的
- 没有两个红色节点是紧挨着(父节点和子节点不可以同时为红色)
- 从根节点到任意末尾节点的黑色节点必须是相同的
如下图所示的三棵树:
树1: 满足根节点是黑色的,也没有两个红色节点相连,但是不满足最后一个条件
树2:满足所有条件
树3:不满足第三个条件
注意:我们认为默认的节点都有两个值为None的两个节点
红黑二叉树的插入
我们现在看一下如何将一个元素插入红黑二叉树:
- 如果是一个None的树,我们直接创建一个根节点,并且颜色为黑色
- 所有插入的新的节点,颜色都是红色的
- 如果插入节点后,插入节点的父节点是黑色,完成插入
- 如果插入节点后,插入的节点的父节点红色 ,则分两种情况:
1:如果这个红色父节点没有同级的兄弟姐妹,或者兄弟是黑色:调整颜色即可
2:如果这个红色节点的兄弟是红色,修改颜色兄弟和自己的颜色,并且修改父节点的颜色(如果父节点不是根节点的话)
例子如下:
下面就是特殊情况了:当我们插入完成之后,如果出现 “红-红”如何解决:
第一种情况:插入元素为红,父节点为红,父节点的兄弟节点为红的时候:修改父节点和其兄弟节点的颜色,并将父节点的父节点修改颜色(除非是根节点)
注:点击查看大图
情况2:若果插入之后出现“红-红”,并且插入节点为左节点,父节点为左节点的情况下,父节点的兄弟节点不存在的情况:右旋转,具体步骤点击查看大图
情况3:若果插入之后出现“红-红”,并且插入节点为右节点,父节点为左节点的情况下,父节点的兄弟节点不存在的情况:先左旋转,然后右旋转,具体步骤点击查看大图
演示一个复杂的的情况4:
其实,我们都遵循如下规律:
- LL ——>R
- RL—->LR
- RR——>L
- LR——->RL
解释一下: 前边是我们遇到红红的情况,第一个L,是指父节点是左节点还是右节点,第二个是指插入节点是做节点还是有节点,然后根据这两个进行后边旋转的选择,例如情况1就是 LL 所以我们只需要一次右旋转即可,此处要注意,我们旋转后的颜色变化,右旋转后,父节点和爷爷节点的颜色发生变化了,左旋转病没有变化
Latest posts by Zhiming Zhang (see all)
- aws eks node 自动化扩展工具 Karpenter - 8月 10, 2022
- ReplicationController and ReplicaSet in Kubernetes - 12月 20, 2021
- public key fingerprint - 5月 27, 2021
墨云 2018/04/24 16:19
收藏了,感谢分享
青山 2018/05/08 11:31
这是什么领域的?我高中森
看不懂哈哈哈
123 2018/07/19 18:24
人在哪,我想砍他
我想飞高高 2018/08/13 17:52
情况4看不懂了
Zhiming Zhang 博主 2018/08/14 09:16
@ 再看一遍
怎样网 2018/11/21 13:40
好像真没看懂....
砍你 2019/03/26 11:42
刀都给买好了,就差你在哪了
咕噜咕噜 2019/06/13 18:08
你人在哪啊?我是真的想砍你
砍你啊 2019/07/13 22:32
地址发过来,砍不死你
20200813 2020/08/13 11:35
”1:如果这个红色父节点没有同级的兄弟姐妹,或者兄弟是黑色:调整颜色即可“ 这里只简单说是调整颜色,后来例4中出现这种情况的时候又说旋转,读者阅读的时候会造成疑惑,建议修改。 “如果这个红色父节点没有同级的兄弟姐妹,或者兄弟是黑色” 后面旋转介绍里面只描述了 红色父节点没有同级兄弟情况,没有举有黑色兄弟的例子,只是在例4里面提及,会给读者造成疑惑
校长 2020/12/09 15:13
二叉树 右边不是一定比根节点大么?
Zhiming Zhang 博主 2020/12/14 08:50
@ 二叉树很多种....