A Survey of Tree Representations

ABSTRACT: In this report, we classify trees, then classify tree representations, then give a survey of tree representations. We also discuss operations on a tree. The purpose of this report is to provide economy of thought, provide consistent terminology, and assist in identifying "convenient" representations of trees to use in applications.








Introduction

The word "tree" is often encountered in computer data structures theory and in graph theory. We use definitions and theorems from graph theory. But our focus is on trees commonly used as computer data structures.

Definition.
Theorems.






Classification of Trees

Knuth's Classification

Knuth [K] said that there are "three fundamental classes of trees," free, oriented, and ordered, defined as follows.

Definition.
In addition, Knuth says each of these three fundamental classes can be "labelled" or "unlabelled".

Definition.

So we can partition free, oriented, and ordered trees by whether they are labelled or unlabelled. Knuth says that the most important trees in computer data structures are ordered trees.

Table 1: Examples for Knuth's Classification of Trees.
Free Oriented Ordered
Unlabelled

counted by OEIS A000055


counted by OEIS A000081


counted by OEIS A000108
Counted by Catalan numbers C(n)=(2n)!/((n+1)!n!)
Labelled

Counted by OEIS A000272
Counted by n^(n-2)


Counted by OEIS A000169
Counted by n^(n-1)


Counted by OEIS A001813
Counted by quadrupleFactorialNumbers(n-1) = (2(n-1))!/((n-1)!)
Theorem.




Beyond the above classification, many trees in practice are equipped with additional structure, which we identify next.





Trees With Additional Structure

Number of Children

Consider ordered trees. We can restrict the number of children of each node.

Definition.

Example.
binary tree:           Strict binary tree:         Complete binary tree:      Perfect Binary Tree:          Binary tree with omitted children:
       x                        x                           x                         x                          x
     /   \                     /  \                        / \                       /  \                       / \
    /     \                   /    \                      /   \                     /    \                     /   \
   x       x                 x      x                    x     x                   x       x                  x     x
  / \      |                / \                         / \   / \                 / \     / \                / \     \
 x   x     x               x   x                       x   x  x  x               x   x   x   x              x   x     x
     |                        / \                     / \  |                    / \ / \ / \ / \                /     / 
     x                       x   x                   x   x x                    x x x x x x x x               x     x 

Theorems. Consider a k-ary tree on n nodes.





Depth

More structure can be given by bounding the length of the path from the root to the leaves.

Definition.
Example.
Tree with height 3:

      x     <---depth 0
    / | \
   x  x  x  <---depth 1
  / \    | 
 x   x   x  <---depth 2
  
Theorems.








A Survey of Tree Representations




Knuth [K] gave examples of three types of tree representations: linked, sequence, and tree. In addition, there may be some other representations. A classification of types of tree representations:





Below is a table of tree representations, classified by type of tree and by type of representation.


Table 1: Classification of Trees.
Free Oriented Ordered Extra structure
Unlabelled
Labelled
  • Many unlabelled encodings above can be extended to labelled





Unlabelled Free Trees

Linked Neighbors


Each node has pointer to each neighbor.

back to table






Unlabelled Oriented Trees

Linked Child-Parent


Each node has pointer to each child or its parent. If both pointers are present, then one node is distinguised as root.

back to table






Unlabelled Ordered Trees

Balanced Parentheses


Traverse tree depth-first, pre-order. When first visit a subtree, print '(' (or '1') and when leaving that subtree, print ')' (or '0'). Alternatively, label edges with '(' on left and ')' on right, walk around tree

Theorem

[KM]
[Re] for binary version

back to table

Branching Sequence ("Arity List")

    *
   / \
  *   *
 /\  /|\
* * * * *
encoding depth first: 2 2 0 0 3 0 0 0
encoding breadth first: 2 2 3 0 0 0 0 0

Label each node with its arity, traverse (depth or breadth first) to accumulate sequence of arities

Remark.


[Re] for binary version

back to table

Depth Sequence

    *
   /|\
  * * *
 /\
*  *
depth list: 0 1 2 2 1 1 
   *
   |
   *
   |
   *
  /\
 *  *
depth list: 0 1 2 3 4 4

Label each node with its depth, traverse depth-first pre-order to accumulate sequence of depths.

Remark.

[RR] binary version

back to table

Navigation Sequence

The navigation sequence ("generalized index") of a tree node is a list indices of children when traversing from the root to that node.

Notation: For tree T, let T[i1,i2,...,in] denote the node at navigation sequence i1,i2,...,in, where the level is n.


Storing every node's navigation sequence is a tree representation, they can be ordered in any way.

back to table

Left-child right-sibling


rotated:

Delete all edges except for the first left child. Draw edges between siblings.

Theorem.

[K]

back to table

Leaves of binary tree




ref OEIS A000081, [CG]

back to table






Additional Structure

binary tree with omitted children

Zak's sequence

Label nodes '1' and extend all possible leaves and label them '0', traverse depth-first preorder accumulating string, drop last 0.

Theorem.

Remark.

[Za], [KM]

back to table

children pattern sequence
     11
    /  \
   01  01
    \    \
    00   10
         /
        11
       /  \
      00   00

