Prerequisites[edit]
Introduction[edit]
In Computer Science, Trees are a hierarchal data structure that are very commonly used. At its core, the Tree is a series of nodes where each node contains some data and references one or multiple other nodes called Children. These structures are called Trees because of the visual resemblance between the data structure and a tree's roots. It's because of this that the top most Node is called the root.
The use of Trees as Data Structures can be seen everywhere: file systems, relationship hierarchies, visual displays and GUIs and many more. This is why developers ought to understand this data structure and how to apply it.
Structure[edit]
As has been mentioned, the structure of a Tree is made entirely of Nodes where each node has some data that's being stored and references to other Nodes lower in the tree. If you look at a Node in a tree, it will likely be referencing one or several Nodes beneath it. These Nodes that are being referenced are called the Children or Child Nodes while the Node they come from is their Parent.
Its important to understand that in a General Tree, a Node can only have One Parent but multiple children.
Now, looking at the Structure of a tree, it starts with The Root. The root is the very top of a Tree's hierarchy and can be recognized because it is the only Node that is not referenced to by another Node. Conversely, a Tree will end with Leaves. Leaves are simply the Nodes that do not reference any other Node.
In fact, the idea of The Root and Leaves lends itself into the idea of a Node's Degree. The Degree of a Node, when discussing Trees, simply refers to how many children does a Node have plus the Number of children each of those Nodes have and so on until you reach a Leaf. Said in another way, The Degree of a given Node is the number of Nodes that can call that given Node one of its roots. This means that if there are a total of twenty Nodes in a Tree, the top Root will have a Degree of 20.
Additionally, in Trees there's the concept of Level. The Root will always be Level 0 and its immediate Children will be Level 1, their children will be level 2 and so on. Note that a Leaf can come up in any Level greater than 0, not just the lowest level in the tree.
For clarification on a Tree's Structure, consult the following diagram.
Usages[edit]
As we mentioned, Trees have many Usages in the real-world. Most notably, they're used for storing data that lends itself to be hierarchal. The common example being, of course, a file system. This is why the base of a file system is often called The Root. Indeed, Hierarchies are present in many day-to-day examples. Games may have hierarchies implemented into collectible items, Websites have tree-like hierarchies in terms of its URL, Enterprise applications in CAD or Digital Art Software may store its file data as a Tree, Large Data companies often contain much of their data in hierarchies for quicker response times when executing commands.
In fact, the General Tree can be used to implement more specialized data structures such as Binary Trees, which are often used for applications where time complexity is very important specifically in searching algorithms. This has made the usages of Tree Data structures very common and is why knowing algorithms using Trees is so important.
