Introduction to Algorithms and Data Structures, Episode 6
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
The mandatory assignments should be handed in no later than 13.00 on or before March 30, 2005.
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.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).
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.
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.
|
|
|
|
last updated March 10, 2005Anna Pagh, Andrzej Wąsowski |