# Introduction to Algorithms and Data Structures, Episode 6

## Lecture, March 11

Subject : Binary Search Trees: successors, insertion, and deletion. The height of a search tree. Balanced Search Trees. AVL trees. The height of an AVL tree. Insertion, deletion, and rebalancing. Time usage of operations on AVL trees.

Text : Refresh your memories of CLRS 12.1–2 if needed. CLRS 12.3; sections 18.3–4 of the handout. A solution of a relevant recurrence relation is found in section 8.6.2 of the handout (together with the average-case performance analysis of QuickSort). Fibonacci numbers are discussed in CLRS 3.2. Optionally, the interested student is invited to study CLRS 12.4.

Prerequisites : Recursion. Binary search trees. In-order traversal of a binary tree.

Comments : Apart from the general idea of balanced search trees, the episode contains extensively gory details of AVL tree rotations and rebalancing. It is important to understand how and why this works in some detail (in this regard, this Episode's programming assignments are particularly highly recommended). On one hand, it is probably overkill to always remember all details off the top of your head. On the other hand, it is a good idea to feel sufficiently confident with the details so that you can perform the necessary operations by hand for individual trees: it tends to be a good exam question.

Time : Friday, March 11, 9:00–12:00, Room 2A12

Tutorial : 13:00–16:00, Room 3A14

## Assignments

• CLRS exercises 12.1-1, 12.1-2, page 256, 12.2-9, page 260, 12.3-1 page 264.
• More exercises, including some mandatory ones.

The mandatory assignments should be handed in no later than 13.00 on or before March 30, 2005.

## Programming Assignments

### Assignment 6.1

1. Add the public field parent to the class BinaryTree from Programming Assignment 5.2 (the parent of the root is nil). Assume that your binary tree is a binary search tree when you take labels into account.
2. Implement the methods BinaryTree minTree(BinaryTree t) finding the element with the minimal label in a binary search tree t, and BinaryTree successor(BinaryTree t) calculating the successor node of t (see CLRS 12.2).
3. Observe that t0=minTree(t), t1=successor(t0), t2=successor(t1),... should give the same result as the method InOrder(t) from Programming Assignment 6.2(i). What works faster? You can use CompleteBinaryTree(int h) from Programming Assignment 6.2(h) for experimentation.

### Assignment 6.2

Implement AVL trees (adding public int balance to BinaryTree) complete with methods for insertion, deletion, and the two variants of rebalancing after these two operations.