经过三天的奋战 传说中的2-3树的insert find remove 三大基本操作已经完成
刚开始就对网上2-3Tree的资料稀少而惊奇 发现2-3Tree的实现代码更罕见:找不到c++,java的也很少
于是自己写,差点被恶心死:书上说的过于理论化,说用3个指针分别存儿子..事实证明,这样基本写不出来..
然后我突然想到2-3Tree是B树的一种,曾经在wiki上看到B树的结构:一个父亲的儿子用一个链表组织起来
妙哉!这样不需要知道父结点也能对一个结点的兄弟进行操作.
实现ok了,花了一定时间保证正确性.然后随便测了组N=1000000,M=10000(N为指令数,M为数的上限)的随机数据,结果让人跌眼睛的是treap竟比2-3快一些!
把N改大几个数量级也是这样.
原来是我把M弄得太小了,这样treap的常数优势就体现出来了,而2-3由于维护时较复杂.
于是我选用不同的N和M,以及同时使用了-O2优化 这样2-3Tree某些inline能够发挥作用,指针操作得以优化,才公平.
(more…)