The Algorithm Design Manual Second Edition

3.4.3

Balanced Search Trees

Random search trees are usually good. But if we get unlucky with our order of

insertion, we can end up with a linear-height tree in the worst case. This worst

case is outside of our direct control, since we must build the tree in response to the

requests given by our potentially nasty user.

What would be better is an insertion/deletion procedure which adjusts the tree a

little after each insertion, keeping it close enough to be balanced so the maximum

height is logarithmic. Sophisticated balanced binary search tree data structures

have been developed that guarantee the height of the tree always to be O(log n).

Therefore, all dictionary operations (insert, delete, query) take O(log n) time each.

Implementations of balanced tree data structures such as red-black trees and splay

trees are discussed in Section

12.1

(page

367

).

From an algorithm design viewpoint, it is important to know that these trees

exist and that they can be used as black boxes to provide an efficient dictionary

implementation. When figuring the costs of dictionary operations for algorithm

analysis, we can assume the worst-case complexities of balanced binary trees to be

a fair measure.

Take-Home Lesson:

Picking the wrong data structure for the job can be

disastrous in terms of performance. Identifying the very best data structure

is usually not as critical, because there can be several choices that perform

similarly.

---

3 . 5

P R I O R I T Y Q U E U E S