Understanding Tree Concepts In Data Structure

Tree is the non-linear and dynamic data structure. It does not store data elements in sequential order. Tree represents logical model of the nodes in hierarchical form, example: Hierarchy of designations in any organizations.


Tree is the collection of nodes and each node contains data element and reference of other node. The top node of the tree is called Root and root can have other node’s references.
Root of the tree is known as parent and other associated nodes are it's children.If tree has two child node such type of tree is known as Binary Tree.

We will discuss about binary tree later.
Tree Data Structure. ByTechAchievers.com 

Let's discuss about some terms used in tree data structure.


I had taken examples from the chart.

S.No
 Terms
Explanation
Example
1
Root
Top node of the tree.
is the root node.
2
Parent
Node that connects other node with itself.
B, C, E, and F are parents.

A is also parent of all nodes.
3
Children
Node that is associated with parents.
D and E are children of B.

E and G are children of C.
4
Siblings
Nodes that have same parent. 
D & E are siblings because of same parent B.

similarly,

F & G are siblings.

B & C are siblings.
5
Leaf
Node that don't have any child node.
D,G,H and I are leaf nodes.
6
Edge
Connection or link between nodes.
Edge between A and B is 1. (A ->B)

Edge between A and D is 2. (A->B->D)

Edge between and I is   3. (A->C->F->I)

Note: 
Edge = Number of connected nodes -1
7
Sub-tree
Tree inside the main tree. 
B,C,E is the subtree.
C,F,G is the subtree.
8
Depth
Number of edge available between the node and root. Root depth is 0
Depth of E is 2, because edge from root A to E is 2.
9
Height
Number of edges in the longest path from root to leaf. 

Leaf height is 0.
Longest path is 
A->B->E->H  or 
A->C->F->and number of edges from A to H or A to I is 3.

Height of the tree is 3 
10
Internal and External node
Internal nodes are that have at least one child.

External nodes are that don't have any child. Leaf nodes are external nodes.
E,F are internal nodes.

D,G,H and I are external or leaf nodes. 
11
Ancestor
Parent, Grandparent or Upper level relationship of the nodes. 
Ancestor of D
B and A (upper level node of D)
12
Descendant
Child, Grandchild or Lower level relationship of the nodes. 
Descendant of C are
F and I (Child level relationship).  



Advantages And Disadvantages of Tree -


Advantages

Non linear data structures are much faster than linear data structures while searching data.

Node can be insert and delete at any place efficiently.

Provides indexing which is helpful in database management.

Disadvantages

Due to its hierarchical structure debugging of any issue is not easy.

Tree based real-life examples   

Managing any organization's designation hierarchical structure.

Useful in networking based applications.

Useful in Router applications.

Widely used in searching based application.


Thanks for reading, please do share and comment your suggestions.

No comments

Powered by Blogger.