Trees

Posted on August 3rd, 2022

Updated on September 9th, 2022

Part of (Re)Learning CS

Talks aboutComputer Science

Trees are a restricted subset of graphs.

To get to grips with the terminology, jump ahead to the basics ofgraphs.

Rooted Tree

In a rooted tree, all nodes have a one parent with many children. All above nodes are ancestors and all below nodes are descendants.

The single node at the top is the root node (no parents) and the nodes are the bottom are leaves (no children). Any node with children is also an internal node.

Rooted trees have an implicit hierarchical structure. With only one parent and multiple children, they can be considered 'top-down'.

Unrooted Tree

In an unrooted tree , there is no notion of parents or children. A given node has neighbours; any nodes with one neighbour is a leaf and any node with many neighbours is an internal node.

Unrooted trees do not have an implicit hierarchy. They can be interpreted as 'outside-in', where only the relationships from lead to internal node are considered , or vice versa with 'inside-out'.

Binary Tree

A binary tree is a rooted tree with these constraints:

• All nodes have a parent except the root
• All nodes have either 0, 1, or 2 children

Generally, we only maintain a pointer to the root node and access its children programmatically. Maintaining pointers to children is possible but complex, as the structure changes.

We can further consider a binary tree as full, meaning every node has two children, excluding the leaves; or complete, meaning every level, but possibly the last, is completely filled and all nodes are to leftmost.

To make the diagram above complete, 8 would become the right child of 3 and 9 would become the left child of 4. To make it full, 5 and 6 would need two children (or 7, 8, and 9 would need removing).

Traversal

We have four algorithms to remember! All of which are $\mathcal{O}(n)$ cos every node is visited.

Heap

A heap is a tree that satisfies the heap property: a parent node means higher priority. A binary heap must also satisfy the binary tree constraints and be complete.

Within the world of heaps, we firstly have min-heaps, in which a parent node has a lesser-or-equal value to all of its children. That is, a smaller value means higher priority. A max-heap is the opposite.

It is also valid for duplicate node values in a heap — two things can have the same priority.

Binary Search Tree

A Binary Search Tree (BST) allows arbitrary values to be found fairly quickly. It's structured as a rooted binary tree, where every node is greater than all nodes to its left and less than all to its right. Inherently, only comparable types can be stored in a BST.

The height of a BST is the longest distance from the root of the tree to a leaf; a tree with no nodes has a height of -1, only a root has a height of 0, and a node+leaf has a height of 1, etc.

We can also consider the balance of a BST. When balanced, most leaves are equidistant from the root and most internal nodes have two children. When perfectly balanced, it's all of em.

Unbalanced trees are also a thing.

The average-case time complexity to find an element $N$ is $\mathcal{O}(\log N)$; there is a proof, but it's fucking mental.

Implementations

Generally, implementing a tree structure involves a Node object containing a value and child pointers — an array for normal trees, left and right properties for binary trees.

Alternatively, we can utilise pointer arithmetic to store binary trees inarrays. The start of the array represents the tree root and the following formulae can access nodes relative to an index $I$:

• Parent: $\lfloor\frac{I-1}{2}\rfloor$
• Left Child: $2i+1$
• Right Child: $2i+2$