论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2015-12-29 09:06 |只看该作者 |倒序浏览

红黑树和平衡二叉树（AVL树）类似，都是在进行插入和删除操作时通过特定旋转保持二叉查找树的平衡，从而获得较高的查找性能。

那么要说插入和调整的性能，确实红黑树高一点，查找性能还是AVL更好啊。
树形结构建立以后，更多的操作不就是查找么。为什么要放弃AVL而选择红黑树呢? STL的map/set也是。

想不明白需求。

博物馆, 二叉树, 平衡

文库|博客

action08

巨富豪门

论坛徽章:: 223

2楼 [报告]

发表于 2015-12-29 09:50 |只看该作者

rbt的好处，实时性强，平衡树性能跟不上

其实rbt在同行的竞争中也是有很大劣势的，例如现在很多互联网行业都流行用nosql，就是用的hash表，
rbt虽然性能比hash差点，但是有排序功能，

不然一切数据结构在hash面前的性能都是渣渣，平衡树基本已经没有价值了

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

w_anthony

家境小康

论坛徽章:: 9

3楼 [报告]

发表于 2015-12-29 09:51 |只看该作者

如果只考虑查找性能，你就算用个排好序的vector进行二分查找，速度和平衡二叉树也差不多，难道map和set要用连续内存去存放吗？
因为没办法确定需求，所以用一个综合性能最好的红黑树来实现，应该是一件容易理解的事情。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

lxyscls

富足长乐

论坛徽章:: 14

4楼 [报告]

发表于 2015-12-29 09:53 |只看该作者

这话谁说的？

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

dorodaloo

富足长乐

论坛徽章:: 6

5楼 [报告]

发表于 2015-12-29 11:26 |只看该作者

w_anthony 发表于 2015-12-29 09:51
因为没办法确定需求，所以用一个综合性能最好的红黑树来实现，应该是一件容易理解的事情。 ...

赞一个!

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

action08

巨富豪门

论坛徽章:: 223

6楼 [报告]

发表于 2015-12-29 12:21 |只看该作者

本帖最后由 action08 于 2015-12-29 12:22 编辑

对的，rbt默认是综合性能最好的数据结构了，也是用在实时系统中的方案，除了hash

vertor有不少应用场景限制，什么应用不准备接受数据插入删除需求的，碰上了性能就会卡死人的，
vertor如果能用上当然好，查找性能只是稍微好过hash（一般的基础hsah算法也就是多两个cpu数学运算指令），

平衡树查找性能也只是稍微好过rbt，
——PS优势不明显，当然要抛弃

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

windoze

版主

论坛徽章:: 44

7楼 [报告]

发表于 2015-12-29 13:01 |只看该作者

红黑树不是严格平衡树，不需要在每次插入删除的时候调整，avl是严格平衡树，每次插入删除的时候都要旋转到平衡状态。
从统计角度来说红黑树的性能要高一点，但查找操作并不能严格保证O(logN)，所以如果一棵树很少修改的话用AVL或许能快一点，但话说回来，如果几乎不修改的话用有序数组+二分查找性能比各种树都要好。