Performance and Test, Spring 2007: Episode 3.1

Lecture Wednesday, February 14, 13:30-15:30, room 2A14

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 notes.

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).