Graphs and Trees

By Herbert J. Bernstein
© Copyright 2003 Herbert J. Bernstein

Graphs and Trees

Often we view information in terms of connections between items. Sometimes the connections allow us to specify the relative positions of items, which item comes before which other item. This defines a list of items. Sometimes the connections are more general and non-linear, leading us to consider trees and graphs

A tree is a graph. A graph is a collection of nodes connected to one another by edges. If the edges have a direction, the graph is called a directed graph. If the edges do not have a direction, the graph is called an undirected graph. A path in a graph is a sequence of edges obeying the direction rules of the graph such that the end node of each edge in the path (except for the last edge in the path) is the start node of the next edge in the path. A path is a circuit if the end node of the last edge of the path is the start node of the first edge of the path. A graph is called connected if there is a path from every node to every other node.

One or more values (attribute-values) may be associated with each node of a graph.

One or more values (attribute-values) may be associated with each edge of a graph.

Directed Graphs


         root node
          / | \
         /  |  \
        /   |   \
       a    b    c
      /\    |   /|\
     d  e   f  g h i
    / \  \  \    \  \
In a rooted tree every node except the root is connected to the tree by a single edge from a parent node, and the node itself is called a child of the parent. Each child may be viewed as the root of a sub-tree.

In a binary tree each node as at most two children, and each child has an attribute ("side") with the value "left" or "right".

A trie (from retrieval) is a tree structure to handle searchable lists of character strings. The tree branches where words with common roots differ:

             / \
            l   s
           /   / \
          l   k   s
         / \   \   \
        .   o   .   i
             \       \
              w       g
               \       \
                .       n

A balanced tree has paths from the root to the leaf nodes of similar lengths. A 2-3 tree has interior nodes with 2 or 3 children each and every path from the root to a leaf is the same length.

For more on trees, see: