Prepared By : Uday Shah (HOD -IT)
E-Mail : rupareleducation@gmail.com
Contact No : 7600044051
Data Structure : Unit 4 Tree
Definition
and concept of Tree
A tree is a collection of nodes connected by
directed or undirected edges. A tree is a nonlinear data
structure, compared to arrays, linked lists, stacks and queues which are linear
data structures. A tree can be empty with no nodes or a tree is a structure
consisting of one node called the root and zero or one or more subtrees.
Representation
of Binary Tree
In a normal tree, every node can have any number
of children. Binary tree is a special type of tree data structure in which
every node can have a maximum of 2 children. One is known as left child and the other is known as right
child.
A tree in which every node can have a maximum of
two children is called as Binary Tree.
In a binary tree, every node can have either 0
children or 1 child or 2 children but not more than 2 children.
Example
There are different types of binary trees and they
are...
1. Strictly Binary Tree
In a binary tree, every node can have a maximum
of two children. But in strictly binary tree, every node should have exactly
two children or none. That means every internal node must have exactly two
children. A strictly Binary Tree can be defined as follows...
A binary tree in which every node has either two
or zero number of children is called Strictly Binary Tree
Strictly binary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree
Strictly binary tree data structure is used to represent mathematical expressions.
2. Complete Binary Tree
In a binary tree, every node can have a maximum
of two children. But in strictly binary tree, every node should have exactly
two children or none and in complete binary tree all the nodes must have
exactly two children and at every level of complete binary tree there must be 2level number
of nodes. For example at level 2 there must be 22 = 4 nodes and
at level 3 there must be 23 = 8 nodes.
Binary Tree Traversals
When we wanted to display a binary tree, we need
to follow some order in which all the nodes of that binary tree must be
displayed. In any binary tree displaying order of nodes depends on the
traversal method.
Displaying (or) visiting order of nodes in a
binary tree is called as Binary Tree Traversal.
There are three types of binary tree traversals.
1. In - Order Traversal
2. Pre - Order Traversal
3. Post - Order Traversal
Consider the following binary tree...
1. In - Order Traversal ( leftChild - root
- rightChild )
In In-Order traversal, the root node is visited
between left child and right child. In this traversal, the left child node is
visited first, then the root node is visited and later we go for visiting right
child node. This in-order traversal is applicable for every root node of all
subtrees in the tree. This is performed recursively for all nodes in the tree.
That means here we have visited in the order of B - F - G - H - P - R - S - T - W - Y - Z using In-Order Traversal.
That means here we have visited in the order of B - F - G - H - P - R - S - T - W - Y - Z using In-Order Traversal.
2. Pre - Order Traversal ( root -
leftChild - rightChild )
In Pre-Order traversal, the root node is visited
before left child and right child nodes. In this traversal, the root node is
visited first, then its left child and later its right child. This pre-order
traversal is applicable for every root node of all subtrees in the tree.
That means here we have visited in the order
of P - F - B - H - G - S - R - Y - T - W - Z using Pre-Order Traversal.
3. Post - Order Traversal ( leftChild -
rightChild - root )
In Post-Order traversal, the root node is
visited after left child and right child. In this traversal, left child node is
visited first, then its right child and then its root node. This is recursively
performed until the right most node is visited.
Here we have visited in the order of B - G - H - F - R - W - T - Z - Y - S - P using Post-Order Traversal.
Here we have visited in the order of B - G - H - F - R - W - T - Z - Y - S - P using Post-Order Traversal.
Binary Search Tree
A Binary Search Tree (BST) is a tree in which all the nodes follow
the below-mentioned properties −
·
The left sub-tree of a node has a key less than or equal to its
parent node's key.
·
The right sub-tree of a node has a key greater than to its parent
node's key.
Thus,
BST divides all its sub-trees into two segments; the left sub-tree and the
right sub-tree
BST is a
collection of nodes arranged in a way where they maintain BST properties. Each
node has a key and an associated value. While searching, the desired key is
compared to the keys in BST and if found, the associated value is retrieved.
Following
is a pictorial representation of BST −
We
observe that the root node key (27) has all less-valued keys on the left
sub-tree and the higher valued keys on the right sub-tree.
Whenever an element is to be searched, start searching from
the root node. Then if the data is less than the key value, search for the
element in the left subtree. Otherwise, search for the element in the right
subtree.
·
Represent
organization
·
Represent
computer file systems
·
Networks to
find best path in the Internet
·
Chemical
formulas representation
·
Manipulate
hierarchical data.
·
Make
information easy to search (see tree traversal).
·
Manipulate
sorted lists of data.
·
As a workflow
for compositing digital images for visual effects.
·
Router
algorithms
·
Used in many search
applications where data is constantly entering/leaving,
Used in almost every
3D video game to determine what objects need to be rendered.
Graph and its representations
What is Graph? Basic Concept and Definition
·
Graph is an abstract data type.
·
It is a pictorial
representation of a set of objects where some pairs of objects are connected by
links.
·
Graph is used to implement the
undirected graph and directed graph concepts from mathematics.
·
It represents many real life
application. Graphs are used to represent the networks. Network includes path
in a city, telephone network etc.
·
It is used in social networks
like Facebook, LinkedIn etc.
·
Graph
consists of two following components:
1. Vertices
2. Edges
1. Vertices
2. Edges
·
Graph is a set of vertices (V)
and set of edges (E).
·
V is a finite number of
vertices also called as nodes.
·
E is a set of ordered pair of
vertices representing edges.
·
For example, in Facebook, each
person is represented with a vertex or a node. Each node is a structure and
contains the information like user id, user name, gender etc.
·
The above figures represent the
graphs. The set representation for each of these graphs are as follows:
·
Graph 1:
V = {A, B, C, D, E, F}
E = {(A, B), (A, C), (B, C), (B, D),(C, E),(D, E), (D, F), (E, F)}
V = {A, B, C, D, E, F}
E = {(A, B), (A, C), (B, C), (B, D),(C, E),(D, E), (D, F), (E, F)}
·
Graph 2:
V = {A, B, C, D, E, F}
E = {(A, B), (A, C), (B, D), (C, E), (C, F)}
Graph 3:
V = {A, B, C}
E = {(A, B), (A, C), (C, B)}
V = {A, B, C, D, E, F}
E = {(A, B), (A, C), (B, D), (C, E), (C, F)}
Graph 3:
V = {A, B, C}
E = {(A, B), (A, C), (C, B)}
Directed Graph
·
If a graph contains ordered
pair of vertices, is said to be a Directed Graph.
·
If an edge is represented using
a pair of vertices (V1, V2), the edge is said to be
directed from V1 to V2.
·
The first element of the pair V1 is
called the start vertex and the second element of the pair V2 is
called the end vertex.
Set of Vertices V = {1, 2, 3, 4, 5, 5}
Set of Edges W = {(1, 3), (1, 5), (2, 1), (2, 3), (2, 4), (3, 4), (4, 5)}
·
Undirected
Graph
·
If a graph contains unordered
pair of vertices, is said to be an Undirected Graph.
·
In this graph, pair of vertices
represents the same edge.
Set of Edges E = {(1, 2), (1, 3), (1, 5), (2, 1), (2, 3), (2, 4), (3, 4), (4, 5)}
·
In an undirected graph, the
nodes are connected by undirected arcs.
·
It is an edge that has no
arrow. Both the ends of an undirected arc are equivalent, there is no head or
tail.
Graph Traversal
·
Graph traversal is a process of
checking or updating each vertex in a graph.
·
It is also known as Graph
Search.
·
Graph traversal means visiting
each and exactly one node.
·
Tree traversal is a special
case of graph traversal.
·
There are two
techniques used in graph traversal:
1. Depth First Search
2. Breadth First Search
1. Depth First Search
2. Breadth First Search
·
Depth First Search
·
Depth first search (DFS) is
used for traversing a finite graph.
·
DFS traverses the depth of any
particular path before exploring its breadth.
·
It explores one subtree before
returning to the current node and then exploring the other subtree.
·
DFS uses stack instead of
queue.
·
It traverses a graph in a
depth-ward motion and gets the next vertex to start a search when a dead end
occurs in any iteration.
·
DFS does not go though all the
edges. The tree contains all the vertices of the graph if it is connected to
the nodes and is called as Graph Spanning Tree. Graph spanning tree is exactly
corresponds to the recursive calls of DFS.
·
If a graph is disconnected then
DFS will not be able to visit all of its vertices.
·
DFS will pop up all the
vertices from the stack which do not have adjacent nodes. The process is going
on until we find a node that has unvisited adjacent node and if there is no
more adjacent node, DFS is over.
·
Breadth First Search
·
Breadth first search is used
for traversing a finite graph.
·
It visits the neighbor vertices
before visiting the child vertices.
·
BFS uses a queue for search
process and gets the next vertex to start a search when a dead end occurs in
any iteration.
·
It traverses a graph in a
breadth-ward motion.
·
It is used to find the shortest
path from one vertex to another.
·
The main purpose of BFS is to
traverse the graph as close as possible to the root node.
·
BFS is a different approach for
traversing the graph nodes.
Spanning
Tree
A spanning tree is a subset of Graph G,
which has all the vertices covered with minimum possible number of edges.
Hence, a spanning tree does not have cycles and it cannot be disconnected..
By this definition, we can draw a
conclusion that every connected and undirected Graph G has at least one spanning
tree. A disconnected graph does not have any spanning tree, as it cannot be
spanned to all its vertices.
We found three spanning trees off one
complete graph. A complete undirected graph can have maximum number
of spanning trees.
General Properties of Spanning Tree
One graph can have more than one spanning
tree. Following are a few properties of the spanning tree connected to graph
·
A connected graph can have more than one spanning tree.
·
All possible spanning trees of
graph, have the same number of edges and vertices.
·
The spanning tree does not have
any cycle (loops).
·
Removing one edge from the
spanning tree will make the graph disconnected, i.e. the spanning tree is minimally
connected.
·
Adding one edge to the spanning
tree will create a circuit or loop, i.e. the spanning tree is maximally
acyclic.
Application of Spanning Tree
Spanning tree is basically used to find a
minimum path to connect all nodes in a graph. Common application of spanning
trees are −
·
Civil Network Planning
·
Computer Network Routing
Protocol
·
Cluster Analysis
Let us understand this through a small
example. Consider, city network as a huge graph and now plans to deploy
telephone lines in such a way that in minimum lines we can connect to all city
nodes. This is where the spanning tree comes into picture.
Minimum Spanning Tree (MST)
In a weighted graph, a minimum spanning
tree is a spanning tree that has minimum weight than all other spanning trees
of the same graph. In real-world situations, this weight can be measured as
distance, congestion, traffic load or any arbitrary value denoted to the edges.
Shortest-paths is a broadly useful problem-solving model
• Maps
• Robot navigation.
• Texture mapping.
• Typesetting in TeX.
• Urban traffic planning.
• Optimal pipelining of VLSI chip.
• Subroutine in advanced algorithms.
• Telemarketer operator scheduling.
• Routing of telecommunications messages.
• Approximating piecewise linear functions.
• Network routing protocols (OSPF, BGP, RIP).
• Exploiting arbitrage opportunities in currency exchange.
• Optimal truck routing through given traffic congestion pattern.
Following is an Example for Shortest Path.
According to above example here we try to find out shortest way to
reach with starting point to ending point.
There are number of
possibility to reached there destination point but we have to find a path that
we have to reached fast and safe.
Dijkstra and Greedy Both algorithm try to find a path in shortest
way.
Dijkstra algorithm is very small to understand the path to find the destination.
Below are the detailed steps used in Dijkstra’s algorithm to find
the shortest path from a single source vertex to all other vertices in the
given graph.
Algorithm
·
Create a set shortest path tree that keeps track of
vertices included in shortest path tree.
·
Assign a distance value to all vertices in the input graph.
·
Initialize all distance values as INFINITE.
·
Assign distance value as 0 for the source vertex so that it is
picked first.
·
While shortest path tree doesn’t include all vertices
·
Pick a vertex v which is not there in shortest path tree and
has minimum distance value.
·
Include vertex v to shortest path tree.
·
Update distance value of all adjacent vertices of v.
:: Best Of Luck ::
https://myshopprime.com/uday.shah3/shop
Please share and comment it... Thank you.
