一句话经典总结红黑树插入

首先大牛绕道,本文适合想要快速懂得红黑树插入的过程,而暂时不考虑算法实现细节的人。

红黑树需要保持的性质:

1、 每个结点的颜色只能是红色或黑色。
2、 根结点是黑色的。
3、 每个叶子结点都带有两个空的黑色结点(被称为黑哨兵nil),如果一个结点n的只有一个左孩子,那么n的右孩子是一个黑哨兵;如果结点n只有一个右孩子,那么n的左孩子是一个黑哨兵。
4、 如果一个结点是红的,则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5、 对于每个结点来说,从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。

插入逻辑:
1、插入点都默认为红色
2、黑父:直接插入,没有然后了
3、红父+红叔:直接插入,然后将父&叔颜色变为黑色,祖颜色变为红色,转而判定祖节点
4、红父+黑叔:直接插入,然后将祖、父、叔、兄、自己、加上两个哨兵儿子,一共七人,排序旋转(左转或右转)为黑-红-黑三层树

注意当红父红叔时,如果祖是根节点,则还是保持黑色

标签