平衡树：选择AVL、红黑树还是SBT？解决思路
平衡树：选择AVL、红黑树还是SBT？
我现在需要一棵平衡树保存一些数据，初步考虑AVL、红黑树、Treap、SBT。对其性能了解少，所以进行了一些简单测试以便获得一些初步印象。但测试下来，发现同一种树，不同的实现不同的代码造成的性能差异较大（目前测试用了他人的代码）。而现在也没有大量时间完善每种树的代码来测试，所以打算听下大伙的看法。选定合适的树后，再花时间写和完善代码，这样节省一些时间。
这里明确，需要的是一棵平衡二叉树。暂不考虑哈希。
我先谈下我对这几种树的粗略看法：
红黑树：查找比AVL稍差，但插入删除稍好（平衡操作最多旋转3次），但它比AVL复杂，插入删除要调用代码多，效率实际会打一点折扣。
AVL：查找性能好（因为高度平衡），插入删除稍差（平衡操作旋转次数多）
SBT（size balanced tree）：和AVL一样是高度平衡的树，但实现容易，一些评价说SBT可以用来取代AVL、红黑树。查找性能好（高度平衡），插入删除除了和AVL一样旋转，还要维护整棵树的size，所以我觉得其比AVL可能要差些。
目前我比较倾向于AVL。请指点。
------解决方案--------------------
帮顶个，最近正在看红黑树，感觉那个性能还行，就是负责点，要旋转，其他的不懂。
------解决方案--------------------
参考：http://wangdei.javaeye.com/blog/236157
------解决方案--------------------
由于AVL树种类较少所以比红黑树实际上更容易实现.而且ALV树在旋转插入所需要的复杂度为0(1),而红
黑树则需要的复杂度为0(lgn).
实际上插入AVL树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的,因为红黑树对已经处理好的数据重新平衡减少了不心要的操作.另外一方面,如果是一种非寻常的插入系列比较常见(比如,插入密钥系列),则AVL树比较快,因为它的严格的平衡规则将会减少树的高度.
Splay树可能比红黑树和AVL树还要快这也取决于你所访问的数据分布,如果你用哈希表来代替一棵树,则
将所以的树还要快.
------解决方案--------------------
听说红黑树的统计效率是最好的，像stl,linux中的搜索都是使用它的，LZ可以考虑考虑
------解决方案--------------------
可以参考这篇文章
http://www.cnblogs.com/abatei/archive/2008/12/17/1356565.html
------解决方案--------------------
红黑树好
------解决方案--------------------
------解决方案--------------------
我对红黑树有好感:)我会用红黑树
不过没有那么麻烦,你在另一帖的方法可行,
如楼上所说将链表换成数组,
查找的方法有很多，因为时间排序,二分即可
或者建立两个索引,如果不存在数据量的问题,仍然可行
------解决方案--------------------
------解决方案--------------------
如果只追求效率的话,用2组数据可以么?
一组按照key排序,一组按照time排序,添加的时候分别向两个组里添加,删除的时候先删key,然后根据key读出time,再删除time组里的
lz可以看看.net里面的SortedDictionary
这样的话插入,删除,查找都是log(n)
------解决方案--------------------
就复杂度来说都是一样的，差异仅仅是对不同类型数据分布带来的影响。
当然通常来说红黑树的插入删除性能比较好，然后查询性能一般（平衡条件不是很严格）。
也确实AVL树的每次插入新元素的时候，需要对整个插入的路径做一次校验，来更新平衡性最后达到平衡。所以插入删除性能稍差。
感觉对于你这样的数量级体现不出什么本质的差异，用什么都可以，但既然stl::map那些关联性的容器都用红黑树，推荐用下红黑树。
这里有一些完整的红黑树和AVL树的实现：
http://blog.csdn.net/hhygcy/category/486845.aspx
------解决方案--------------------
FreeBSD的sys/tree.h
有写好了的红黑树与伸展树，没必要自己实现。
我现在需要一棵平衡树保存一些数据，初步考虑AVL、红黑树、Treap、SBT。对其性能了解少，所以进行了一些简单测试以便获得一些初步印象。但测试下来，发现同一种树，不同的实现不同的代码造成的性能差异较大（目前测试用了他人的代码）。而现在也没有大量时间完善每种树的代码来测试，所以打算听下大伙的看法。选定合适的树后，再花时间写和完善代码，这样节省一些时间。
这里明确，需要的是一棵平衡二叉树。暂不考虑哈希。
我先谈下我对这几种树的粗略看法：
红黑树：查找比AVL稍差，但插入删除稍好（平衡操作最多旋转3次），但它比AVL复杂，插入删除要调用代码多，效率实际会打一点折扣。
AVL：查找性能好（因为高度平衡），插入删除稍差（平衡操作旋转次数多）
SBT（size balanced tree）：和AVL一样是高度平衡的树，但实现容易，一些评价说SBT可以用来取代AVL、红黑树。查找性能好（高度平衡），插入删除除了和AVL一样旋转，还要维护整棵树的size，所以我觉得其比AVL可能要差些。
目前我比较倾向于AVL。请指点。
------解决方案--------------------
帮顶个，最近正在看红黑树，感觉那个性能还行，就是负责点，要旋转，其他的不懂。
------解决方案--------------------
参考：http://wangdei.javaeye.com/blog/236157
------解决方案--------------------
由于AVL树种类较少所以比红黑树实际上更容易实现.而且ALV树在旋转插入所需要的复杂度为0(1),而红
黑树则需要的复杂度为0(lgn).
实际上插入AVL树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的,因为红黑树对已经处理好的数据重新平衡减少了不心要的操作.另外一方面,如果是一种非寻常的插入系列比较常见(比如,插入密钥系列),则AVL树比较快,因为它的严格的平衡规则将会减少树的高度.
Splay树可能比红黑树和AVL树还要快这也取决于你所访问的数据分布,如果你用哈希表来代替一棵树,则
将所以的树还要快.
------解决方案--------------------
听说红黑树的统计效率是最好的，像stl,linux中的搜索都是使用它的，LZ可以考虑考虑
------解决方案--------------------
可以参考这篇文章
http://www.cnblogs.com/abatei/archive/2008/12/17/1356565.html
------解决方案--------------------
红黑树好
------解决方案--------------------
------解决方案--------------------
我对红黑树有好感:)我会用红黑树
不过没有那么麻烦,你在另一帖的方法可行,
如楼上所说将链表换成数组,
查找的方法有很多，因为时间排序,二分即可
或者建立两个索引,如果不存在数据量的问题,仍然可行
------解决方案--------------------
------解决方案--------------------
如果只追求效率的话,用2组数据可以么?
一组按照key排序,一组按照time排序,添加的时候分别向两个组里添加,删除的时候先删key,然后根据key读出time,再删除time组里的
lz可以看看.net里面的SortedDictionary
这样的话插入,删除,查找都是log(n)
------解决方案--------------------
就复杂度来说都是一样的，差异仅仅是对不同类型数据分布带来的影响。
当然通常来说红黑树的插入删除性能比较好，然后查询性能一般（平衡条件不是很严格）。
也确实AVL树的每次插入新元素的时候，需要对整个插入的路径做一次校验，来更新平衡性最后达到平衡。所以插入删除性能稍差。
感觉对于你这样的数量级体现不出什么本质的差异，用什么都可以，但既然stl::map那些关联性的容器都用红黑树，推荐用下红黑树。
这里有一些完整的红黑树和AVL树的实现：
http://blog.csdn.net/hhygcy/category/486845.aspx
------解决方案--------------------
FreeBSD的sys/tree.h
有写好了的红黑树与伸展树，没必要自己实现。