​这是笔者一个好友面试阿里时，被问及的一个问题，应该不少人看到这个问题都会一面懵逼。因为，大部分的文章都是分析链表是怎么转换成红黑树的，但是并没有说明为什么当链表长度为8的时候才做转换动作。笔者第一反应也是一样，只能初略的猜测是因为时间和空间的权衡。

    根据上一节的红黑树分析, 结合 sgi stl map 的实现, 看看红黑树的源码是如何实现的. 以下主要以代码的注释为主. sgi stl map 底层实现是 _Rb_tree类, 为了方便管理, _Rb_tree 内置了 _M_header, 用于记录红黑树中的根节点, 最小节点和最大节点. 在插入删除中都会对其进行维护.

    红黑树并没有想象的那么难, 初学者觉得晦涩难读可能是因为情况太多. 红黑树的情况可以通过归结, 通过合并来得到更少的情况, 如此可以加深对红黑树的理解. 网络上的大部分红黑树的讲解因为没有「合并」.

    要学习红黑树，那么首先要知道红黑树到底是个什么东西，其实他的定义在网络到随处都可以搜索到，他是一种平衡二叉搜索树，在这个定义里面引入了三个关键词，一是二叉树，另一个是二叉搜索树，第三个是平衡。我们一层一层分析， 二叉树，他的定义是每个节点最多只有两个子树（即左子树和右子树，当然也可以没有子树），如下图是一个简单的二叉树： 对于这样的数据结构，在C语言中通常这样来定义结构体 [c] typedef struct _binary_t...

    最近在修改一个代理机server，增加url rewrite的功能，由于其单机的访问量很高，20000/s左右，对性能要求很高，所以在做url映射的时候，纠结在用map还是hashmap存储映射的问题上。于是做了一个...