Week 8. Search Trees

Reading 8 Goodrich & Tamassia: Chapter 11

Problem 9.1 Consider the Sorted Binary Tree ADT. Provide pseudo-code for the core operations,

• get
• insert
• delete

The lecture notes in OneNote give the principles for each operation. You should focus on formalising the details.

For each operation, comment on the time complexity and demonstrate that the operation is correct.

Problem 9.2 Consider the preliminary Sorted Binary Tree ADT with the operations you designed above and modify it to maintain balance. Augment your design to ensure the tree is balance. In particular, we want the tree to be an AVL tree, i.e. for every node, the heights of the two subtrees must differ by at most one.

Since a new, empty tree is trivially balanced, it suffices to consider the operations which could possibly create an imbalance. Design new insert and delete operations which maintain balance. Note that you need to store the height of each node.

For each operation, comment on the time complexity and demonstrate that the operation is correct.

Problem 9.3 In the textbook:

• C-11.37
• R-11.7–8
• R-11.9
• R-11.18