期刊名称:International Journal of Mathematics and Mathematical Sciences
印刷版ISSN:0161-1712
电子版ISSN:1687-0425
出版年度:1991
卷号:14
期号:3
页码:545-551
DOI:10.1155/S0161171291000741
出版社:Hindawi Publishing Corporation
摘要:
In this paper we prove that if the nodes of an arbitrary n -node binary search tree T are splayed in 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.