首页
注册
登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请
登录
V2EX 提问指南
广告
V2EX
›
问与答
平衡树还是跳表?
mortonnex
·
2019-02-18 19:40:54 +08:00
· 990 次点击
这是一个创建于 2130 天前的主题,其中的信息可能已经有所发展或是发生改变。
从插入性能和查找性能来讲,跳表都更出色
所以怎么取舍?
取舍
性能
插入
查找
1 条回复
•
2019-02-18 19:56:10 +08:00
1
rayingecho
2019-02-18 19:56:10 +08:00
2
平衡树的最差查找时间是有保证的, 一定是 O(LogN)
跳表每层的的链表是随机生成的, 最差查找时间不稳定, 只能说平均是 O(LogN), 但最差是可以 O(N) 的
但跳表插入更快且对并发更友好, 平衡树需要旋转, overhead 比较大
关于
·
帮助文档
·
博客
·
API
·
FAQ
·
实用小工具
·
1061 人在线
最高记录 6679
·
Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 30ms ·
UTC 22:55
·
PVG 06:55
·
LAX 14:55
·
JFK 17:55
Developed with
CodeLauncher
♥ Do have faith in what you're doing.