Splaying preorders and postorders

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