平衡树还是跳表?

2019-02-18 19:40:54 +08:00
 mortonnex
从插入性能和查找性能来讲,跳表都更出色

所以怎么取舍?
941 次点击
所在节点    问与答
1 条回复
rayingecho
2019-02-18 19:56:10 +08:00
平衡树的最差查找时间是有保证的, 一定是 O(LogN)
跳表每层的的链表是随机生成的, 最差查找时间不稳定, 只能说平均是 O(LogN), 但最差是可以 O(N) 的
但跳表插入更快且对并发更友好, 平衡树需要旋转, overhead 比较大

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/536260

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX