32
/ \
16 45
/ \
5 38
Use the Binary Search Tree insertion algorithm to insert the keys
1, 2, 3, 4, 5, 6, 7 into a initially empty BST (in that order!).
What is the height of the resulting tree?
What is the (exact) average number of nodes that must be
visited to find a value that is in this tree assuming that all
values 1-7 are equally likely to be searched for? (Remember: An
average case analysis is performed by adding up the costs for
each possible case, then dividing by the number of cases.)
In general, if I add the numbers 1 through n to a binary tree
(in order), what is the average number of nodes that will be
accessed during the find operation in the resulting tree?
Draw the binary search tree with the smallest possible height
containing the keys 1, 2, 3, 4, 5, 6, 7.
remove(4)
is called.Here is an interface describing a simple Dictionary ADT:
public interface Dictionary<K, E> {
/** Reinitialize dictionary */
public void clear();
/**
* Insert a record
*
* @param k The key for the record being inserted.
* @param e The record being inserted.
*/
public void insert(K key, E elem);
/**
* Remove and return a record.
*
* @param k The key of the record to be removed.
* @return A maching record. Return null if no record
* with key "k" exists.
*/
public E remove(K key);
/**
* @return A record matching "k" (null if none exists).
* @param k The key of the record to find.
*/
public E find(K key);
/** Return The number of records in the dictionary. */
public int size();
}
insert | remove | find | |
---|---|---|---|
Sorted Array | |||
BST | |||
Balanced BST |