SUNY Geneseo Department of Computer Science

Performance of Ordered Binary Trees

{Date}

CSci 141, Fall 2004
Prof. Doug Baldwin

Misc

Lab 12 will be available in lab next Monday

Reading summary: section13.3.5

Proofs are hard to read
Example of, and tips on, reading one
- Lemma re subtrees fully balanced and same height
- Figure out what the theorem is really about, how it fits in with other things
  - Alternative definition of "fully balanced"
- Figure out what the basic idea is and whether it seems intuitively plausible

[Two Views of Fully Balanced Trees]

Once you've got this far the proof is basically just putting the intuitive sense into precise words
Take the time to read sentence by sentence, figure out why you believe each claim made in the proof. Approach the proof as a guide or set of hints on why you should believe the claim, but you have to use this guide to work it out for yourself. Sometimes you'll have to work harder than other times.
Technical proof terminology guides you in what to expect -- e.g., "if and only if," "induction," etc.
Variables or names get introduced into proofs as shorthands for concepts that would otherwise be awkward to say -- e.g., "h_r" is easier to write than "the height of the right subtree." But keep in mind that they do stand for things. Much like variables in a program save you having to write a bulky computation every time you want a value.

Critical idea: "it's fast"
- Search time depends on height
- Search time ranges between Θ(log n) and Θ(n)

Exponential algorithms (the opposite end of the performance spectrum)

Read Sections 15.2.1, 15.2.2