UNIT III
NON-LINEAR DATA STRUCTURES
Trees: Definition, Types of Trees, Operations of tree DS, Working etc.,
Binary Tree: Definition, Operations (Insertion, Deletion)
AVL Tree: Definition, Operations, rotation etc
M way tree, B Tree, B* Tree etc
Graph – Definition, Types, Operations, Traversal, algorithms etc
Trees
In linear data structures (arrays, queues) data are stored sequentially.
Factors involved in considering the right data structure:
1) What type of data are stored?
2) Cost of operations involved.
3) Efficient Memory usage.
A tree is one of the data structures that represents hierarchical data.
For Example:
Employees and their positions can be easily represented using tree structure.
The above figure represents Tree data structure. It is an upside-down tree, where the root is at the
top.
There are two direct reports for the root (one of the left and the other on the right).
Tree data structure is efficient to represent data of hierarchical nature and it consist of objects /
entities known as nodes.
In simple terms, tree is a non-linear data structure which is a collection of objects / entities that are
linked together to represent a tree structure.
Tree is a non linear data structure and consists of multiple levels.
Each node can contain any type of data.
Nodes that follow are called children.
,Basic Terminologies of a tree structure:
Root :
The topmost node in the tree hierarchy.
Root doesn’t have a parent.
If a node is directly connected to some other node, they are said to have parent child relationship.
Child node:
If a node is a descendant of any other node, it is known as child node.
Parent:
If a node contains any subnode, then that node is knows as the parent of the sub node.
Sibling:
Nodes that have same parent are called siblings.
Leaf Node:
A node of the tree, that doesn’t have any child node is called a leaf node.
Leaf node is generally at the bottom of the tree.
Leaf nodes are also called as external nodes.
Internal node:
A node that has atleast one child is knows as Internal node
Ancestor node:
It is that node that are predecessors node on the path from the root till the node.
In the above example, nodes 1,2,5 are ancestor of node 10.
Descendant:
The immediate successor of a given node is known as the descendant of a node.
Properties of a Tree Data Structure
Recursive data structure
,o However, is the depth of a tree, the tree can be traversed thoroughly only through the root, forward
and backward.
o Thereby, the tree is recursive in nature..
Number of edges:
If there are n nodes, the number of edges in a tree is always n-1.
Each arrow in the tree represents a link or path.
These links are knows as edges.
Depth of node x:
The depth of node x can be defines as the length of the path from the root to the node x.
The depth of the node is the number of edges between the root and the node
Root node has 0 depth.
Types of Trees
Types of trees based on the number of children,
Based on the number of children, Trees are categoriezed as
Binary Tree
Ternary Tree
N-ary Tree
Binary Tree consists of following types based on the number of children:
o Full Binary Tree
o Degenerate Binary Tree
On the basis of completion of levels, the binary tree can be divided into following types:
o Complete Binary Tree
o Perfect Binary Tree
, o Balanced Binary Tree
Special types of trees based on nodes
Binary Search Tree
AVL Tree
Red Black Tree
B Tree
B+ Tree
Segment Tree
Implementation of Tree
Types of Binary Tree
Full Binary Tree
A full Binary tree is a special type of binary tree in which every parent node/internal node has either
two or no children.
Perfect Binary Tree
A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes
and all the leaf nodes are at the same level.
NON-LINEAR DATA STRUCTURES
Trees: Definition, Types of Trees, Operations of tree DS, Working etc.,
Binary Tree: Definition, Operations (Insertion, Deletion)
AVL Tree: Definition, Operations, rotation etc
M way tree, B Tree, B* Tree etc
Graph – Definition, Types, Operations, Traversal, algorithms etc
Trees
In linear data structures (arrays, queues) data are stored sequentially.
Factors involved in considering the right data structure:
1) What type of data are stored?
2) Cost of operations involved.
3) Efficient Memory usage.
A tree is one of the data structures that represents hierarchical data.
For Example:
Employees and their positions can be easily represented using tree structure.
The above figure represents Tree data structure. It is an upside-down tree, where the root is at the
top.
There are two direct reports for the root (one of the left and the other on the right).
Tree data structure is efficient to represent data of hierarchical nature and it consist of objects /
entities known as nodes.
In simple terms, tree is a non-linear data structure which is a collection of objects / entities that are
linked together to represent a tree structure.
Tree is a non linear data structure and consists of multiple levels.
Each node can contain any type of data.
Nodes that follow are called children.
,Basic Terminologies of a tree structure:
Root :
The topmost node in the tree hierarchy.
Root doesn’t have a parent.
If a node is directly connected to some other node, they are said to have parent child relationship.
Child node:
If a node is a descendant of any other node, it is known as child node.
Parent:
If a node contains any subnode, then that node is knows as the parent of the sub node.
Sibling:
Nodes that have same parent are called siblings.
Leaf Node:
A node of the tree, that doesn’t have any child node is called a leaf node.
Leaf node is generally at the bottom of the tree.
Leaf nodes are also called as external nodes.
Internal node:
A node that has atleast one child is knows as Internal node
Ancestor node:
It is that node that are predecessors node on the path from the root till the node.
In the above example, nodes 1,2,5 are ancestor of node 10.
Descendant:
The immediate successor of a given node is known as the descendant of a node.
Properties of a Tree Data Structure
Recursive data structure
,o However, is the depth of a tree, the tree can be traversed thoroughly only through the root, forward
and backward.
o Thereby, the tree is recursive in nature..
Number of edges:
If there are n nodes, the number of edges in a tree is always n-1.
Each arrow in the tree represents a link or path.
These links are knows as edges.
Depth of node x:
The depth of node x can be defines as the length of the path from the root to the node x.
The depth of the node is the number of edges between the root and the node
Root node has 0 depth.
Types of Trees
Types of trees based on the number of children,
Based on the number of children, Trees are categoriezed as
Binary Tree
Ternary Tree
N-ary Tree
Binary Tree consists of following types based on the number of children:
o Full Binary Tree
o Degenerate Binary Tree
On the basis of completion of levels, the binary tree can be divided into following types:
o Complete Binary Tree
o Perfect Binary Tree
, o Balanced Binary Tree
Special types of trees based on nodes
Binary Search Tree
AVL Tree
Red Black Tree
B Tree
B+ Tree
Segment Tree
Implementation of Tree
Types of Binary Tree
Full Binary Tree
A full Binary tree is a special type of binary tree in which every parent node/internal node has either
two or no children.
Perfect Binary Tree
A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes
and all the leaf nodes are at the same level.
