首页    期刊浏览 2025年07月06日 星期日
登录注册

文章基本信息

  • 标题: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
  • 出版年度: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.

国家哲学社会科学文献中心版权所有