TREES

Please note that the material on this website is not intended to be exhaustive.
This is intended as a summary and supplementary material to the required textbook.
Outdegree
is the number of edges stemming from a node or vertex in a digraph and is denoted by outdeg (v).
Indegree
is the number of edges entering a node or vertex in a digraph and is denoted by indeg (v).

Free Tree
T is a simple graph where a unique simple path exists from vertex v to vertex w in T.
Rooted Tree
contains a vertex specially designated as the root.   The root is said to be on level 0, while the vertices immediately below the root is said to be on level 1.

Level
of a vertex v is the length of the simple path from the root to v.
Height
of a rooted tree is the maximum level number of the tree.
Hierarchical Definition Tree
is a tree used to illustrate the logical relationships among records in a database.
Huffman Codes
is used to represent characters by variable length bit strings to provide an alternative to the ASCII codes and other fixed length codes.
Optimal Huffman Code Algorithm
constructs an optimal Huffman code from a table of frequency of occurrence of the characters to be represented by replacing each frequency by a character having that frequency.
Input: A sequence of n frequencies, n ³ 2
Output: A rooted tree that defines an optimal Huffman code
Algorithm: procedure huffman (f, n)
    {
       if n == 2 then
          {
             let f1 and f2 denote the frequencies
             let T be as in Figure 9.1.11
             return (T)
          }
       let fi and fj denote the smallest frequencies
       replace fi and fj in the list f by fi + fj
       T' := huffman (f, n – 1)
       replace a vertex in T' labeled fi + fj by the tree shown in Figure 7.1.12 to obtain the tree T
       return (T)
    } huffman
Relations between Vertices
Given a rooted tree T with root n0.   The following are some of the relations between vertices.
  1. parent
  2. ancestor
  3. child
  4. descendant
  5. sibling
  6. leaf or terminal vertex
  7. branch or internal vertex
  8. subtree of T rooted at x is the graph with vertex set V and edge set E, where V is x together with the descendants of x and E = { e | e is an edge on a simple path from x to some vertex in V }.

Acyclic Graph
is a graph with no cycles.
THEOREM:
Given a graph T with n vertices.   Then
  1. T is a tree.
  2. T is connected and acyclic.
  3. T is connected and has n – 1 edges.
  4. T is acyclic and has n – 1 edges.
Spanning Tree
is a subgraph T of a graph G such that T is a tree containing all the vertices of G.
THEOREM:
A graph G has a spanning tree if and only if G is connected.
Breadth–First Search (BFS) for a Spanning Tree Algorithm
finds a spanning tree by processing all the vertices on a given level before moving to the next–higher level.
Input: A connected graph G with ordered vertices v1, v2, ¼, vn
Output: A spanning tree T
Algorithm: procedure bfs (V, E)
    {
       // V = vertices ordered v1, v2, ¼, vn
       // E = edges
       // V' = vertices of spanning tree T
       // E' = edges of spanning tree T
       // v1 is the root of the spanning tree
       // S is an ordered list
       S := (v1)
       V' := {v1}
       E' := Æ
       while true do
          {
             for each x Î S, in order, do
                for each y Î V – V', in order, do
                   if (x, y) is an edge then
                      add edge (x, y) to E' and y to V'
             If no edges were added then
                return (T)
             S := children of S ordered consistently with the original vertex ordering
          }
    } bfs

The BFS can be used to find minimum–length paths in an unweighted graph from a fixed vertex v to all other vertices while the Dijkstra's shortest–path algorithm is for weighted graphs making it a generalization of BFS.

Depth–First Search (DFS) for a Spanning Tree
is an alternative algorithm to BFS
Input: A connected grpah G with ordered vertices v1, v2, ¼, vn
Output: A spanning tree T
Algorithm: procedure dfs (V, E)
    {
       // V' = vertices of spanning tree T
       // E' = edges of spanning tree T
       // vi is the root of the spanning tree
       V' := {v1}
       E' := Æ
       w := v1
       while true do
          {
             while there is an edge (w, v) that when added to T does not create a cycle in T do
                {
                   choose the edge (w, vk) with minimum k that when added to T does not create a cycle in T
                   add (w, vk) to E'
                   add vk to V'
                   w := vk
                }
             if w = v1 then
                return (T)
             w := parent of w in T // backtrack
          }
    } dfs

