## Abstract

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

Original language | English (US) |
---|---|

Title of host publication | Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings |

Editors | Zachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack |

Publisher | Springer Verlag |

Pages | 510-522 |

Number of pages | 13 |

ISBN (Print) | 9783030247652 |

DOIs | |

State | Published - 2019 |

Event | 16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, Canada Duration: Aug 5 2019 → Aug 7 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11646 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 16th International Symposium on Algorithms and Data Structures, WADS 2019 |
---|---|

Country/Territory | Canada |

City | Edmonton |

Period | 8/5/19 → 8/7/19 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science

## Keywords

- Amortized time
- Binary search trees
- Pattern avoidance