Journal Menu

Abstracting and Indexing
Aims and Scope
Article Processing Charges
Author Guidelines
Bibliographic Information
Contact Information
Editorial Board
Editorial Workflow
Reviewers Acknowledgment
Subscription Information

Abstract
Full-Text PDF
How to Cite this Article

International Journal of Mathematics and Mathematical Sciences 
Volume 14 (1991), Issue 3, Pages 545-551
doi:10.1155/S0161171291000741

Splaying a search tree in preorder takes linear time

R. Chaudhuri and H. Höft

Department of Computer Science, Eastern Michigan University, Ypsilanti 48197, Michigan, USA

Received 31 May 1990; Revised 1 November 1990

Abstract

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.