红黑树

红黑树是一种二叉查找树，树中每个加点包含五个域：color，key，left， right和p。

红黑树性质：

1)每个结点或是红的，或是黑的

2)根结点是黑的

3)每个叶结点是黑的

4)如果一个结点是红的，则它的两个儿子都是黑的

5)对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点