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 (also called dictionaries in some languages). Here “dynamic” means that the keys, 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 keys, and

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

In contrast, the data structures described in the next round do not preserve the order of the keys but are usually somewhat faster on the “basic” 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: Sections 12.1–12.3

• ​ Red-black trees: Sections 13.1–13.4

• ​ AVL trees are not covered in Introduction to Algorithms (Aalto access) 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 keys not covered)