Splaying preorders and postorders

Caleb C. Levy, Robert E. Tarjan

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

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 languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
EditorsZachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack
PublisherSpringer Verlag
Pages510-522
Number of pages13
ISBN (Print)9783030247652
DOIs
StatePublished - Jan 1 2019
Event16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, Canada
Duration: Aug 5 2019Aug 7 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11646 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Symposium on Algorithms and Data Structures, WADS 2019
CountryCanada
CityEdmonton
Period8/5/198/7/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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.

Cite this