Skip to main content

Splaying Preorders and Postorders

Author(s): Levy, Caleb C; Tarjan, Robert E

To refer to this page use:
Abstract: Let T be a binary search tree of n nodes with root r, left subtree ๐ฟ=left(๐‘Ÿ) , and right subtree ๐‘…=right(๐‘Ÿ) . The preorder and postorder of T are defined as follows: the preorder and postorder of the empty tree is the empty sequence, and preorder(๐‘‡)postorder(๐‘‡)=(๐‘Ÿ)โŠ•preorder(๐ฟ)โŠ•preorder(๐‘…)=postorder(๐ฟ)โŠ•postorder(๐‘…)โŠ•(๐‘Ÿ), where โŠ• 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 ๐‘‡โ€ฒ has the same keys as T and T is weight-balanced [18] then splaying either preorder(T) or postorder(T) starting from ๐‘‡โ€ฒ 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].
Publication Date: 2019
Citation: Levy, Caleb C., and Robert E. Tarjan. "Splaying Preorders and Postorders." In Workshop on Algorithms and Data Structures (2019): pp. 510-522. doi:10.1007/978-3-030-24766-9_37
DOI: 10.1007/978-3-030-24766-9_37
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 510 - 522
Type of Material: Conference Article
Journal/Proceeding Title: Workshop on Algorithms and Data Structures
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.