Splaying a search tree in preorder takes linear time (Q1178797)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Splaying a search tree in preorder takes linear time |
scientific article |
Statements
Splaying a search tree in preorder takes linear time (English)
0 references
26 June 1992
0 references
Summary: 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 \textit{D. D. Sleator} and \textit{R. E. Tarjan} [J. Assoc. Comput. Mach. 32, 652-686 (1985)].
0 references
binary search tree
0 references
splay
0 references
preorder traversal
0 references
rotation
0 references
