TreeMap
底层红黑树
复杂度
可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目
五个性质
- Each node is either red or black. (要么红色要么黑色)
- The root is black (根是黑色). This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
- All leaves (NIL) are black (所有叶子都是黑色).
- If a node is red, then both its children are black (如果结点是红色，那么所有孩子都是黑色, 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. Some definitions: the number of black nodes from the root to a node is the node's black depth; the uniform number of black nodes in all paths from root to the leaves is called the black-height of the red–black tree (从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点)
这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
