Tree representation

This section is about ways in which you can represent a tree.

Trees are a specific type of graph, so any graph representation also provides a way to represent a tree.

Therefore this section will focus only on methods specific to tress, and which cannot be used for graphs in general.

Table of contents
- Nested set model Tree representation

Nested set model

This is particularly important in SQL: Nested set model in SQL, as it is an efficient way to transverse trees there, since querying parents every time would require multiple disk accesses.

The ASCII art visualizations from stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/194031#194031 are worth reproducing.

As a tree:

Root 1
- Child 1.1
  - Child 1.1.1
  - Child 1.1.2
- Child 1.2
  - Child 1.2.1
  - Child 1.2.2

As the sets:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

Consider the following nested set:

0, 8, root
  1, 7, mathematics
    2, 3, geometry
      3, 6, calculus
        4, 5, derivative
        5, 6, integral
      6, 7, algebra
  7, 8, physics

When we want to insert one element, e.g. limit, normally under calculus, we have to specify: