Algorithms and Data Structures; Programming

New Beginnings: Week 8
Lecture Notes by Bart Massey
Copyright (c) 2014 Bart Massey

2014-08-18: Trees

More About Binary Trees

  • It is possible to represent binary trees as nodes instead of in an array :-). Typically, the links are parent-to-children only. We will use None for missing children.

          class Tree(object):
              def __init__(self, label, left=None, right=None):
                  self.label = label
                  self.left = left
                  self.right = right
    
          t = Tree(1, Tree(2, Tree(4, None, Tree(5))), Tree(3))
    
  • We can recursively traverse these trees:

          def print_inorder(self):
              if self.left != None:
                  self.left.print_inorder()
              print(self.label)
              if self.right != None:
                  self.right.print_inorder()
    
          def print_preorder(self):
              print(self.label)
              if self.left != None:
                  self.left.print_preorder()
              if self.right != None:
                  self.right.print_preorder()
    
          def print_postorder(self):
              if self.left != None:
                  self.left.print_postorder()
              if self.right != None:
                  self.right.print_postorder()
              print(self.label)
    
  • We can use these recursive traversals to compute things, too:

          def sum(self):
              t = 0
              if self.left != None:
                  t += self.left.sum()
              t += self.label
              if self.right != None:
                  t += self.right.sum()
              return t
    

Standard Properties of Trees

  • Things we often compute or maintain as invariants for a tree (including all subtrees):

    • The number of nodes in the tree.

    • The max tree depth.

    • The frontier of the tree: the list of all the leaves in order.

    • The width of the tree: the maximum at any level of the count of nodes at that level.

      • Easiest to start by recursively building the widths at all levels, and then take a maximum afterwards.

Exercise: Find The Frontier

Printing and Reading Trees

  • Let's build code that prints a tree in the following format:

    • For a tree with at least one child, print the label followed by "(", the left child, ",", the right child and ")". If a child is None, print "-" for that child.

    • For a leaf, print the label.

    • Example: 1(2(3,-),4(5, 6))

  • Build code that reads this format and builds the tree. Assume that the labels are non-negative integers.

  • I will build code that "pretty-prints" the tree. This is useful for debugging.

2014-08-20: Search Trees; Prim's Algorithm

Search Trees

  • A search tree is a binary tree with the invariant that the labels of the left subtree of node t are all less than the label of t, and the labels of the right subtree of t are all greater than or equal to the label of t.

  • We can search for a label v in t by traversing the tree:

          def search(self, v):
              if self.label == v:
                  return self
              if v < self.label:
                  if self.left != None:
                       return self.left.search(v)
              else if self.right != None:
                  return self.right.search(v)
              return None
    

    It is straightforward to remove the recursion here.

  • We can insert a label v into t by modifying the search:

          def insert(self, v):
              if self.label == v:
                  return
              if v < self.label:
                  if self.left == None:
                      self.left = Tree(v, None, None)
                  else:
                      self.left.insert(v)
                  return
              if self.right == None:
                  self.right = Tree(v, None, None)
              else:
                  self.right.insert(v)
    
  • Note that search and insertion require time O(d) where d is the depth of the tree. If we can keep the tree shallow, this will give us O(lg n) insertion and deletion.

Balanced Search Tree Insertion

  • Unfortunately, it is easy for a search tree to turn into a list, for example by inserting labels in increasing order.

  • We attach a count n_nodes of the size of the tree to each node by modifying the constructor. [Note: None of this code is debugged at all. You should not necessarily believe it.]

          def __init__(self, label, left, right):
              self.label = label
              self.n_nodes = 1
              self.left = left
              if left != None:
                  self.n_nodes += self.left.n_nodes
              self.right = right
              if right != None:
                  self.n_nodes += self.right.n_nodes
    
  • Now we modify insertion to maintain the count:

          def insert(self, v):
              if self.label == v:
                  return
              self.n_children += 1
              if v < self.label:
                  if self.left == None:
                      self.left = Tree(v, None, None)
                  else:
                      self.left.insert(v)
                  return
              if self.right == None:
                  self.right = Tree(v, None, None)
              else:
                  self.right.insert(v)
    
  • Now we further modify insertion to "rotate" the tree so that insertion below a node always goes toward the side with less children. We will need to make insert() return a new tree, since the root node may have changed.

          def insert(self, v):
              if self.label == v:
                  return self
              self.n_children += 1
              if v < self.label:
                  if self.left == None:
                      self.left = Tree(v, None, None)
                  else:
                      self.left.insert(v)
                  return self.maybe_rotate_right()
              if self.right == None:
                  self.right = Tree(v, None, None)
              else:
                  self.right.insert(v)
              return self.maybe_rotate_left()
    
          def maybe_rotate_right(self, v):
              n_right = 0
              if self.right != None:
                  n_right = self.right.n_nodes
              if self.left.n_nodes <= n_right + 1:
                  return self
              a = self
              b = self.left
              c = self.left.right
              b.right = a
              a.left = c
              return b
    

    and similarly for maybe_rotate_left()

  • Thus the tree is approximately balanced, and thus we get O(lg n) insertion and search.

  • There are many schemes for balancing with less than a full count of nodes at each node. They are complicated and IMHO somewhat pointless most of the time.

    • AVL Trees take advantage of the fact that we really only need counts in the range -1..1 of the difference between children.

    • Red-Black Trees allow one bit of count per node by doing fanciness.

    • Etc, etc

Edge-Weighted Graphs

  • Recall that a graph is a structure (V, E) where V is a set of vertices and E is a set of edges.

  • We will be concerned today with an edge-weighted graph, where there is a function w: E -> N+ that gives the weight of every edge.

  • Obvious place where this pops up: roadmaps

Minimum-Weight Spanning Trees

  • One interesting question: imagine that you have a graph describing all possible roads that could be built to connect a collection of cities.

  • Now: what is the shortest collection of roads that are guaranteed to connect all the cities?

  • We call this thing the "Minimum-Weight Spanning Tree".

    • It will be a tree because cycles should never appear.
  • How to find such a thing?

    • Searching the space of all possible sets of roads is hopelessly inefficient.

Prim's Algorithm

  • Idea: Greedily select the node closest to the currently-connected subtree.

  • Implementation: Construct the tree using a priority queue.

    • Mark all nodes as unattached.
    • Push a root node as the target.
    • Repeatedly:

      • If the queue is empty, we're done.
      • Pop a target node.
      • If the target node is visited, continue.
      • Add the edge implied by the target to the tree.
      • Mark the target as visited.
      • For every unattached neighbor of the target such that the edge from the target to the neighbor is shorter than the current implied edge:

        • Mark the implied edge of the neighbor.
        • Push the neighbor.

2014-08-20: Dijkstra's Algorithm

Dijkstra's Algorithm

  • Idea: Solve the problem greedily. Find all the nodes one hop from the starting vertex, and try them in order of increasing distance. Recurse.

  • If we apply the idea depth-first, we get a slow recursive algorithm.

  • Let's instead try always extending a path from a node that is minimum distance from the origin.

  • Implementation needs three things:

    • A "best previous edge" for each node saying how it was reached.

    • A distance from the origin for each node.

    • A priority queue of nodes sorted by distance.