Tree in data structure
Tree represents hierarchical relationship. A tree is a finite set of one or more nodes such that there is a specially designated node called the root and the remaining nodes are partitioned into n>= 0 disjoint sets T1,... , Tn, where each of these sets is a tree. The sets T1....Tn are called the subtree of root
T = {V,E}
V → Vertex
E → Edge
R → Root
Root does not have a parent, but each one of the other nodes has a parent node associated to it. A node may or may not have children. A node that has no children is called leaf node.
Degree : The number of subtree of a node is called as its degree.
Terminal node : Nodes with no children. It can be also called as leaf node whose degree is zero.
Non-terminal node : Nodes with at least one child.
A path in a tree is a list of distinct vertices in which successive vertices are connected by edges in the tree. There is exactly one path between the root and each of the other nodes in the tree.
Sibling : Children of same parent are known as siblings. Root does not have sibling. For example in the shown tree B, C and D are siblings.
Height : Height of tree is the number of edges from root to its farthest leaf node. Thus all leaves are at height zero. The height of the tree is same as the height of the root.
Level : Level is (number of ancestor+1) for the given node. All the sibling nodes have same level. Root
always be on 1st level.
The depth of any node ni is the length of the path from root to ni. Depth of a node is sometimes also referred to as level of a node
Each node, except the root, has a unique parent, and every edge connects a node to its parent. Therefore, a tree with N nodes has N–1 edges.
- Node A is the root node.
- E, F, G, H, J are the Terminal nodes.
- z The nodes E, F are siblings of subtree B, so as H, I are of subtree D.
- z Node G has no sibling as the parent node has no other child node.
- z Height of the tree is 3.
{
int data;
struct node *left;
struct node *right;
}
Applications of trees
The following are the applications of trees:
- Storing naturally hierarchical data: Trees are used to store the data in the hierarchical structure. For example, the file system. The file system stored on the disc drive, the file and folder are in the form of the naturally hierarchical data and stored in the form of trees.
- Organize data: It is used to organize data for efficient insertion, deletion and searching. For example, a binary tree has a logN time for searching an element.
- Trie: It is a special kind of tree that is used to store the dictionary. It is a fast and efficient way for dynamic spell checking.
- Heap: It is also a tree data structure implemented using arrays. It is used to implement priority queues.
- B-Tree and B+Tree: B-Tree and B+Tree are the tree data structures used to implement indexing in databases.
- Routing table: The tree data structure is also used to store the data in routing tables in the routers.
Types of Tree data structure
- General tree
- Binary tree
- Binary Search tree
- AVL tree
- Red-Black Tree
- Splay tree
- Treap
- B-tree
