pith. sign in

arxiv: 1907.06309 · v1 · pith:LBUPXEYHnew · submitted 2019-07-15 · 💻 cs.DS

Splaying Preorders and Postorders

Caleb C. Levy , Robert E. Tarjan This is my paper

Pith reviewed 2026-05-24 21:35 UTC · model grok-4.3

classification 💻 cs.DS
keywords splay treesbinary search treespreorderpostorderpattern avoidancedynamic optimalityweight-balanced treesdynamic finger theorem
0
0 comments X

The pith

Splaying the preorder or postorder sequence of a binary search tree inserts its keys in linear time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that splaying a preorder or postorder traversal sequence into an initially empty binary search tree costs only linear time overall. It relies on the fact that these traversal orders avoid certain permutation patterns, which restricts how the inserted nodes can sit relative to uninserted ones and allows a simple potential function to bound the total splaying cost. A second theorem shows the same linear bound holds when the sequence is splayed starting from any other tree on the same keys, provided the source tree is weight-balanced; here the argument uses the dynamic finger theorem after proving that balanced trees produce preorders and postorders with few large symmetric-order jumps. Both results are offered as further support for the dynamic optimality conjecture for splay trees.

Core claim

Inserting keys into an empty binary search tree via splaying in the order of either T's preorder or T's postorder takes linear time. The proof exploits that preorders avoid subsequences order-isomorphic to (2,3,1) and postorders avoid (3,1,2), which imposes insertion constraints that a potential counting inserted nodes on paths to uninserted nodes can exploit. When T is weight-balanced, the same linear bound holds even if splaying begins from an arbitrary tree T' on the same keys, because such traversals contain few large jumps and the dynamic finger theorem applies.

What carries the argument

Pattern avoidance in preorders and postorders, which constrains the relative positions of inserted and uninserted keys and enables a potential function that counts inserted nodes lying on access paths to uninserted nodes; the dynamic finger theorem is used in the weight-balanced case.

If this is right

  • Splay trees achieve linear cost on the natural traversal orders of any binary search tree.
  • The same linear bound holds when the starting tree is arbitrary but the source tree is weight-balanced.
  • The potential-function technique based on pattern avoidance may apply to other classes of pattern-avoiding insertion sequences.
  • These linear-time results supply additional evidence toward the dynamic optimality conjecture.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the pattern-avoidance approach generalizes, splay trees may run in linear time on additional families of access sequences that arise from tree traversals.
  • The limited-jump property of balanced preorders and postorders could be used to analyze splay performance under other access models that involve symmetric-order locality.

Load-bearing premise

Preorders and postorders avoid the patterns (2,3,1) and (3,1,2) respectively, which imposes strong limits on how inserted nodes can interleave with uninserted ones during splaying.

What would settle it

An explicit preorder or postorder sequence of a weight-balanced tree whose total splaying cost, either from an empty tree or from another tree, exceeds linear in the number of keys.

Figures

Figures reproduced from arXiv: 1907.06309 by Caleb C. Levy, Robert E. Tarjan.

