Performance and Test, Spring 2008: Episode 3.1

Lecture Wednesday, February 13, 9:00-11:00, room 3A14

Subject : Binary Search Trees

Text: RS 12.6—12.7, p. 543 (Program 12.18, the paragraph starting "Fortunately..." with the following one), pp. 548—549, Program 12.22 p. 551, 13.0, 13.3, 13.6 [27pp, 3h30min]

Downloads: Lecture slides. Demos of BST search and of BST insertion.

Prerequisites: binary search, basic data structures (lists, arrays, trees).

Comment: In section 12.8 you should only understand how rotations work (not how insertion on top works). This is why reading p. 543 and arround should suffice. In section 12.9 the only goal is to understand remove, and not the other operations (like select). In order to understand remove, you have to read about partition that uses rotations. Reading the fragments suggested above should be sufficient for this. Finally, section 13.6 gives a general characterization of performance of various trees and tree-like structures. For us only information about 2-3-4 trees is relevant in detail. The rest should be read in an abstract manner (in the same style as the sorting lecture: appreciating the properties without actually understanding how these other data structures work internally).

The tree rotation examples in the lecture were taken from a short interactive tutorial by James Stewart that you might want to try out. There are also a number of 2-3-4 tree applets available on the web, but keep in mind that they do not necessarily perform the different operations the same way as in RS.