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

原创
2018/10/22 20:14
阅读数 36

经过上一版的验证,发现如果按照以前的算法计算出来的结果是不正确的,导致后续的计算过程中产生了很多错误的结果。没有理清楚其中的节点关系,基于上面的错误总结经验,主要是参考《算法导论》中关于红黑树算法的介绍,基本上摸清楚了其中的原理。

我的理解如下:

1.首先离不开红黑树的5条原则  1.1 每一个节点只能是黑色或者红色 1.2 根节点只能是黑色 1.3 从任何一个节点到叶子节点中包含的黑色节点数一定是相同的(这是为了保证红黑树的平衡) 1.4 红色节点的子节点必须是黑色节点(这是为了保证后续的旋转正确性) 1.5每一个叶子节点都为黑色

2.插入的时候,必须是首先默认新节点为红色节点,然后来调整红黑树,这是为了首先先保证第3条规则的满足,然后再通过调整树结构来动态调整树结构。还有一个隐患的条件,如果父节点为黑色,则不需要任何变化,新添加进来的元素不会影响红黑树的结构,如果不是,就违背了第4条规则,需要根据具体的情况调整了。

3.接下来就是旋转的概念了,按照书上的伪代码来看:是以当前节点的父节点所在的左右位置来区别;

3.1 如果父节点和叔叔节点都为红色,则将叔叔节点和父节点染黑,将爷爷节点染红。并以爷爷节点进行调整。

3.2.如果父节点是左节点,当前节点是右节点,则以父节点进行左旋,并且置父节点为当前节点  ----->3.2.1

3.2.1 此时,节点的结构一定是当前节点和父节点都为红色,并且父子节点所处的相对位置都是一致的(父节点相对于爷爷节点,子节点相对于父节点,都为左节点)爷爷节点为黑色,然后将父节点涂黑,爷爷节点涂红,并以爷爷节点进行右旋转。此时已经满足二叉树的结构了,调整结束。

3.3 如果父节点是左节点,当前节点是左节点,按照3.2.1所示旋转(其实3.2的转换,就是为了使其达成3.3的样子,从而做旋转)---->3.2.1。

3.4 如果父节点是右节点,当前节点是左节点,则以父节点进行右旋,并且置父节点为当前节点 ---->3.4.1

3.4.1 此时,节点的结构一定是当前节点和父节点都为红色,并且父子节点所处的位置都是一致的(父节点相对于爷爷节点,子节点相对于父节点,都为右节点)爷爷节点为黑色,然后,将父节点涂黑,爷爷节点涂红,并以爷爷节点进行左旋转。此时已经满足红黑树的结构了,调整结束。

3.5 如果父节点是右节点,当前节点是右节点,则按照3.4.1的结构进行调整 ------>3.4.1

后记:

    红黑树的数据有一个隐含的应用:每一个key值都不能重复。c++的map底层结构就是红黑树

源码链接地址:

https://gitee.com/gaoxe/code_sharing/blob/master/RBT.py

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