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.
  1. Permutations of {a, b, c, d} there are 24, or 4 factorial.

  2. Each one is mapped to one of the 14 bst shapes.

  3. 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.

  4. 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.

  5. 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.

1. I will show the solution to the Kruskal MST example problem data and my answers to questions 1, 2, 3 and 4 during class.
2. 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.