CS61B(17): B-Trees(2-3, 2-3-4 Trees)

This is the lecture note of CS61B - Lecture 17.

In today's lecture, we are gonna be primarily concerned with one thing: tree height.

BST Again

The answer is B.

WE can see that performance of operations on spindly trees can be just as bad as a linked list!

Big O is still a useful idea:

Allows us to make simple blanket statements, e.g. can just say “binary search is O(log N)” instead of “binary search is Θ(log N) in the worst case”.
Sometimes don’t know the exact runtime, so use O to give an upper bound.
- Example: Runtime for finding shortest route that goes to all world cities is O(2N)*. There might be a faster way, but nobody knows one yet.
Easier to write proofs for Big O than Big Theta, e.g. finding runtime of mergesort, you can round up the number of items to the next power of 2 (see A level study guide problems for Asymptotics2 lecture). A little beyond the scope of our course

Let’s now turn to understanding the performance of BST operations.

The “height” of a tree determines the worst case runtime to find a node.
- Example: Worst case is contains(s), requires 5 comparisons (height + 1).
The “average depth” determines the average case runtime to find a node.
- Example: Average case is 3.35 comparisons (average depth + 1).

So an important question is What about Real World BSTs? One way to approximate this is to consider randomized BSTs.