网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
noip吧 关注：25,161贴子：642,087
  • 20回复贴，共1页

求问splay为什么双旋会比单旋快？

想来想去还是想不明白


势能分析?


奇怪的地方；看书一直以为书上是乱讲。。。


单旋会退化成O(n)


orz


把最深的点转上去，转好是折过的一条链


我感觉就是单旋会退化，可能一直成链，双旋不会。深度变小


其实我一直不理解为什么要有zig-zig
如果单纯的平衡树，为了降低深度，直接把父亲zig不就好了吗？
然后继续splay 它的父亲


扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！
  • 20回复贴，共1页
分享到: