关于红黑树安插时的疑惑

关于红黑树插入时的疑惑
看了许多关于红黑树的介绍，可是有一点始终回绕我。就是在插入时，若父结点是红色，叔父结点为黑色的情况，例如：

这种情况，无论是插入前还是插入再调整后都是违反了性质5的呀（对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一样）。由于叔叔结点下面也是存在黑哨兵的，所以包含叔叔结点的路径上的黑结点数目应该会多一个才对。 这个状态，一般是由其他状况旋转之后变化而来。

[解决办法]
http://blog.csdn.net/v_JULY_v/article/details/6105630 这篇文章比较详细。
[解决办法]

引用:

看了许多关于红黑树的介绍，可是有一点始终回绕我。就是在插入时，若父结点是红色，叔父结点为黑色的情况，例如：

这种情况，无论是插入前还是插入再调整后都是违反了性质5的呀（对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一样）。由于叔叔结点下面也是存在黑哨兵的，所以包含叔叔结点的路径上的黑结点数目应该会多一个才对。

就你这个例子来说，进入这个情况的前提条件是1,2,3和叔应当有同样深度的黑节点。然后经过这个调整以后，黑节点深度依然不变。

注意你这里的叔应当和1,2,3一样理解成一棵子树，这个子树的根是黑色。

查看更多 下一篇