文章基本信息
- 标题：Splaying a search tree in preorder takes linear time
- 本地全文：下载
- 作者：R. Chaudhuri ; H. Höft
- 期刊名称：International Journal of Mathematics and Mathematical Sciences
- 印刷版ISSN：0161-1712
- 电子版ISSN：1687-0425
- 出版年度：1990
- 卷号：13
- 期号：1
- 页码：186-186
- DOI：10.1155/S0161171290000254
- 出版社：Hindawi Publishing Corporation
- 摘要：
In this paper we prove that if the nodes of an arbitrary n -node binary search tree T are splayed according to the preorder sequence of T then the total time is O ( n ) . This is a special case of the splay tree traversal conjecture of Sleator and Tarjan [1].
