引用:
作者: bankrock  可以做到所有操作都是O(lgn)的算法在算法导论的14章讲过，简单的说是在RbTree里记录每个节点的子节点数，插入、删除、查找节点和查找排序位置都是O(lgn)时间复杂度 |
开始我的想法也差不多，而且RB Tree已有现成的实现，只需修改一下。不过觉得：
1. 当元素量很大时，插入、删除操作需要修改的值个数（树的深度）比较多，因为只要是路径上的节点，都需要修改；
2. 旋转节点的时候比较麻烦，特别是删除算法本来就很复杂了。
后来跟同事讨论了一下，觉得使用B+ Tree可能会简单一些：
1. 本来每个叶子节点都记录了自己的元素个数，只需给内部节点的每个指针加一个字段，记录所指向的子树的节点个数就可以了；
2. 由于B+ Tree的深度比较少，插入、删除元素的时候需要修改的值个数会少一些；
3. B+ Tree没有旋转问题，只有分裂和合并节点，在内部节点的指针发生变化时，修改计数值比较容易；
4. 查询排序位置的复杂度也是O(lgn)。
不知各位觉得怎么样？或者有更好的办法。