Round 4: Binary Search Trees

In this and the next round (Chapter 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 elements, or key-value associations in maps, are inserted, searched for and removed all the time in an online fashion.

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 based on Round 5: Hashing, described in the next round, do not preserve the order of the elements. Instead they are usually somewhat faster on 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

• ​ BSTs: Section 3.2 in Algorithms, 4th ed.

• ​ Red-black trees: Section 3.3 in Algorithms, 4th ed. (removing elements not covered)