# Algorithms and Data Structures; Programming

*New Beginnings:* Week 8

*Lecture Notes by Bart Massey*

Copyright (c) 2014 Bart Massey

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

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