首页 » python » 正文

红黑二叉树的插入与旋转图解(看不懂你砍我)

二叉树我们都知道,就是一棵树,红黑二叉树是满足特殊条件的二叉树,这棵树是一颗有颜色,而且符合一定规则的树,规则如下:

  • 根节点必须是黑色的
  • 没有两个红色节点是紧挨着(父节点和子节点不可以同时为红色)
  • 从根节点到任意末尾节点的黑色节点必须是相同的

如下图所示的三棵树:

红黑树.001

 

树1: 满足根节点是黑色的,也没有两个红色节点相连,但是不满足最后一个条件

树2:满足所有条件

树3:不满足第三个条件

注意:我们认为默认的节点都有两个值为None的两个节点

红黑二叉树的插入

我们现在看一下如何将一个元素插入红黑二叉树:

  • 如果是一个None的树,我们直接创建一个根节点,并且颜色为黑色
  • 所有插入的新的节点,颜色都是红色的
  • 如果插入节点后,插入节点的父节点是黑色,完成插入
  • 如果插入节点后,插入的节点的父节点红色 ,则分两种情况:

1:如果这个红色父节点没有同级的兄弟姐妹,或者兄弟是黑色:调整颜色即可

2:如果这个红色节点的兄弟是红色修改颜色兄弟和自己的颜色,并且修改父节点的颜色(如果父节点不是根节点的话)

 

例子如下:

红黑树.001红黑树.002

下面就是特殊情况了:当我们插入完成之后,如果出现 “红-红”如何解决:

第一种情况:插入元素为红,父节点为红,父节点的兄弟节点为红的时候:修改父节点和其兄弟节点的颜色,并将父节点的父节点修改颜色(除非是根节点)

注:点击查看大图

 

红黑树.003 红黑树.004 红黑树.005 红黑树.006 红黑树.007 红黑树.008

 

情况2:若果插入之后出现“红-红”,并且插入节点为左节点,父节点为左节点的情况下,父节点的兄弟节点不存在的情况:右旋转,具体步骤点击查看大图

红黑树.008 红黑树.009 红黑树.010 红黑树.011 红黑树.012 红黑树.013

 

情况3:若果插入之后出现“红-红”,并且插入节点为右节点,父节点为左节点的情况下,父节点的兄弟节点不存在的情况:先左旋转,然后右旋转,具体步骤点击查看大图

红黑树.014 红黑树.015 红黑树.016 红黑树.017 红黑树.018 红黑树.019 红黑树.020

演示一个复杂的的情况4:

红黑树.021 红黑树.022 红黑树.023 红黑树.024 红黑树.025 红黑树.026 红黑树.027 红黑树.028

 

其实,我们都遵循如下规律:

  • LL ——>R
  • RL—->LR
  • RR——>L
  • LR——->RL

解释一下: 前边是我们遇到红红的情况,第一个L,是指父节点是左节点还是右节点,第二个是指插入节点是做节点还是有节点,然后根据这两个进行后边旋转的选择,例如情况1就是 LL 所以我们只需要一次右旋转即可,此处要注意,我们旋转后的颜色变化,右旋转后,父节点和爷爷节点的颜色发生变化了,左旋转病没有变化

 

发表评论