Data Structures - Tree ADT

<< Previous

Next >>





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

  • It used to implement the file system of computer system.
  • The mathematical expression is calculated by using trees data structure.
  • It supports searching operations in O(log n) average time.
  • Tree is defined as collection of n nodes, among that one node is the root node, and n-1 edges. In which every node has one parent except the root node.
  • It consists of a finite set of elements(called nodes) and a finite set of directed line(called branches or edges)

Terminology

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 >>





Learn C Progamming

Krivalar.com © 2017