Round 4: Binary Search Trees

In this round and in Round 5: Hashing, we are interested in the abstract data types for dynamic sets and maps. Maps are also called dictionaries in some programming languages. Here “dynamic” means that the set elements, or key-value associations in maps, are inserted, searched for, and removed all the time.

In this round, we will in fact consider ordered sets and ordered maps that

• ​ assume an ordering between the elements, and

• ​ allow efficient searching for the smallest, next smallest, etc elements.

In contrast, the data structures discussed in Round 5: Hashing do not preserve the order of the elements. Instead, they are usually somewhat faster in the core operations of insert, search, and remove.

Contents:

• Introduction: sets and maps
• Binary search trees
• Balancing Binary Search Trees
• AVL Trees
• Extra: Red-Black Trees
• Extra: B-trees

Material in Introduction to Algorithms (Aalto access):

• ​ BSTs: Chapter 12

• ​ Red-black trees: Chapter 13

• ​ AVL trees are not covered in the book but one should use these lecture notes.

Some external links:

• ​ MIT 6.006 OCW video on binary search trees

• ​ MIT 6.006 OCW video on AVL trees

• ​ wikipedia on AVL trees

• ​ A visualization tool for AVL trees

• ​ Algorithms, 4th ed.

  • ​ Section 3.2: binary search trees

  • ​ Section 3.3: red-black trees, removing elements is not covered.