算法导论—红黑树

华电北风吹
天津大学认知计算与应用重点实验室
日期：2015/9/9

红黑树是对二叉树的一种平衡扩展。红黑树采用开放的数据扩张策略，并且对于诸如插入、查询，删除有$\Theta($lg $n)$的时间复杂度，因此也是一种应用比较广泛的数据结构。

一、红黑树的节点
节点属性：关键字key，节点颜色，左孩子指针，右孩子指针，父节点指针，卫星数据。
虚拟节点—NIL：对于红黑树中所有节点如果没有父节点或者缺少某个子节点，则把对应的指针指向同一个NIL。

二、红黑树的性质
1、每个节点的颜色是红色或黑色。
2、根节点是黑色。
3、每个叶节点是黑色。
4、如果一个节点是红色的，他的两个子节点都是黑色。
5、对于红黑树中的每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同个数的黑色节点。
节点的黑高：从该节点(不包含该节点)到任意一个叶子节点的任意一条简单路径上黑色节点的个数。

三、红黑树的旋转

四、红黑树的插入

五、红黑树的删除