Encoding: 11 01 00 01 10 11 00 00
label nodes of binary tree: 00=leaf, 01=only right child, 10=only left child, 11=two children, traverse in preorder

Theorem

[KM]

back to table

Level-order representation

Label all nodes 1's and extend all external nodes with children labelled 0. Traverse breadth-first accumulating encoding.

Theorem Consider a k-ary tree. Let the nodes be ordered in breadth-first left-to-right order, and consider the "level-order sequence" as the binary encoding above.

Remark.

[De]

back to table

Rotation based

[KM]

back to table






binary trees

Strict binary tree as compressed branching sequence (and compressed balanced parentheses)
    0
   / \
  1   0
      /\
     1  1

encoding: 01011

For a strict binary tree, label internal nodes with 0's and external nodes with 1's. Then traverse depth first pre-order accumulating encoding.

Theorem.

[Ko]

back to table

Binary pixel

Store array of pixel values.

back to table






Labelled Free Trees

Prufer Code


Remove the leaf with the smallest label, and append the label of the node it was removed from. Continue until 2 vertices are left.

The Prufer code encodes labelled free trees as n-2 digit sequence from {1,2,...,n}.

back to table

Adjacency matrix (for free and oriented trees)

Adjacency matrix is a n-by-n binary matrix representing either labelled free tree or labelled oriented trees. For labelled oriented trees, there are n-1 1's each corresponding to an edge from parent to child. For labelled free trees there are 2*(n-1) 1's each corresponding to an edge from one vertex to another and another edge back. Example:
    1 
   /\ 
  2  3 
 /\ 
4  5 
For free tree:
  1 2 3 4 5
1 0 1 1 0 0
2 1 0 0 1 1
3 1 0 0 0 0
4 0 1 0 0 0
5 0 1 0 0 0
For orieted trees with root labelled '1':
  1 2 3 4 5
1 0 1 1 0 0
2 0 0 0 1 1
3 0 0 0 0 0
4 0 0 0 0 0
5 0 0 0 0 0

The adjacency matrix can be compressed with a runlength encoding or quad-tree encoding

One wonders about whether the adjacency matrix can be reduced to some (block- or tri-)diagonal form. The following refutes such a possibility.
Theorem: There exists a tree whose adjacency matrix is irreducable to some diagonal form.

Because adjacency matrices are sparse, they can be compressed with a runlength coding. For example the top matrix above, read row-by-row, is: 1:0, 2:1, 2:0, 1:1, 2:0, 3:1, 5:0, 1:1, 5:0, 1:1, 3:0.

back to table

Adjacency List

Adjacency Lists can represent both labelled free tree and labelled oriented trees. This is a list of the n-1 edges in an n node tree. Alternatively, this can be represented. Example: consider the tree
     1
   /  \
  2    5
 /\   /|\
3  4 6 7 8
Adjacency list version 1:
(1,2),(2,3),(2,4),(1,5),(5,6),(5,7),(5,8)
Adjacency list version 2:
1: 2,5
2: 1,3,4
3: 2
4: 2
5: 1,6,7,8
6: 3
7: 3
8: 3
For a oriented tree, say with root '1', list only inderior nodes and children:
1: 2,5
2: 3,4
5: 6,7,8
back to table





Ordered Labelled

parenthesesed strings in pre or postfix ntn


prefix: A(BC(K)))D((E(H))F(J)G) 
postfix: (B(K)C)A((H)E(J)FG)D

[K] (knuth pg336)

back to table

Mitchell's cononical recursive representation


List of indices to parent they were hung from when added, label i corresponds to ith node added

Remark.

[Mi] has some linear-time operations on this
[K] mentions this pg 390

back to table





Classification of Operations on Trees

Base and Derived Operations

Definitions.


We fix a base set of operations as follows.

Conjecture.




Common Operations


A classification of tree operations follow.
Table: Classification of Operations.
Access Modify
Local
  • access parent
  • access next child
  • access m'th child
  • access neighbor
  • ...
  • insert and graft
  • delete and prune
  • refine
  • ...
Global
  • traverse
    • breadth first - all nodes or leaves only
    • depth first - all nodes (pre-, in-, post-order) or leaves only
  • search
  • access node at a navigation sequence
  • ...
  • balance
  • merge trees in some way
  • Convert from one representation to another
  • ...








Efficienct Implementation on a Computer

Store a given tree representation in computer memory.

Choosing a tree representation based on desired constraints and operations.

Miscellaneous thoughts





References

[KM] Katajainen, Makinen. Tree Compression and Optimizatin With Applications, 1990.
[Za] S. Zaks, "Lexicographic generation of ordered trees", Theoret. Comput. Sci. 10 (1980) 63-82.
[K] Knuth, The Art of Computer Programming, Volume 1.
[De] Erik Demaine, MIT 6.897: Advanced Data Structures, Lecture 12, Spring 2003
[Mi] Mitchell, Linear algorithms on recursive representations of trees
[Re] Read, Ronald C. The coding of various kinds of unlabeled trees. Graph theory and computing, pp. 153–182. Academic Press, New York, 1972.
[Ko] Thomas Koshy, Catalan Numbers with Applications
[RR] Rajeev Raman and S. Srinivasa Rao, Succinct Representations of Ordinal Trees
[CG] Conway and Guy, The book of numbers