红黑树

红黑树是一种二进制查找树，但在每个节点上增加一个存储位表示节点的颜色，可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

树中灭个节点包含五个域，color,key,left,right 和p。如果某及诶但没有一个子节点或父节点，则该节点响应的指针域包含值NIL.我们将把这些NIL指向二叉查找树的外节点（叶子）指针,而把带关键字的节点，视为树的内节点。

一棵二进制查找树如果满足以下性质，则说明是一棵红黑树。

1. 每个节点或是红色的，或是黑色的。
2. 根节点是黑色的。
3. 每个叶节点是黑色的。
4. 如果一个节点是红色的，那么它的儿子是黑色的。
5. 对于每个节点 ，从该节点到子孙节点的所有路径上包含相同数目的黑色节点。