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  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  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 ; our proof simplifies theirs. These results provide further evidence in favor of the elusive dynamic optimality conjecture .|
|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|
|Pages:||510 - 522|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Workshop on Algorithms and Data Structures|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.