Tree information models

A family tree in a photo album, the folders on a computer, the contents page of a book, the draw of a sports tournament — they all have the same shape: branches grow from one starting point, and more branches grow from those. Such a structure is called a hierarchy, and its graphic model is a tree. The name is no accident: the picture looks like an upside-down tree, with the root at the top and the leaves at the bottom.

In the lesson “Models and modelling” we met the tree among the graphic information models, and in “Table information models: solving logic puzzles with tables” we worked with tables. A table places objects side by side, while a tree shows who is under whom and what is part of what.

The parts of a tree

• Root — the top node; it has no parent.
• Node (vertex) — any element of the tree; the lines joining nodes are edges (branches).
• Parent and child — an upper and a lower node joined directly by an edge. A node may have any number of children.
• Leaf — a node with no children; a node with at least one child is an internal node.
• Level — the number of edges from the node up to the root: the root is on level 0, its children on level 1, and so on. The largest level is the height of the tree. (Some books count the root as level 1 — then every number is one larger; read the task carefully.)

Family trees and classification trees

A family tree shows the descendants of one person: the root is the ancestor and every level is a generation (children, grandchildren, great-grandchildren). Careful: if both parents of every child are drawn, the picture is no longer a tree, because a node would have two parents. You get a tree when it shows the descendants of one person.

A classification tree divides a notion into kinds: the general notion is at the root and more specific kinds go lower down. A tree can also be written without drawing — as a nested list, where every child is written one step further in than its parent. The contents page of a book (1, 1.1, 1.2, 2 …) is such a list. Below, the classification of software is given as a nested list.

Software
├── System software
│   ├── Operating systems
│   ├── Utilities
│   └── Drivers
├── Application software
│   ├── Text editors
│   ├── Spreadsheets
│   ├── Graphics editors
│   ├── Desktop publishing systems
│   └── Database management systems
└── Programming tools

The file-system tree and the full name of a file

Files on a disk are arranged as a tree too. The root is the disk’s root folder (C:\), internal nodes are folders, and leaves are files and empty folders. The path from the root to any file is unique, because every node of a tree has one parent. This path is the path of the file, and the path together with the file name is the full name of the file. In Windows folders are separated by a backslash \. For working with files and folders see the lesson “Software, operating systems and files”.

A tree is a graph without cycles

In the language of graphs, a tree is a connected graph without cycles: any two vertices are joined by a path, but there is no closed loop (cycle). Three useful facts follow: the path between any two nodes is unique; removing any edge splits the tree into two parts; adding any new edge creates a cycle. More about graphs in the next lesson, “Graph information models: adjacency matrices and counting paths”.

A tree can also be written with brackets: after a node, its children are written in brackets, separated by commas. The tree in the picture is written as A(B(E(H, K), F), C, D(G(L, M, N))). The letters without brackets after them are the leaves.

tree = {
    "A": ["B", "C", "D"],
    "B": ["E", "F"],
    "D": ["G"],
    "E": ["H", "K"],
    "G": ["L", "M", "N"],
}

def show(node, level):
    print("    " * level + node)
    for child in tree.get(node, []):
        show(child, level + 1)

show("A", 0)
nodes = {"A"} | {c for kids in tree.values() for c in kids}
leaves = [n for n in sorted(nodes) if n not in tree]
edges = sum(len(kids) for kids in tree.values())
print("nodes:", len(nodes), "edges:", edges)
print("leaves:", leaves)

A
    B
        E
            H
            K
        F
    C
    D
        G
            L
            M
            N
nodes: 12 edges: 11
leaves: ['C', 'F', 'H', 'K', 'L', 'M', 'N']