# Trees

Introduction to Trees

Tree

A tree is a connected graph with no circuits and a unique simple path between any of it's vertices.

Forest

Forest is a graph containing zero or more disjoint trees.

Rooted Trees

Definition:

A rooted tree is an acyclic graph, with one vertex designated as root.

• Root A vertex is defined in a tree as a root. It is the entry point of a tree.
• Parent A vertex u is said to be a parent of v, if there is a unidirected edge from u to v. A root has no parent
• Child The vertex v defined above is a child of u
• Leaf The last vertices of a tree are leaf. leaf has no children
• Subtree A tree formed by an internal vertex, which is not a root.
• Siblings: vertices with the same parent
• Ancestors: vertices which come along the path when traversing to a vertex from the root. It doesnot include the vertex
• Decendants: Decendants of a vertex are vertices which come along the path when traversing from the vertex to a leaf, excluding the vertex itself.
• M-ary tree A tree with every internal vertices having no more than m children.
• Full m-ary tree A tree with every internal vetrx having exactly m children.
• (Some) molecules
• Org charts
• Computer file systems
Properties of Trees Theorem 2:

A tree with n vertices has n − 1 edges.

Theorem 3:

A full m-ary tree with i internal vertices contains n = m*i + 1 vertices.

Theorem 4:

A full m-ary tree with

1. n vertices has i = (n − 1)/m internal vertices and l = [(m − 1)n + 1]/m leaves,
2. i internal vertices has n = mi + 1 vertices and l = (m − 1)i + 1 leaves,
3. l leaves has n = (ml − 1)/(m − 1) vertices and i = (l − 1)/(m − 1) internal vertices.

Theorem 5:

There are at most mh leaves in an m-ary tree of height h.

Applications of Trees

Trees provide easier location of items. Depending on a certain property, items are stored in a tree data structure for faster retrieval.

Binary Search Trees
Try Binary Search Tree Algorithms
##### 1. Create a Binary Search Tree:
sample values: Randomize

##### 2. Choose an algorithm:
Choose Speed:

Get Get of

Decision Trees
NOT COVERED SPRING 2018
Prefix Codes
Introduction

Prefix codes are coding schemes in which no codeword is a prefix of a different codeword.
This makes decoding easier -- no lookahead. (else and else-if)
It means that we never hit two letters on the same path down the tree!

 a b c d e f 45 13 12 16 9 5 0 101 100 111 1101 1100
Huffman codes

Huffman coding is away of compressing data that consists of characters buy creating short binary representations for the characters that occur most frequently in the data, and using longer representations for characters that occur less frequently.

Constructing a Huffman code

We build a binary tree from the bottom-up, starting with the two least-frequent characters, and building up from there. This ensures the least-frequent characters have the longest codes.

Consider the phrase "Mississippi River". This is 136 bits in 8-bit ASCII encoding.

Here is the Huffman coding for it:

I = 00
S = 01
P = 100
R - 101
M = 1100
V = 1101
E = 1110
_ = 1111

The final string:
110000010100010100100100001111101001101101

Try parsing it, and convince yourself that there is only one possible interpretation of it. That is what the prefix coding buys us.

Game Trees

Trees can be used to analyze certain type of games like tic-tac-toe where there is no element of chance and previous move is known to each player.

The vertices of trees represent position that a game can be in as the game progresses, the edge represent legal moves between these positions

Game trees can be simplified by representing all symmetric positions of game by the same vertex.

However, same position of the game may be represent by different vertices if different sequences of moves lead to this position.

Tree Traversal
NOT COVERED SPRING 2018
Traversal Algorithms

Preorder pseudocode:

``` ```

``````                    preorder(T):
if T == nil:
return
else:
print(T)
preorder(T.left)
preorder(T.right)
``````
``` ```

Inorder pseudocode:

``` ```

``````                    inorder(T):
if T == nil:
return
else:
inorder(T.left)
print(T)
inorder(T.right)
``````
``` ```

Postorder pseudocode:

``` ```

``````                    postorder(T):
if T == nil:
return
else:
postorder(T.left)
postorder(T.right)
print(T)
``````
``` ```

Infix, Prefix, and Postfix Notation Parse tree for ((x + y)^2) + ((x - 4) / 3)

Prefix form: + ^ + x y 2 / - x 4 3
Postfix form: x y + 2 ^ x 4 - 3 / +

Spanning Trees
Introduction

The spanning tree of a graph G is a subgraph of G that is a tree and that contains every vertex of G.

A graph is connected if and only if it has a spanning tree.
We prove this by removing edges from circuits.

This is a way to find a spanning tree in a connected graph (or detect that the graph is unconnected).
The edges used to form that tree are called tree edges.
The edges not used in forming that tree are called back edges (because they lead back to a node already visited). If there are back edges, they show that circuits exist in the graph. And if there are unvisited vertices when DFS is done, then the graph is not connected.
So, DFS can:

• Find spanning trees
• Detect circuits
• Detect if a graph is connected
Backtracking Applications
NOT COVERED SPRING 2018
Depth-First Search in Directed Graphs
NOT COVERED SPRING 2018
Minimum Spanning Trees
Introduction

An electrical grid in an area can be thought of as a weighted graph.

There is a certain cost attached to forming a grid which depends on the area, the distance between two poles and certain other factors.

We can think of all the poles to be vertices and the cost of forming a connection as the weighing factor.

We can form a Minimum Spanning Tree to determine the minimum cost of total connection.

Algorithms for Minimum Spanning Trees
Minimum Spanning Tree Animation:
Algorithms:
Choose Speed:
Fill the input box with sample values:

### Credits

• Images from Wikipedia are linked to the original.