1. 数据结构与算法

1.1 红黑树

Red-black tree，是一种自平衡二叉查找树，典型用途是实现关联数组，1972 年由鲁道夫.贝尔发明，被称为 “对称二叉 B 树”。有着良好的最坏情况运行时间，可以在 O(logn) 时间内完成查找、插入、删除。

关联数组，又称映射（map）、字典（Dictionary），包含着类似于（键、值）的有序对。c++ 中的 map 就是，set 虽然不是键值对，但底层也是基于红黑树的。关联数组中的键值对也可以重复，比如 c++ 中的 multimap。

为了保证平衡性，红黑树需要满足 5 个约束：

1、节点是红色或黑色；
2、根是黑色；
3、所有的叶子都是黑色（叶子是NIL节点）；
4、每个红色节点必须有两个黑色子节点；
5、从任一节点到其每个叶子节点的简单路径都包含相同数目的黑色节点；

这些约束保证了红黑树关键特性：从根到叶的最长可能路径不多于最短可能路径的两倍长。所以，这棵树大致上是平衡的。

只读操作与普通的二查找叉树一样，但插入和删除操作可能会破坏红黑树的性质。恢复性质，需要少量的 ( O(logn) ) 颜色变更和不多于 3 次的树旋转。

[1] wikipedia. 红黑树. Available at https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91.