红黑树

　　红黑树(Red-Black Tree)是二叉搜索树(BinarySearch Tree)的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点按从小到大的顺序依次插入后)。而红黑树在每一次插入或删除节点之后都会花O(log N)的时间来对树的结构作修改，以保持树的平衡。也就是说，红黑树的查找方法与二叉搜索树完全一样;插入和删除节点的的方法前半部分节与二叉搜索树完全一样，而后半部分添加了一些修改树的结构的操作。

　　map就是采用红黑树存储的，红黑树(RB Tree)是平衡二叉树，其优点就是树到叶子节点深度一致，查找的效率也就一样，为logN。在实行查找，插入，删除的效率都一致，而当是全部静态数据时，没有太多优势，可能采用hash表各合适。

　　相对来说，hash_map是一个hashtable占用内存更多，查找效率高一些，但是hash的时间比较费时。总体而言，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小无关，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小， hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且 hash_map的构造速度较慢。

　　现在知道如何选择了吗?权衡三个因素: 查找速度, 数据量, 内存使用。

　　红黑树的每个节点上的属性除了有一个key、3个指针：parent、lchild、rchild以外，还多了一个属性：color。它只能是两种颜色：红或黑。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下4点性质：

　　1. 根节点是黑色的。

　　2. 空节点是黑色的(红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点)。

　　3. 红色节点的父、左子、右子节点都是黑色。

　　4. 在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。