Tree Data Structure

Tree data structure

Tree data structure is a non linear data structue which is organized data in herarchical structure and this is recursive definination.

A tree data structure is a finite set of one or more node such that there is specially designated node called root and the remaining nodes are partitioned into n>=0 disjoint sets T1,T2,…Tn.  T1..Tn is called the subtrees of thr root.

The tree is representation for hierarchical information. Thus, tree are used to represent genealogical information.

 

Tree Terminologies

1. Root

 

In a tree , the first node is known as Root Node. Every tree must have root node. The root node is the origin of tree data structure .In any tree, there must be only one root node. We never hvae more than one root nodes in a tree

 

2. Edge

 

In a tree  , the connecting between any two nodes is called as EDGE. In a tree with  N number of nodes there will be maximum of N-1 number of edges

3. Parent

 

In tree the node which is predecessor of any node is called as PARENT NODE.  The node which has branch from it to any other node is called parent node.

4. Child

 

In a tree the node which is descendant of any node ia called CHILD NODE.The node which has a link from its parent node is called child node. In atree, any parent node can have any number of child nodes.

5. Siblings

 

In a tree, nodes which belong to same parent are known as SIBLINGS. The nodes with same parents are called as Sibling nodes.

6. Leaf

 

In a tree, the node which does not have a child is called as LEAF NODE.  In a tree data structure, the leaf nodes are also called External Node. External node is also a node having no child.

7. Degree of tree

 

In a tree ,the total number of children of a node is known as DEGREE of that node. The highest degree of a node among all nodes in a tree is called as Degree of tree.

8. Height of tree

 

In a tree data structure, the total number of edge from left node to a particular node in the longest path is called as Height of that node. Height of all leaf node is ‘0’.

 

Types of Tree

1. Binary Tree
2. Binary Search Tree
3. AVL Tree
4. B-Tree

Applications of trees

 

1. Storing naturally hierarchical data:
2. Organize data:
3. Heap
4. B-Tree and B+Tree
5. Routing table

 

Read more, Fibonacci Heap Data Structure