Splay简介常用宏定义与基本参数新建节点初始化.PDF

下载文档 降价啦

4
0
约1.37万字
约 10页
2018-11-27 发布于天津
举报
版权申诉
保障服务

Splay简介常用宏定义与基本参数新建节点初始化.PDF

1、本文档共10页，其中可免费阅读6页，需付费100金币后方可阅读剩余内容。
2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
4、文档侵权举报电话：400-050-0827(电话支持时间：9:00-18:30)。

简介二叉查找树的一种改进数据结构伸展树它的主要特点是不会保证树一直是平衡的但各种操作的平摊时间复杂度是因而从平摊复杂度上看二叉查找树也是一种平衡二叉树另外相比于其他树状数据结构如红黑树树等伸展树的空间要求与编程复杂度要小得多伸展树的出发点是这样的考虑到局部性原理刚被访问的内容下次可能仍会被访问查找次数多的内容可能下一次会被访问为了使整个查找时间更小被查频率高的那些节点应当经常处于靠近树根的位置这样很容易得想到以下这个方案每次查找节点之后对树进行重构把被查找的节点搬移到树根这种自调整形式的二叉查找

Splay简介二叉查找树的一种改进数据结构–伸展树（Splay Tree ）。它的主要特点是不会保证树一直是平衡的，但各种操作的平摊时间复杂度是O(log n) ，因而，从平摊复杂度上看，二叉查找树也是一种平衡二叉树。另外，相比于其他树状数据结构（如红黑树，AV L树等），伸展树的空间要求与编程复杂度要小得多。伸展树的出发点是这样的：考