OpenDataStructures(inpseudocode)

← Back to document page

Open Data Structures (in pseudocode)Edition Pat MorinContentsAcknowledgmentsixWhy This Book?xi1 The Need for Efficiency. . . . . . . . . . . . . . . . . . . . . Interfaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Queue, Stack, and Deque Interfaces. . . . . . . The List Interface: Linear Sequences. . . . . . . . . The USet Interface: Unordered Sets. . . . . . . . . . The SSet Interface: Sorted Sets. . . . . . . . . . . . . Mathematical Background. . . . . . . . . . . . . . . . . . . Exponentials and Logarithms. . . . . . . . . . . . . Factorials. . . . . . . . . . . . . . . . . . . . . . . . . Asymptotic Notation. . . . . . . . . . . . . . . . . . Randomization and Probability. . . . . . . . . . . . The Model of Computation. . . . . . . . . . . . . . . . . . . Correctness, Time Complexity, and Space Complexity. . . Code Samples.

Contents 8 ScapegoatTrees 165 8.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding166 8.1.1 Analysis of Correctness and Running-Time . . . . . 170

  Opendatastructures