Trees (Minimum Spanning and Binary Search)
 Calculating the successful search
peformance for
a BST.
 Doing the binary tree TRAVERSALS
problems.

There are 14 shapes of binary search
trees (bst) with 4 nodes, as well as
many definitions and terms.
 Permutations
of {a, b, c, d} there are 24, or 4 factorial.
 Each one is mapped to one of the
14 bst shapes.
 Draw the 24 arrows from the 24 permutations of the letters
in {a, b, c, d} to the 14 different binary search trees.
The domain permutations and codomain
4 node binary search tree shapes are shown here.
 Here is where the solution will be to check your work
against for mapping a permutation
to a binary search tree. The arrows are:

GREEN arrows for
the best case performance trees which average 2.0 probes per search,
 BLUE arrows for the medium performance
trees which average 2.25 probes per search, and

RED arrows for the slowest, worst
performance trees.
These RED trees are the most unbalanced and the tallest trees.
They average 2.5 probes per search.
 There are
3 different performance levels for 4 node trees (2.0, 2.25 and 2.5
are the average successful search values).
 Which binary search tree shapes with four nodes are BEST
performance? (2.0 average successful search).
Which permutations of {a, b, c, d} create them?
 Which binary search tree shapes with four nodes are AVERAGE
performance? (2.25 average probes for successful search).
 Which binary search tree shapes with four nodes are WORST
(2.5 average) performance?
Which permutations of {a, b, c, d} create them?
Kruskal's handout
and example problem and data.
Kruskal's original, more
readable
version of the above handout.
This will be handed out on Tuesday, November 28th and Wednesday, November
29th, 2000 in class.

I will show the solution to the Kruskal MST example problem
data and my answers to questions 1, 2, 3 and 4 during class.

I will show some hints for question #5 as well. Your lecture notes
for Monday, April 24th are probably enough, but a solution shown
here will be useful supplement to those notes and the messy blackboard
examples.
The Kruskal's algorithm,
homework is due
during the last week of class. It might be a two coin flip homework.
Kruskals algorithm for creating a minimum spanning tree from a
connected, weighted graph is covered on page 440 of our textbook.
Prim's algorithm is discussed on page 435 of our textbook. It is
an alternative approach to creating a MST from a weighted, connected
graph. Focus on Kruskal's algorithm instead.