红黑树
红黑树简介
红黑树（Red-Black Tree）是一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红色或黑色。
红黑树特性
- 每个节点或是黑色，或是红色。
- 根节点是黑色。
- 每个叶子节点是黑色。
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
红黑树图示
红黑树应用
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(logn)，效率非常之高。
例如，Java集合中的 TreeSet 和 TreeMap，C++ STL中的 set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
红黑树自平衡
- 左旋：以某个结点作为旋转结点（X），其右子结点（Y）变为旋转结点的父结点，其右子结点的左子结点（β）变为旋转结点的右子结点，左子结点保持不变。
- 右旋：以某个结点作为旋转结点（Y），其左子结点（X）变为旋转结点的父结点，其左子结点的右子结点（β）变为旋转结点的左子结点，右子结点保持不变。
- 变色：结点的颜色由红变黑或由黑变红。