Splaying Preorders and Postorders

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].