# Splaying preorders and postorders

Caleb C. Levy, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

## Abstract

Let T be a binary search tree of n nodes with root r, left subtree L= left (r), and right subtree R= right (r). The preorder and postorder of T are defined as follows: the preorder and postorder of the empty tree is the empty sequence, and (formula presented), where (formula presented) denotes sequence concatenation. (We will refer to any such sequence as a preorder or a postorder). We prove the following results about the behavior of splaying [21] preorders and postorders: 1.Inserting the nodes of preorder(T) into an empty tree via splaying costs O(n). (Theorem 2.)2.Inserting the nodes of postorder(T) into an empty tree via splaying costs O(n). (Theorem 3.)3.If T has the same keys as T and T is weight-balanced [18] then splaying either preorder(T) or postorder(T) starting from T costs O(n). (Theorem 4.) For 1 and 2, we use 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. The proof of 3 uses the fact that preorders and postorders of balanced search trees do not contain many large “jumps” in symmetric order, and exploits this fact using the dynamic finger theorem [5, 6]. Items 2 and 3 are both novel. Item 1 was originally proved by Chaudhuri and Höft [4]; our proof simplifies theirs. These results provide further evidence in favor of the elusive dynamic optimality conjecture [21].

Original language English (US) Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings Zachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack Springer Verlag 510-522 13 9783030247652 https://doi.org/10.1007/978-3-030-24766-9_37 Published - 2019 16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, CanadaDuration: Aug 5 2019 → Aug 7 2019

### Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 11646 LNCS 0302-9743 1611-3349

### Conference

Conference 16th International Symposium on Algorithms and Data Structures, WADS 2019 Canada Edmonton 8/5/19 → 8/7/19

## All Science Journal Classification (ASJC) codes

• Theoretical Computer Science
• General Computer Science

## Keywords

• Amortized time
• Binary search trees
• Pattern avoidance

## Fingerprint

Dive into the research topics of 'Splaying preorders and postorders'. Together they form a unique fingerprint.