11 数据结构和算法——红黑树
红黑树也是一种自平衡的二叉查找树。
- 每个结点要么是红的要么是黑的。（红或黑）
- 根结点是黑的。 （根黑）
- 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。 （叶黑）
- 如果一个结点是红的，那么它的两个儿子都是黑的。 （红子黑）
- 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。（路径下黑相同）
如图就是一棵典型的红黑树。保证红黑树满足它的基本性质，就是在调整数据结构自平衡。
而红黑树自平衡的调整操作方式就有旋转和变色两种。
红黑树是一种应用很广的数据结构，如在Java集合类中TreeSet和TreeMap的底层，C++STL中set与map，以及linux中虚拟内存的管理。