To refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr18n80`

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.