Figure 1
Figure 1. Figure 1: Rotation at node x with parent y, and reversing the effect by rotating at y. Rotation Binary search trees are the canonical data structure for maintaining an ordered set of elements, and are building blocks in countless algorithms. Perhaps the most attractive feature of binary search trees is that the number of comparisons required to find an item in an n-node binary search tree is O(log n), provided that … view at source ↗
Figure 2
Figure 2. Figure 2: A splaying step at node x. Symmetric variants not shown. Triangles denote subtrees. The algorithm begins with a binary search for a key in the tree. Let x be the node returned by this search. If x is not null then the algorithm repeat￾edly applies a “splay step” until x becomes the root. A splay step applies a certain series of rotations based on the relationship between x, its parent, and its grandparent,… view at source ↗
Figure 3
Figure 3. Figure 3: Possible locations for the next sub-root [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Possible locations for the next sub-root [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
read the original abstract

Let $T$ be a binary search tree. We prove two results about the behavior of the Splay algorithm (Sleator and Tarjan 1985). Our first result is that inserting keys into an empty binary search tree via splaying in the order of either $T$'s preorder or $T$'s postorder takes linear time. Our proof uses the fact that preorders and postorders are pattern-avoiding: i.e. they contain no subsequences that are order-isomorphic to $(2,3,1)$ and $(3,1,2)$, respectively. Pattern-avoidance implies certain constraints on the manner in which items are inserted. We exploit this structure with a simple potential function that counts inserted nodes lying on access paths to uninserted nodes. Our methods can likely be extended to permutations that avoid more general patterns. Second, if $T'$ is any other binary search tree with the same keys as $T$ and $T$ is weight-balanced (Nievergelt and Reingold 1973), then splaying $T$'s preorder sequence or $T$'s postorder sequence starting from $T'$ takes linear time. To prove this, we demonstrate that preorders and postorders of balanced search trees do not contain many large "jumps" in symmetric order, and exploit this fact by using the dynamic finger theorem (Cole et al. 2000). Both of our results provide further evidence in favor of the elusive "dynamic optimality conjecture."

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves two results on splay trees. First, inserting the keys of a BST T into an initially empty tree by splaying in the preorder (resp. postorder) sequence of T takes O(n) time; the argument uses the classical 231-avoidance (resp. 312-avoidance) of these sequences together with a potential function that counts already-inserted nodes lying on paths to uninserted nodes. Second, when T is weight-balanced, the same sequences can be splayed starting from an arbitrary initial tree T' on the same keys and the total cost remains linear; this follows from showing that the sequences contain only O(n) large symmetric-order jumps and invoking the dynamic finger theorem of Cole et al. (2000). Both results are offered as further evidence for the dynamic-optimality conjecture.

Significance. If the claims hold, the work supplies two infinite families of access sequences for which splay trees are dynamically optimal, thereby strengthening the empirical and theoretical case for the conjecture. The proofs are self-contained once the cited external results (pattern-avoidance facts and the dynamic finger theorem) are granted, and the potential-function argument is a natural fit for the recursive structure of preorder and postorder traversals. The observation that the same techniques may extend to other pattern-avoiding permutations is noted but left unexplored.

minor comments (3)
  1. §2, paragraph after Definition 2.1: the sentence 'Pattern-avoidance implies certain constraints…' is vague; a one-sentence reminder of the precise insertion-order constraints used later would improve readability.
  2. §4, proof of Theorem 4.2: the bound on the number of large jumps is stated as O(n) but the constant hidden by the weight-balance assumption is not made explicit; adding a short calculation relating subtree-size ratios to jump length would clarify the application of the dynamic finger theorem.
  3. The paper cites Sleator-Tarjan 1985 and Cole et al. 2000 but does not include a brief comparison paragraph with the earlier 'sequential access' and 'deque' results; such a paragraph would help situate the new linear-time families.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, accurate summary of our results, and recommendation to accept. We appreciate the recognition that the work supplies infinite families of access sequences for which splay trees are dynamically optimal.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external classical results

full rationale

The paper establishes linear-time splaying for preorder/postorder sequences using pattern-avoidance (classical for BST traversals), a potential counting inserted nodes on paths, and the dynamic finger theorem (Cole et al. 2000). These inputs are independent of the present claims, not fitted parameters, and not justified via self-citation chains. The weight-balanced case reduces to showing O(n) jumps via balanced subtree sizes, which follows directly from the tree definition without redefining the target bound. No step equates a prediction to its input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central claims rest on standard BST properties, the pattern-avoidance facts for traversals, and the cited dynamic finger theorem. No free parameters or new entities introduced.

axioms (3)
  • standard math Binary search trees maintain symmetric order during insertions and splaying
    Fundamental to BST definition and splaying operations.
  • domain assumption Preorder and postorder permutations avoid specific patterns (2,3,1) and (3,1,2)
    Stated in abstract as fact used to constrain insertions and enable the potential function argument.
  • standard math The dynamic finger theorem applies to bound splay costs
    Cited from Cole et al. 2000 and used for the weight-balanced starting tree case.

pith-pipeline@v0.9.0 · 5797 in / 1611 out tokens · 31197 ms · 2026-05-24T21:35:25.180926+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    Adel’son-Vel’skii and E

    G. Adel’son-Vel’skii and E. Landis. An algorithm for the organization of information. Sov. Math. Dokl., 3:1259–1262, 1962

    work page 1962

  2. [2]

    Akra and L

    M. Akra and L. Bazzi. On the solution of linear recurrence equations. Computational Optimization and Applications, 10(2):195–210, 1998

    work page 1998

  3. [3]

    Chalermsook, M

    P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, and T. Saranurak. Pattern-avoiding access in binary search trees. InFOCS, pages 410–423, 2015

    work page 2015

  4. [4]

    Chaudhuri andH

    R. Chaudhuri andH. HÃűft. Splayinga search treein preorder takeslinear time. ACM SIGACT News, 24(2):88–93, 1993

    work page 1993

  5. [5]

    R. Cole. On the dynamic finger conjecture for splay trees. part ii: the proof. SICOMP, 30(1):44–85, 2000

    work page 2000

  6. [6]

    R. Cole, B. Mishra, J. Schmidt, and A. Siegel. On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sortinglogn-Block Sequences. SICOMP, 30(1):1–43, 2000. 13

    work page 2000

  7. [7]

    Demaine, D

    E. Demaine, D. Harmon, J. Iacono, D. Kane, and M. PÇŐtraŧcu. The geometry of binary search trees. InSODA, pages 496–505, 2009

    work page 2009

  8. [8]

    K.Fox.Upperboundsformaximallygreedybinarysearchtrees.In WADS, pages 411–422, 2011

    work page 2011

  9. [9]

    Goyal and M

    N. Goyal and M. Gupta. Better analysis of binary search tree on decom- posable sequences.Theoretical Computer Science, 2019

    work page 2019

  10. [10]

    Guibas and R

    L. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In FOCS, pages 8–21, 1978

    work page 1978

  11. [11]

    Haeupler, S

    B. Haeupler, S. Sen, and R. Tarjan. Rank-balanced trees.TALG, 11(4), 2015

    work page 2015

  12. [12]

    Iacono and S

    J. Iacono and S. Langerman. Weighted dynamic finger in binary search trees. InSODA, pages 672–691, 2016

    work page 2016

  13. [13]

    L. Kozma. Binary Search Trees, Rectangles and Patterns. PhD thesis, Saarland University, 2016

    work page 2016

  14. [14]

    Kujala and T

    J. Kujala and T. Elomaa. The cost of offline binary search tree algorithms and the complexity of the request sequence.TCS, 393:231–239, 2008

    work page 2008

  15. [15]

    Levy and R

    C. Levy and R. Tarjan. A new path from splay to dynamic optimality. In SODA, pages 1311–1330, 2019

    work page 2019

  16. [16]

    J. Lucas. Canonical Forms for Competitive Binary Search Tree Algo- rithms. Technical report, Rutgers University, 1988

    work page 1988

  17. [17]

    I. Munro. On the competitiveness of linear search. InESA, pages 338–345, 2000

    work page 2000

  18. [18]

    Nievergelt and E

    J. Nievergelt and E. Reingold. Binary search trees of bounded balance. SICOMP, 2(1):33–43, 1973

    work page 1973

  19. [19]

    S. Pettie. Applications of forbidden 0-1 matrices to search tree and path compression-based data structures. InSODA, pages 1457–1467, 2010

    work page 2010

  20. [20]

    S. Pettie. Splay trees, davenport-schinzel sequences, and the deque con- jecture. InSODA, pages 1115–1124, 2008

    work page 2008

  21. [21]

    Sleator and R

    D. Sleator and R. Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652–686, 1985

    work page 1985

  22. [22]

    R. Sundar. On the deque conjecture for the splay algorithm.Combinator- ica, 12(1):95–124, 1992

    work page 1992

  23. [23]

    R. Tarjan. Amortized computational complexity.SIAM Journal on Alge- braic and Discrete Methods, 6(2):306–318, 1985

    work page 1985

  24. [24]

    R. Tarjan. Sequential access in splay trees takes linear time.Combinator- ica, 5(4):367–378, 1985

    work page 1985

  25. [25]

    R. Wilber. Lower bounds for accessing binary search trees with rotations. SICOMP, 18(1):56–67, 1989. 14

    work page 1989