红黑树性质:
1、每个节点或为红色或为黑色
2、根节点为黑色
3、叶子节点为黑色
4、如果一个节点为红色,则其子节点为黑色
5、对每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点
所以下图中的这个链表应该符合红黑树的这五个性质。如果红黑树经过插入,删除等一系列操作之后,退变为下图,那不就意义不大了?还是说下图这个不属于红黑树(为了让图更清楚,叶子节点nil省略)
红黑树叶子结点的定义是nil结点,nil结点没有数据,每个数据结点的子结点如果少于两个都用nil填满,也就是上图1-4都有另一个nil子结点,n有两个nil子结点,规则5说的到所有叶子的距离,不是到最靠下的数据结点的距离,而是到所有nil结点的距离。