[Image 1]
Hey it's a me again @drifter1!
Today we continue with Mathematics, and more specifically the branch of "Discrete Mathematics", in order to get into Trees.
So, without further ado, let's get straight into it!
Approaching graphs is easier when focusing on specific types of them. In the previous parts various types of graphs were discussed, but of course there are even more.
One such type are the so called trees. Trees are basically acyclic connected graphs, which means that they are connected graphs containing no cycles. If the graph is not connected then it can be a forest (multiple trees). A forest is basically an acyclic graph. Of course any connected forest is a tree.
Trees are useful in many applications as they satisfy the following properties:
Trees don't have any clear order as is, but it's common to specify a root vertex with only outgoing edges. Such trees are known as Rooted Trees.
In the context of rooted trees, vertices are given special names. When two vertices are adjacent then one of them is known as the parent and the other as the child of the parent. The one closer to the root is the parent. That way, all non-root vertices will have exactly one parent. Vertices with the same parent are siblings.
This logic extends further, meaning that the child of a child vertex is a grandchild etc. In general, vertices with a path to an ancestor vertex are its descendants. So, all vertices of a tree are descendants of the root. Last but not least, vertices with no children are known as leaves.
The vertices of a tree also have levels. The root has a level of zero. The children of the root have a level of one. This logic extends, meaning that each child has a level more than its parent.
The maximum number of vertices in a branch is known as the depth or height of a tree. The depth of the root vertex is defined as one, and so the depth is greater then the maximum level of the tree.
General trees can have any number of children. On the other hand, in binary trees each vertex can only have up to 2 children. This limitation makes such trees very useful in lots of computer science applications.
A binary tree can always be split into two subtrees: the left subtree and the right subtree, which have the left child (and right child respectively) of some vertex as a root.
Binary Trees can be traversed using three methods:
All of these are recursive processes. The main difference is when the root / parent is visited. In pre-order the root / parent is visited first, and then the left subtree, right subtree respectively. In post-order, the root is visited last. Finally, in in-order, the root is visited in between, yielding a left -> root -> right order.
Many algorithms can be written for trees because of the simple traversal mechanisms. In order to be able to use them in the case of any connected graph as well, a subgraph known as a spanning tree is taken from the graph, which contains all the vertices of the original graph but is a valid tree. Every connected graph has a spanning tree, and mostly multiple such trees. Finding the minimum spanning tree is a very common problem in Graph Theory and Computer Science.
Mathematical equations used in this article, have been generated using quicklatex.
Block diagrams and other visualizations were made using draw.io.
And this is actually it for today's post!
Only a few more parts and the series is officially over...
See ya!
Keep on drifting!
