A tree is a connected graph with no circuits and a unique simple path between any of it's vertices.
Forest is a graph containing zero or more disjoint trees.
A rooted tree is an acyclic graph, with one vertex designated as root.
A tree with n vertices has n − 1 edges.
A full m-ary tree with i internal vertices contains n = m*i + 1 vertices.
A full m-ary tree with
There are at most mh leaves in an m-ary tree of height h.
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 from DAA
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!
|Frequency (in 1000s)||45||13||12||16||9||5|
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.
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:
Try parsing it, and convince yourself that there is only one possible interpretation of it. That is what the prefix coding buys us.
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.
if T == nil:
if T == nil:
if T == nil:
Prefix form: + ^ + x y 2 / - x 4 3
Postfix form: x y + 2 ^ x 4 - 3 / +
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
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:
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.
Minimum Spanning Trees from DAA