(Up to Basic
It is recommended that you read the essay
on linked lists before proceeding to this essay.
Trees are data structures organized into a group of interconnected
nodes that form leaves and branches. This is a little confusing,
so looking at the diagram below would be easier to understand than
reading an explanation:
You can see why this structure is called a tree. A computer data
tree, however, is different from a plant tree in that the root is
at the top and the leaves are at the bottom. The root is
the first node of the entire tree, and there is only one root per
tree. In the diagram, D is the root node. Each of the letters in
the tree above represents a node, much like the linked
Most of the nodes link to one or more other nodes, represented
by the red arrows in the diagram above. Nodes that are directly
linked to a node a level above them are called child nodes
or children to the parent node, and nodes that share
a parent node are a set of sibling nodes. The link between
a parent and a child is called a branch. Thus, in the diagram
above, H is a parent node to G, K, and L. These three child nodes
are siblings to each other. A sub-tree is just a section
of the tree. G, S, and F constitute the left sub-tree extending
Some nodes do not have any children, and these are known as leaf
nodes. So, S, F, B, L, and M are all leaf nodes.
What I have just described above is the general structure for a
tree. Still, most programmers use a variation of the general tree
that is more suited to the particular problem at hand. These variations
usually deal with the organization and structure of the trees themselves,
and each have their good points.
The simplest variation to the general tree is a binary tree.
In a binary tree, each node has at most two children. The binary
tree also has a couple of variations. The best known variation is
the binary search tree, which is ordered
to allow really fast data searching.
Another type of binary tree is the heap.
A heap is primarily used to prioritize data, but there is also a
very fast array sorting algorithm implemented with a heap.
Other ordered tree variations are the 2-3
tree and the 2-3-4 tree. Although ordered, they are not binary
trees. These take care of the problem of balancing the tree.
This speeds up the searching of the tree.
One of the most complex tree variations is the Red-Black tree.
This tree is basically a binary tree representation of the 2-3-4
tree, thus combining the more simple binary tree design with the
search efficiency of a 2-3-4 tree.
Finally, a tree variation that is not necessarily ordered, the
minimax game tree. This structure is important to programming Chess
and Go AI, as well as the AI of many other board games.