# Algorithms and Data Structures; Programming

New Beginnings: Week 8
Lecture Notes by Bart Massey

## 2014-08-18: 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

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