A tree is a data structure that represents data in a hierarchical form. Due to its non-linear form, it is highly preferred since it allows quicker and easier access to data.
Terminologies
Node: this is an entity that contains a key or value and pointers to its child nodes.
In trees, there are different types of nodes:
-
Child node: a child node is a descendant of any node.
-
Leaf node: these are nodes that do not have any child nodes. The nodes can also be called external nodes.
-
Internal nodes: a node that has at least one child
-
Ancestor node: is a predecessor node on a path from the root to that node.
-
Root: a node that is the top most and does not have any parent.
-
Parent: a node that has a sub-node
-
Sibling: a node that has the same parent
-
Descendant: the immediate successor of a node
Edge: the link between nodes
Height of a node: the longest path from the node to a leaf node
Depth of a node: number of edges from the node to the root.
Height of a tree: height of the root node
Degree of a node: total branches of that node
Forest: a collection of disjoint trees
Types of Trees
General tree: in this tree, the node can have either 0 or a maximum n number of nodes.
Binary tree: in this tree, a node can have a maximum of two child nodes.
Binary Search tree: a node can be represented with three fields that is data part, left-child, and right child. A node can be connected to utmost two child nodes. The node in the left sub-tree should have a value less than the root node while the value of the right sub-tree should be bigger than the value of the root node.
AVL tree: is a height-balanced binary search tree where each node has a balance factor calculated by subtracting the height of its right subtree from that of its left sub-tree.
Red-Black tree: is similar to AVL the only difference is that the red-black tree requires a maximum of two rotations to balance the tree.
Tree Applications
Binary Search Trees are used to check whether elements are present in a set or not.
Tries which are modified trees are used in modern routers to store routing information.
Compilers use syntax trees to validate the syntax of every program you write.