There is a joke in computer science that "everything is a tree" due to their widespread use and applications. Trees are abstract data types/structures with a hierarchical build made up of a central root node (thought some types of tree allow this space to be empty) and many levels of children nodes under it. These nodes all link up to form a tree like the one below:
Trees can be, and often are, implemented recursively as a collection of nodes that have both a value or condition attribute and one storing a reference for their parent and/or children nodes. The root is the only node that has no parents; all others must have a single parent node in standard trees. A node with no children is called a leaf. The height of a tree is the longest possible branch (path) from the root to one of these leaves, counted by the the number of nodes it passes through to get there. The industry standard is to say the root has height 0 but some notate it as height 1. Sometimes it is useful to look at trees as a whole, but often more so at subsections or the individual nodes. Common operations on trees are:
- adding a node
- searching the tree for a value
- removing a node with a specific value
There are many types of trees too! Common types include:
- Binary search trees (BSTs) - wherein values are sorted as they are added. You begin at the root and go left if the value is smaller than the root's value and right if it is bigger, repeating those comparisons until you reach a place where the node you're adding can be a leaf. The above tree is an example of this type.
- AVL trees - a BST which is balanced, i.e. arranged so that the heights of each branch are within 1 node of each other. The above tree restructured as an AVL tree would look as follows:
- Red-Black trees - Similarly to AVL trees, these trees must be balanced, but with branch heights 2 nodes of each other. Each node is also assigned a colour attribute, either red or black, and the black height is the number of black nodes in the longest branch from root to leaf. The root of a Red-Black tree is always black.