The objective of the Eight Queens Problem is to place 8 queens on a chess board such that no two queens can cancel each other.

Minimal Spanning Tree
of a weighted graph G is a spanning tree of G with minimum weight.
Prim's Algorithm
finds a minimal spanning tree in a connected, weighted graph.
Input: A connected grpah with vertices 1, 2, ¼, n and start vertex s.   If (i, j) is an edge, then w (i, j) is the weight of (i, j).   If (i, j) is not an edge, then w (i, j) = , a value greater than any actual weight.
Output: The set of edges E with a minimal spanning tree (mst)
Algorithm: procedure prim (w, n, s)
    {
       // v(i) = 1 if vertext i has been added to mst
       // v(i) = 0 if vertex i has not been added to mst
       for i := 1 to n do
          v(i) := 0
       // add start vertex to mst
       v(s) := 1
       // begin with an empty edge set
       E := Æ
       // put n – 1 edges in the minimal spanning tree
       for i := 1 to n – 1 do
          {
             // add edge of minimum weight with one vertex in mst and one vertex not in mst
             min :=
             for j := 1 to n do
                if v(j) = 1 then // j is a vertex in mst
                   for k = 1 to n do
                      if v(k) = 0 and w(j, k) < min then
                         {
;                            add_vertex := k
                            e := (j, k)
                            min := w(j, k)
                         }
          // put vertex and edge in mst
          v(add_vertex) := 1
          E := E {e}
       }
       return (E)
    } prim
Greedy Algorithm
is one that optimizes the choice at each iteration without regard to previous choices.   The Prim's algorithm furnishes such an example.
K–Tree
T is a tree with a vertex v that has maximum outdeg (v) = k.

Binary Tree
is a rooted 2–tree whose children are designated as the left child or the right child.

Full Binary Tree
is a rooted tree whose vertices have either two children or zero children.
THEOREM:
If T is a full binary tree with i internal vertices, then T has i + 1 terminal vertices and 2i + 1 total vertices.
THEOREM:
If a binary tree of height h has t terminal vertices, then lg t £ h.
Binary Search Tree
is a binary tree T in which data is "stored" in the vertices such that data in the left subtree is less than the data in the right subtree.

Depth or Height
of a tree is the maximum number of levels in the tree.

Height
of a vertex or node n is denoted by ht (n).   If a vertex n is a leaf, then ht (n) = 1.   If a vertex n is a non–leaf, then

ht (n) = maximum (ht (leftchild), ht (rightchild)) + 1.

Balance
of a vertex n is denoted by bal (n).   If n is a leaf, then bal (n) = 0.   If n is a non–leaf, then

bal (n) = ht (leftchild) – ht (rightchild).

Balanced Tree
is one where bal (vi) £ |1| for all its vertices vi, otherwise the tree is said to be imbalanced.
Balanced Binary Tree Sort Algorithm
  1. Make the first data the root of the tree.
  2. If the next data is less than the value of the current node, then take the left path, otherwise take the right path, and add a new node to the leaf at the end of the path for the new data.
  3. Recalculate the heights and balances of the nodes along the path from the leaf towards the root until an imbalance is encountered or the root is reached.
  4. Rebalance if an imbalance is encountered and recalculate the heights and balances of the affected nodes.
  5. Go to step 2 and repeat the process until all data have been sorted.

Types of Imbalances
encountered are as follows:

Example of rebalancing a tree sort.

Expressions
consists of two components namely operands and operators.
Operators
indicate the operation to be carried out on operands.

There are two kinds of operators namely unary and binary.

Unary Operators
require one operand to carry out the intended operation
Binary Operators
requires two operands to carry out the intended operation.

Most operators are binary.

There are three ways of representing expressions:

Example: PREFIX: = A / * H + B1 B2 2
INFIX: A = H * ( B1 + B2 ) / 2
POSTFIX: A H B1 B2 + * 2 / =
PREFIX: = M / * P i – 1 / 1 ^ + 1 i t
INFIX: M = ( P * i ) / ( 1 – 1 / ( 1 + i ) ^ t )
POSTFIX: M P i * 1 1 1 i + t ^ / – / =

Regardless of the notation, an expression is represented in a binary tree in the same manner all the time.

ASSIGNMENT

© 2000-07-07 cpsm ; last update 2008-10-29 15:44