Module 4
TREES : Binary Search Trees, Selection Trees, Forests, Representation
of disjoint sets, Counting Binary Trees.
GRAPHS : The Graph Abstract Data Types, Elementary Graph
Operations
Binary Search Trees
Binary Search Tree is a binary tree. It may be empty. If it is not empty
then it satisfies the following properties.
1. Each node has exactly one key and the keys in the tree are distinct.
2. The keys(if any) in the left subtree are smaller than the key in the
root.
3. The keys(if any) in the right subtree are greater than the key in the
root.
4. The left and right subtrees are also BST.
Binary Search Trees
Example
Binary Search Trees
Searching a Binary Search Tree
1. Suppose we wish to search for a node whose key is k.
2. The searching should begin from root node, if the root node is
NULL then the BST contains no nodes and the search is
unsuccessful.
3. Otherwise we compare the key with root. If they are equal means
the search terminated successfully.
4. If k is less than root we have to search to left subtree of the root.
5. If k is greater than root we have to search to right subtree of the
root.
Searching a Binary Search Tree(Recursive)
element* search(treePointer root, int k)
{
if(!root)
return NULL;
if(k==root->key)
return &(root->key);
if(k < root->key)
return search(root->leftChild,k);
else
return search(root->rightChild,k);
}
Searching a Binary Search Tree(Iterative)
element* iterSearch(treePointer tree, int k)
{
while(tree)
{
if(k==tree->key)
return (tree->key);
if(k < tree->key)
tree=tree->leftChild;
else
tree=tree->rightChild;
}
return NULL;
}
Inserting into a Binary Search Tree
Inserting into a Binary Search Tree
Inserting into a Binary Search Tree
Inserting into a Binary Search Tree
• To insert a new node to BST we need to do a search to the tree, if the search is unsuccessful then we
insert the node at the point where the search terminated.
void insert(treePointer *node, int k)
{
treePointer ptr;
temp=modifiedSearch(*node,k); // it returns a pointer to the last node of the tree
ptr=malloc(ptr,sizeof(ptr));
ptr->key=k;
ptr->leftChild=ptr->rightChild=NULL;
if(k < temp->key)
temp->leftChild=ptr;
else
temp->rightChild=ptr;
}
Deletion from a Binary Search Tree
Deletion of leaf is quite easy. Consider the example above, there leftChild of
parent should set as NULL and the node should be freed.
Deletion from a Binary Search Tree
Deletion of a nonleaf that has a single child node is also simple in BST. Copy
the child to the node and free the node
Deletion from a Binary Search Tree
When a node to be deleted is a nonleaf node with 2 children then it can be replaced either
by the largest node in the left subtree or the smallest one in the right subtree.
OR
Find the inorder successor of the node. Copy contents of the inorder successor to the node,
and delete the inorder successor. Otherwise find the inorder predecessor of the node. Copy
contents of the inorder predecessor to the node, and delete the inorder predecessor
FORESTS
A forest is a set of n>=0 disjoint trees.
• The concept of forest is very close to tree. Because if we remove the root of a
tree we will get forests.
• Eg : removing root of a binary tree will produce a forest of 2 trees.
Converting forests to binary tree
FOREST TRAVERSALS
FOREST PREORDER TRAVERSAL
FOREST INORDER TRAVERSAL
FOREST POSTORDER TRAVERSAL
Converting forests to binary tree
• If T1,T2, ……Tn is a forest of trees then binary tree corresponding
to this forest is denoted by B(T1,T2, ……Tn ).
Is empty if n=0.
Has root equal to root(T1)
Has left subtree is equal to B(T11, T12,….T1m)where T11, T12,
….T1m are subtrees of root(T1)
Has right subtree B(T2,T3,…..Tn)
SELECTION TREE
• It a complete binary tree with n external nodes and n – 1 internal nodes.
The external nodes represent the players, and the internal nodes are
representing the winner OR loser of the match between the two players.
• There are 2 kinds of selection trees
1. Winner Tree
2. Loser Tree
SELECTION TREE – Winner Tree
• Winner tree is a complete binary tree in which each node represents the
smaller of its two children.
SELECTION TREE – Winner Tree
• The root node represent the smallest node in the tree.
• Construction of winner tree may be compared to the playing
of tournament in which winner is recorded with the smaller
key.
• Each leaf node represents first record in the corresponding
run.
SELECTION TREE – Loser Tree
A selection tree in which non leaf node retains a pointer to the loser is
called a loser tree
.
REPRESENTATION OF DISJOINT SETS
• How we can make use of trees to represent sets.
• Assume sets being represented are disjoint
• For Example : S1={0,6,7,8}, S2={1,4,9} S3={2,3,5}
• Consider the possible representation of these trees using sets.
• Here we have linked the nodes from the children to parent
REPRESENTATION OF DISJOINT SETS
Union Operation and Find Operation
• Union
Si U Sj= {All elements x such that x is either in Si or in Sj}
• Find(i)
Find the set containing element i. Eg : 3 is in S3 and 8 is in S1.
REPRESENTATION OF DISJOINT SETS
Union Operation and Find Operation
For performing union
operation we simply make one
of the tree as subtree of other.
REPRESENTATION OF DISJOINT SETS
Data Representation and Array representation of S1 , S2 and S3
REPRESENTATION OF DISJOINT SETS
int simpleFind(int i)
{
for( ; parent[i]>=0 ; i=parent[i] )
;
return i;
}
void simpleUnion(int i, int j)
{
parent[i]=j;
}
COUNTING BINARY TREE
DISTINCT BINARY TREE
• We know that if n=0 or n=1 then there is only 1 binary tree.
• If n=2 then there are 2 distinct trees.
• If n=3 then there are 5 distinct binary trees
Constructing tree from tree traversals
Constructing tree from tree traversals
• Postorder Traversal : 10 , 30 , 20 , 150 , 300 , 200 , 100
• Inorder Traversal : 10 , 20 , 30 , 100 , 150 , 200 , 300 Construct the
tree
Constructing tree from tree traversals
1. Inorder Traversal – H F A P G
Pre order Traversal – A H F G P
2. Inorder Traversal –F D B E A C
Post order Traversal – F D E B C A
GRAPHS
• Graph G consist of 2 sets V and E.
• V - Finite non empty set of vertices
• E - Set of pairs of vertices. These pairs are called edges.
• We will also write G = (V , E) to represent a graph.
GRAPHS
Graphs can be classified into directed and undirected.
Undirected Graph
In undirected graphs the pair of vertices representing any edge is unordered.
Thus (u,v) and (v,u) represent the same edge.
0
1 3 Here
V(G)={0,1,2,3}
E(G)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
2
GRAPH
Directed Graph
In directed graph each edge is represented by directed pair <u,v>
u – is the head of the edge
v – is the tail of the edge
So in directed graph <u,v> and <v,u> represent two different edges.
A
Here
B D V(G)={A,B,C,D}
E(G)={(A,B),(B,D),(D,A),(D,C),(C,B),(B,D)}
C
Restrictions impose on graph
• A graph may not have an edge from vertex v back to itself.
That is edges of the form (v, v) are not legal.
Such edges are known as self edges or self loops.
The graphs containing such edges are known as
Graphs with self loop .
• A graph may not have multiple occurrences of same
edge. If we remove this restriction we will get
multigraph. (A graph with multiple occurrences of the
same edge is called a multigraph)
Complete Graph
In complete graph all pairs of vertices are connected by an edge. An
undirected graph with n vertices and exactly n(n-1)/2 edges is said to be
a complete graph.
Adjacent Vertex
If (u,v) is an edge in E(G), then we say that the vertices u and v are adjacent and
the edge(u,v) is incident on vertices u and v.
0
A
1 3
B D
2
C
Example : In the undirected Example : In directed graph above <D,A> is
graph above the vertices a directed edge the vertex D is adjacent to
adjacent to 3 are 0,1,2. The vertex A and vertex A is adjacent from D.
edges incident on vertex 3 are Here the vertex incident to vertex A are
(0,3) ,(1,3) and (2,3) <D,A> and <A,B>
Path
• A path from vertex u to v in graph g is a sequence of vertices
u ,i1, i2, ……. ik, v such that (u, i1),(i1, i2)………(ik,v) are edges in E(G).
• If G is directed then the path consists of <u, i 1 >,< i1, i2 >………< ik,v>
edges in E(G’).
• The length of the path is the number of edges in it.
Example
The path from B to D is
(B,C),(C,D). The length of the
path is 2
Simple Path
A simple path is a path in which all the vertices are distinct.
Example : (B,A),(A,E),(E,C)
Cycle
A cycle is a simple path in which all the vertices except the first and last vertices
are distinct. Otherwise the first and the last vertices are same.
Example :
(B,C),(C,D)(D,E)(E,A)(A,B) is a cycle
Degree of a vertex
• In a undirected graph degree of a vertex is the number of edges incident
0
on a vertex
1 3
Example : degree(1)=3
2
• In a directed graph
in-degree : The number of edges that are coming into a vertex. Or for how
many number of edges v is the tail.
out degree : The number of edges for which v is the head i.e. the number of
edges that are going out of a vertex A
Example : in-degree(B)=2 out-degree(B)=1 B D
C
Subgraph
A subgraph of G is a graph G’ such that V(G’) V(G) and E(G’) E(G)
Example
Graph G Subgraph G’
Connected Graph
An undirected graph G is said to be connected if for every pair of distinct
vertices u and v in V(G) there is a path from u to v in G.
Strongly Connected
A directed graph G is said to be strongly connected if for every pair of
distinct vertices u and v in V(G), there is a directed path from u to v and
from v to u.
Tree
A tree is a connected acyclic connected graph.
Graph Representation
The three most commonly used representations are
Adjacency Matrix
Adjacency List
Adjacency Mult list
Adjacency Matrix
• Let G=(V,E) be a graph with n vertices, n>=1.
• The adjacency matrix of G is a two dimensional n*n array
• For example matrix A, with the property that A[i][j]=1 if there exist
one edge (i,j)(for a directed graph edge <i,j> ) is in E(G).
• If no such edge in graph then A[i][j]=0.
Adjacency Matrix
Adjacency Matrix
Adjacency Matrix
The space requirement to store an adjacency matrix is n 2 bits.
The adjacency matrix for a undirected graph is symmetric .About
half the space can be saved in an undirected graph by storing only the
upper or lower triangle of the matrix.
For an undirected graph the degree of any vertex i is its row sum. For
a directed graph the row sum is the out-degree and the column sum is
the in-degree.
Adjacency List
• In adjacency matrix the n rows of the adjacency matrix are represented as n
chains.
• There is one chain for each vertex in G.
• The nodes in chain i represent the vertices that are adjacent from vertex i.
The data field of a chain node stores the index of an adjacent vertex.
0
1 2
3
Adjacency List
0
1 3
2 The node Structure is
For an undirected graph with n vertices struct node
and e edges, the degree of any vertex {
in an undirected graph may be int vertex;
determined by counting the number of struct node * link;
nodes in the adjacency list. }
struct node *graph[max_vertices];
Adjacency Multilists
• For each edge there will be exactly one node, but this node will be in two
list(i.e., the adjacency list for each of the two nodes to which it is
incident).
• A new field is necessary to determine if the edge is determined and mark
it as examined
• The new node structure is
M Vertex1 Vertex2 Link1 Link2
Adjacency Multilists
Weighted Edges
• In many applications the edges of a graph have weight assigned to them.
• These weights may represent the distance from one vertex to another or the
cost for going from one vertex to an adjacent vertex.
• The adjacency matrix and list maintain the weight information also.
• A graph with weighted edges are also called network.
0 1 2 3 4
0 0 1 6 ∞ ∞
1 1 0 4 3 1
2 6 4 0 1 ∞
3 ∞ 3 1 0 1
4 ∞ 1 ∞ 1 0
Elementary Graph Operations
Given an undirected graph G = ( V, E ) and a vertex v in V(G) ,there are
two ways to find all the vertices that are reachable from v or are
connected to v .
Depth First Search
Breadth First Search
Depth First Search(DFS)
1. Visit the starting vertex v. (visiting consist of printing node’s vertex)
2. Select an unvisited vertex w from v’s adjacency and carry a depth first
search on w.
3. A stack is maintained to preserve the current position in v’s adjacency
list.
4. When we reach a vertex u that has no unvisited vertices on adjacency
list, remove a vertex from the stack and continue processing its
adjacency list. Previously visited vertices are discarded and unvisited
vertices are placed on stack
5. The search terminates when the stack is empty.
DFS -EXAMPLE
DFS -EXAMPLE
DFS -EXAMPLE
Depth First Search(DFS)-C Function
• This function uses a global array visited[MAX_VERTICES], that is
initialized to false when we visit vertex i we change visited[i]=TRUE
# define FALSE 0
# define TRUE 1
short int visited[max_vertices];
void dfs(int v)
{
visited[v]=TRUE;
printf(“%d”,v);
w=graph[v];
while(w!=NULL)
{
if(visited[w->vertex]==FALSE)
dfs(w->vertex);
w=w->link;
}
Breadth First Search(BFS)
1. Search starts at vertex v marks it as visited.
2. It then visits each of the vertices on v’s adjacency list.
3. As we visit each vertex it is placed on a queue.
4. When all the vertices in the adjacency list is visited, we remove a vertex
from the queue and proceed by examining each of the vertices in its
adjacency list.
5. Visited vertices are ignored and unvisited vertices are placed on the queue
6. The search terminates when the queue is empty.
Breadth First Search(BFS)-Example
Breadth First Search(BFS)-Example
Breadth First Search(BFS)-Example
Breadth First Search(BFS)-Example
Breadth First Search(BFS)
The queue definition and the function prototypes while(front)
struct node {
{ v=deleteq();
int vertex; w=graph(v);
struct node * link; while(w!=NULL)
}; {
typedef struct node queue; if(visited[w->vertex]==FALSE)
queue * front,*rear; {
int visited[max_vertics]; printf(“%d”,w->vertex);
void addq(int); addq(w->vertex);
int delete(); visited[w->vertex]=TRUE;
void bfs(int v) }
{ w=w->link;
front=rear=NULL; }
printf(“%d”,v); }
visited[v]= TRUE; }
addq(v);
VTUQstns
VTUQstns
VTUQstns
Qstns
1. Explain the Depth First Search traversal technique with an example.
Write a function for the same
2. Explain the Breadth First Search traversal technique with an example.
Write a function for the same.