Handouts

1) Balanced Binary Search Trees

• Videos:
  • Binary Search Trees [41m23s]
  • AVL Trees [38m31s]
  • Red-Black Trees [45m44s]
• Slides:
  • Balanced Binary Search Trees

• Other Material:
  • Binary Search Trees
  • CLRS Chapter 12 - Binary Search Tree
  • Binary Search Tree Visualization (recommended)
  • Binary Search Trees (B. Hasti - University of Wisconsin-Madison)
  • AVL Trees
  • AVL Trees (R. Pattis - University of California)
  • AVL Tree Visualization (recommended)
  • AVL Trees (E. Alexander - University of Wisconsin-Madison)
  • Red-Black Trees
    • CLRS Chapter 13 - Red-Black Trees
    • Red-Black Tree Visualization (recommended)
    • Red-Black Trees (B. Hasti - University of Wisconsin-Madison)
    • An Introduction to Binary Search and Red-Black Trees (TopCoder)
    • A Practical view on Red-Black Trees (Eternally Confuzzled)
    • Left-leaning Red-Black Trees [slides] (R. Sedgewick)

2) Self Adjusting Data Structures

• Videos:
  • Self Adjusting Linked Lists and Amortized Analysis [1h17m2ss]
  • Splay Trees [1h00m39s]
• Slides:
  • Self Adjusting Data Structures

• Other Material:
  • Amortized Analysis
    • Amortized Analysis (my own slides, from 18/19 Algorithms course)
  • Self Organizing Lists
    • Amortized Analysis of Move-to-Front (MTF) List Rearrangement with paid exchanges (MIT)
    • On line algorithms: list update and paging (A. Blum - Carnegie Mellon University)
  • Splay Trees
    • Splay Tree Visualization (D. Galles - University of San Francisco)
    • 1999 Paris Kanellakis Award (given to Sleator and Tarjan for the Splay Tree data structure)
    • Splay Trees Recitation (D. Kozen - Cornell University)
    • Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3), 652-686.
    • Lee, E. K., & Martel, C. U. (2007). When to use splay trees. Software: Practice and Experience, 37(15), 1559-1575.

3) Probabilistic Data Structures

• Slides:
  • Probabilistic Data Structures

• Other Material:
  • Probabilistic Analysis
    • Probabilistic Analysis and Randomized Algorithms (my own slides, from 18/19 Algorithms course)
  • Treaps and Randomized Binary Search Trees
    • Red Black Trees, Heaps and Treaps (T. Veldhuizen - University of Waterloo)
    • Gnarley trees | visualization of algorithms and data structure
    • Wikipedia entry on Treaps
    • Aragon, C. R., & Seidel, R. G. (1989, October). Randomized search trees. In Foundations of Computer Science, 1989., 30th Annual Symposium on (pp. 540-545). IEEE.
    • Seidel, R., & Aragon, C. R. (1996). Randomized search trees. Algorithmica, 16(4-5), 464-497.
    • Martínez, C., & Roura, S. (1998). Randomized binary search trees. Journal of the ACM (JACM), 45(2), 288-323.
  • Skip Lists
    • Skip Lists (slides from C. Kingsford - CMU)
    • Skip Lists Visualization (Y. Lucet - University of British Columbia)
    • Gnarley trees | visualization of algorithms and data structure
    • Skip Lists (Goodrich and Tamassia - DSA Book)
    • Wikipedia entry on Skip Lists
    • Skip Lists: Done Right
    • Pugh, W. (1990). Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668-676.
  • Bloom Filters
    • Wikipedia entry on Bloom Filters
    • Bloom Filters By Example
    • Bloom Filters (with visualization) (Jason Davies)
    • Some possible hash functions: murmur | FNV | Jenkins
    • Broder, A., & Mitzenmacher, M. (2004). Network applications of bloom filters: A survey. Internet mathematics, 1(4), 485-509.
    • Kirsch, A., & Mitzenmacher, M. (2008). Less hashing, same performance: Building a better Bloom filter. Random Structures & Algorithms, 33(2), 187-218.

4) Spatial Data Structures

• Videos:
  • Quadtrees and Variants [1h04m38s]
  • KD-trees and Range Trees [1h13m36s]
• Slides:
  • Quadtrees (selected slides from C. Kingsford - University of Marlyand)
  • 2D Range Search (kd-trees and 2D range trees) (selected slides from C. Kingsford - University of Marlyand)

• Other Material:
  (Note: most of the visualizations are java applets (you meed need an old browser or a tool like appletviewer)
  • Quadtrees
    • PR Quadtree Demo (Brabet & Samet - University of Maryland)
    • PR Bucket Quadtree Demo (Brabet & Samet - University of Maryland)
    • MX Quadtree Demo (Brabet & Samet - University of Maryland)
    • Point Quadtree Demo (Brabet & Samet - University of Maryland)
    • Spatial Index Demos (Brabet & Samet - University of Maryland)
    • MX Quadtree Visualization (Ivan Kuckir)
  • KD-Trees and 2d Range Trees
    • kd-tree Demo (Brabet & Samet - University of Maryland)
    • 2D range tree Demo (Brabet & Samet - University of Maryland)
    • Spatial Index Demos (Brabet & Samet - University of Maryland)
    • KD Trees (adapted from M. Kreveld, one of the authors of " Computational Geometry: Algorithms and Applications." book)
    • Range Trees (adaptef from M. Kreveld, one of the authors of " Computational Geometry: Algorithms and Applications." book)
    • Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509-517.
    • Chazelle, B., & Guibas, L. J. (1986). Fractional cascading: I. A data structuring technique. Algorithmica, 1(1-4), 133-162.
    • Chazelle, B., & Guibas, L. J. (1986). Fractional cascading: II. applications. Algorithmica, 1(1-4), 163-191.

Last Update: