Tree

Abstract

A Tree is a directed, acyclic Graph. That means, you can't go back to the node you came from, and you can never visit a node you've already been to.

Behavior

In a tree, there are branch nodes and leaf nodes.

The branch nodes are nodes with child nodes. In some trees, they have data, but in others, they have none.

Leaf nodes are nodes with no children. Leaf nodes always have data associated with them.

To walk a tree, you need to use a recursive algorithm that walks each of the nodes from this node. It will then combine the results somehow and pass it back up.

An alternative, non-recursive approach requires a stack to keep track of where you've been. This stack is no different from the stack that a recursive algorithm would use to keep track of where to return to. The recursive implementation is much simpler and precise.

Types of Trees

Lists

A List is a special type of tree where every node only has 0 or 1 child nodes.

Binary Tree

A Binary Tree is a special type of tree where every node only has 0, 1 or 2 child nodes. Lisp's cons cell is really a binary tree.

Note that a binary tree can be represented with a vector. To do this, imagine the tree placed upside down, with the trunk in the middle. Then squash it down so that child trees all fit between their parent and grandparent or the edges.

For instance, the following tree:

    A
   / \
  B   C
 / \ / \
 D E F G 

Compresses into:

 DBEAFCG

The root node is in the middle.

 DBEAFCG

It's child nodes are in the middle of the left and right halves.

    A
   / \
 DBE FCG

And so on until you run out of spaces.

You can represent non-existent nodes with null data.

Balanced Tree

A balanced tree has all the branches about the same depth as all the others. That is, it looks less like a list and more like a bush.

Unbalanced Tree

An unbalanced tree is not balanced. This means some of the branches are much longer than others.

Binary Search Tree

A Binary Search tree[1] is a way to quickly find data. Each node has a value. The tree with all the values less than the node is to the left. The values greater than are to the right. By traversing the tree, you can quickly find the value, or determine that it isn't there. If the tree is balanced, the search time is logarithmic.

The binary search algorithm is the same as the binary search tree search algorithm except the tree is flattened into a vector.

B-Tree

A B-Tree[2] is a great way to organize data such as dates. It allows you to not only find specific values quickly, but to find ranges.

B+ Tree

A B+ Tree builds on the B-Tree. (I don't completely understand it, honestly.) There's also a B# Tree which is a little bit different.

Abstract Syntax Tree

In Parsing, for languages with recursion, the expression is represented with an abstract syntax tree. You can execute the AST by writing an algorithm that can traverse the tree and evaluate each node. Usually, however, the AST is compiled into a linear set of machine instructions much like a binary tree can be squashed into a vector.

You can also modify the tree to find equivalent trees that are easier to work with.