22 Apr 1996

Outline

Quiz Tuesday (tomorrow), April 22, 30 minutes, open book, one page of notes. Quiz topics:

• 2-3 trees
• tree rotations
• graph searching algorithms
  • breadth-first search
  • depth-first search
  • priority-first search
• minimum-cost spanning trees

Today's topics:

• review for quiz
• bottom-up splaying
• minimum spanning tree / shortest paths example

Bottom-up splaying

• splaying brings a node (in these examples x) to the root of a binary search tree using rotations
• guarantees (magically) that n operations will take O(n log n) time
• based on the following three operations that move x up in the tree:

  Zig-Zag:

         w                w                      x
          \                \                    / \
           y     ===>       x       ===>       w   y
          /                  \            
         x                    y           
  

  (ie, rotate about x-y then about x-w)

  Zig-Zig:

              z              y                x      
             /              / \                \     
            y    ===>      x   z    ===>        y    
           /                                     \ 
          x                                       z
  

  (ie, rotate about y-z then about x-y)

  Zig: (terminal used if path length is odd)

          y                       x
         /            ===>         \
        x                           y
  

  Each of these cases has a mirror image version.

Minimum Spanning Trees (and Shortest Paths)

Do a complete example of the Dijkstra-Prim algorithm for finding a minimum spanning tree.

This algorithm is nearly identical to the shortest path algorithm. The only difference is that the priority of a node on the fringe is the length of the shortest edge connecting that node to somewhere in the tree, rather than the distance of the shortest path from the start to that node. The rule is:

dist(X) = min(dist(X), length(UX edge))

Here's an edge list for an undirected graph with nodes 0 through 6:

node  neighbors  edge weight
 0        1          3
          2          1
          3          6
          4          4
 1        4          1
 2        3          4
          4          2
 3        4          1
          6          5
 4        5          3
          6          2
 5        6          1

  1-0-2
  |/|/
  4-3
  |\|
  5-6

We might as well do both shortest path tree and minimum spanning tree. If you execute the algorithms correctly, you should notice that the minimum-cost spanning tree and the shortest-path tree are slightly different. In particular, in the shortest-path tree, there are edges from 0 to 1 and 4 to 6, whereas in the minimum-cost spanning tree, there are edges from 4 to 1 and 5 to 6.

What could a minimum-cost spanning tree be used for? Suppose we want to connected a bunch of pins on a wire-wrap board together so that they are all electrically equivalent, and we want to use the least amount of wire possible. A minimum-cost spanning tree gives us the solution.

Note: the Dijkstra algrorithm for shortest paths works even if you have directed edges (but all lengths are positive). However, the spanning tree algorithm DOESN'T work. If you want, you can try to figure out where the proof breaks down.

Here's an example (A is the start)

              3
           A---->B
           |     |
          4|     |3
           v     v
           C---->D
              1