红黑树从一到无穷(第一版)

原创
2018/10/22 11:15
阅读数 71

红黑树需要把握的5个原则,是构建红黑树的基础:

  • 1.每一个节点,要么是黑色,要么是红色
  • 2.有一个根节点,并且为黑色
  • 3.红色节点的子节点一定是黑色(此处注意:并未规定,黑色节点的子节点一定是红色)
  • 4.对于任何一个节点到任何一个叶子节点的路径中,包含的黑色节点数量都相同
  • 5.每一个叶子节点都为黑色(此处注意,每一个叶子节点都默认会存在一个空的黑色叶子节点)

根据以上五条原则,个人理解如下:

  • 1.第一条是为了保证算法的简单性和规则性,防止更多种可能性的存在,增加算法的复杂性
  • 2.第二条保证在结构调整时能够快速实现
  • 3.第3条是硬性要求,保证红黑树的平衡和调整
  • 4.第四条是最重要的,保证红黑树的平衡,是判定是否是红黑树的重要依据
  • 5.第五条,暂时没有看出有什么用,可以忽略

红黑树的插入原则: 此处插播一条实践发现的现象:

        在插入的时候,是否只需要最多3次的调整就可以实现的,目前来看,结果未知。不管是左旋还是右旋,都需要保证,将最底下的节点作为当前节点,判断是否满足,在每一次调整过程中,是对当前节点的一个调整,使其可以满足红黑树的规则,但是并没有做当前节点后面节点的情况,每一次的当前节点的改变,必然会影响其子节点的从属关系,也会在一定程度上不满足红黑树的规则,所以在一次调整过后,将当前节点的子节点作为当前节点处理,是合理的。

        并且在调整的时候需要选择一定的点,每一次的旋转都是为了调整那个可能会不符合二叉树的点,基于此原则,

  1. 如果父节点和叔叔节点都为红色时,通过染色父节点,叔叔节点为黑色,爷爷节点为红色,可以保证当前操作节点是满足红黑树原则的,从此种找到可能会打破红黑树原则的节点,进行变换,即爷爷节点可能会打破,所以,就需要对爷爷节点进行调整使其满足红黑树的原则。
  2. 如果父节点为红色,叔叔节点为黑色,并且当前节点是左节点,此时,将父节点设置为黑色,将爷爷节点设置为红色,是当前节点满足红黑树的原则,此时,爷爷节点可能会打破红黑树的原则,此刻,将爷爷节点设置为当前节点进行调整使其满足红黑树的原则。此处有一个分支,父节点为左节点,则以爷爷节点右旋,此时,新的可能不满足红黑树的节点为父节点的右子节点,然后以此节点进行调整。如果父节点为右节点,则爷爷节点左旋,此时,新的可能不满足红黑树的节点为父节点的左子节点,然后以此节点进行调整。
  3. 如果父节点为红色,叔叔是黑色,当前节点是右节点,则以父节点左旋,此时,新的可能不满足红黑树的节点为当前节点的左子节点,然后以此节点进行调整。

这其中容易犯的错误是,不清楚如何旋转,如何选择后续处理的节点,从而获得的红黑树是错误的。特别是第二点的时候,父节点为红色,叔叔节点为黑色,此时还需要判断父节点相对于爷爷节点的位置,如果是父节点是左节点,则右旋,如果是右节点则左旋。

第二点易犯的错误是:

    在左旋完成后,当前节点要变为旋转节点右节点的左节点,这是因为,可能此节点有可能是不符合红黑树规则的,所以需要对其进行调整。

     在右旋完成后,当前节点要变为旋转节点左节点的右节点,同上的原因,需要对其进行调整。

经过上面的调整之后,退出的判断条件为:当前节点的父节点为黑色节点为止。(特殊情况是:没有父节点了,则当前节点为root节点,将节点图黑,退出)。

 

红黑树的自检:

1.从root到每一个叶子节点所包含的黑色节点数是相同的

2.每一个红色节点的子节点都为黑色

 

后续:

按照上述的算法,还是有问题,会出现黑色节点的数量不一致的问题,不满足红黑树规则。

经过仔细的筛选发现,当当前节点为右节点,并且父节点为左节点时,应该右旋。

花絮:

在考虑节点插入调整的时候,确定左旋和右旋,需要考虑父节点相对于爷爷节点的位置,来确定如何旋转。

红黑树在调整过程中,先通过旋转,将每个节点摆平再处理。如:父节点为左节点,当前节点为父节点的右节点,则通过父节点右旋,使其可以将节点摆平在一条直线上,设置当前节点为父节点,然后根据左节点的旋转规则进行调整,将父节点涂黑,爷爷节点涂红,有一个关键的因素,在最开始确定如何旋转时,都假定红色节点的子节点为红色,叔叔节点一定是黑色,不然就不成立。

 

参考网址:

https://www.cnblogs.com/zjutzz/p/3281319.html

漫画算法-红黑树 https://www.sohu.com/a/201923614_466939

http://www.cnblogs.com/skywang12345/p/3245399.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部