Tree Data Structure - ADT

<< Previous

Next >>





Tree is a data structure better understood visualizing it in the shape of a tree having a root, branches, sub branches and leaves.

If you draw the tree data structure, you draw the tree upside down with the root at top, branching out and having leaves at the sides and bottom of the tree.

A tree will have one and only one root node.

If you consider a tree has n nodes, it would have n-1 edges. Every node has one parent node except the root node.

Tree is a simple and more useful data structure in which the average running time of most operation is O(log n).


Figure 1. Tree Structure

Tree data structure is useful in a number of scenarios or use cases

  • Tree data structure is used to implement the file system of computer system. For example, like Windows explorer on Windows OS, File Manager on Android mobile phones, Files software on some Linux operating systems
  • Tree data structure is used to evaluate simple or complex mathematical expressions. This kind of tree is a special tree called the

    expression tree

  • Tree data structure supports searching operations in O(log n) average time.

    Binary tree and ternary tree support search operations


  • Tree data structure consists of a finite set of elements(called nodes) and a finite set of directed line (called branches or edges)


Terminology used in Tree Data Structure

Various terms are used to describe the attributes of a tree as given below. These terms have been described based on Figure 2


Fig 2. A Tree



Root
The first node is called root, in which indegree of root is zero. Root node is A
Subtree
It is the connected structure below the root node.
Leaf
Leaf is any node in which outdegree of the node is zero. Leaf nodes are D, E, and G
Parent
A node is parent if it has successor nodes. Parent nodes are B, C, and F
Child
The node is a child if it has a one predecessor. B and C are the Child nodes of A.
Siblings
Two or more nodes with same parent. D and E are siblings
Ancestor
It is any node in the path from root to that node. The ancestors of node D are B and A
Descendant
All the nodes in the path from a given node to a leaf node. The descendents of node C are F and G
Path
It is a sequence of nodes in which each node is adjacent to the next one. For reaching D, AB and BD these two branches should be added. Path is ABD
Degree
The number of lines associated with a node is called degree of the node. Degree of node B = 3
Degree of the node = Indegree + Outdegree
Indegree
Number of branches directed towards the node. Indegree of node B = 1
Outdegree
The branch is directed away from the node. Outdegree of node B = 2
Level
It is a distance from root node is that root node is at level 0, its next child is at level 1, and its grandchild is at level 2 and so on.
Level 0 node A
Level 1 nodes B and C
Level 2 nodes D, E and F
Height of the tree
The height of the tree is the level of the leaf in the longest path from root plus one.
The height of the tree is 4 (i.e. it has 3 levels (3+1))
Length of the path
It is the number of edges on that path. The length of the path from A to F is 2
Depth
The depth of the node is the length of unique path from root to that specific node. The depth of node G is 3
Height of the node
The height of the node is the longest path from that node to leaf. The height of node C is 2

<< Previous

Next >>











Tree Data Structure - ADT

<< Previous

Next >>





Tree is a data structure better understood visualizing it in the shape of a tree having a root, branches, sub branches and leaves.

If you draw the tree data structure, you draw the tree upside down with the root at top, branching out and having leaves at the sides and bottom of the tree.

A tree will have one and only one root node.

If you consider a tree has n nodes, it would have n-1 edges. Every node has one parent node except the root node.

Tree is a simple and more useful data structure in which the average running time of most operation is O(log n).


Figure 1. Tree Structure

Tree data structure is useful in a number of scenarios or use cases

  • Tree data structure is used to implement the file system of computer system. For example, like Windows explorer on Windows OS, File Manager on Android mobile phones, Files software on some Linux operating systems
  • Tree data structure is used to evaluate simple or complex mathematical expressions. This kind of tree is a special tree called the

    expression tree

  • Tree data structure supports searching operations in O(log n) average time.

    Binary tree and ternary tree support search operations


  • Tree data structure consists of a finite set of elements(called nodes) and a finite set of directed line (called branches or edges)


Terminology used in Tree Data Structure

Various terms are used to describe the attributes of a tree as given below. These terms have been described based on Figure 2


Fig 2. A Tree



Root
The first node is called root, in which indegree of root is zero. Root node is A
Subtree
It is the connected structure below the root node.
Leaf
Leaf is any node in which outdegree of the node is zero. Leaf nodes are D, E, and G
Parent
A node is parent if it has successor nodes. Parent nodes are B, C, and F
Child
The node is a child if it has a one predecessor. B and C are the Child nodes of A.
Siblings
Two or more nodes with same parent. D and E are siblings
Ancestor
It is any node in the path from root to that node. The ancestors of node D are B and A
Descendant
All the nodes in the path from a given node to a leaf node. The descendents of node C are F and G
Path
It is a sequence of nodes in which each node is adjacent to the next one. For reaching D, AB and BD these two branches should be added. Path is ABD
Degree
The number of lines associated with a node is called degree of the node. Degree of node B = 3
Degree of the node = Indegree + Outdegree
Indegree
Number of branches directed towards the node. Indegree of node B = 1
Outdegree
The branch is directed away from the node. Outdegree of node B = 2
Level
It is a distance from root node is that root node is at level 0, its next child is at level 1, and its grandchild is at level 2 and so on.
Level 0 node A
Level 1 nodes B and C
Level 2 nodes D, E and F
Height of the tree
The height of the tree is the level of the leaf in the longest path from root plus one.
The height of the tree is 4 (i.e. it has 3 levels (3+1))
Length of the path
It is the number of edges on that path. The length of the path from A to F is 2
Depth
The depth of the node is the length of unique path from root to that specific node. The depth of node G is 3
Height of the node
The height of the node is the longest path from that node to leaf. The height of node C is 2

<< Previous

Next >>