Scribd
Upload
22 views20 pages

M4 Notes - PART-1

Uploaded by

sumukhchavan6
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
22 views20 pages

M4 Notes - PART-1

Uploaded by

sumukhchavan6
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 20

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

Define binary search tree


It is a binary tree. It may be empty. If it is not empty then it satisfies the following
properties:
1. Every element has a unique key
2. The keys in the left subtree are smaller than the root.
3. The keys in the right subtree are larger than the root.
4. The left and right sub trees are also binary search trees.

For the given data draw a binary search tree and show the array and linked
representation of the same 100, 85, 45, 55, 110 , 20, 70, 65
Operations on a Binary Search Tree
The following operations are performed on a binary search tree...
 Search
- Recursive
- Iterative
 Insertion
 Deletion
 Traversal

For searching a given key in the BST,

 Compare the key with the value of root node.


 If the key is present at the root node, then return the root node.
 If the key is greater than the root node value, then recur for the root
node’s right subtree.
 If the key is smaller than the root node value, then recur for the root
node’s left subtree.

What is binary search tree ? Write algorithm to implement for


recursive search or iterative search for a binary search tree

Recursive search
struct node *search(struct node *root, int key)
{
if(root==NULL)
{
printf("key not found\n");
}
else if(key < root->data) /*search in left subtree*/
return search(root->left, key);
else if(key > root->data) /*search in right subtree*/
return search(root->right,key);
else
printf("Key found\n");
return root;
}
Iterative search

struct node *search(struct node *root, int key)


{
while (root)
{
if (key == root->data)
return root;
if (key < root->data)
root = root->left;
else
root = root->right;
}
return NULL;
}

Inserting into a Binary Search Tree

Firstly create a node using malloc function and assign a key value to it.
If tree is empty initially then the newly created node becomes the first
node in the tree.

(a) Compare ITEM with the root node N of the tree.


(i) If ITEM < Node, proceed to the left child of N.
(ii) If ITEM > Node, proceed to the right child of N.

(b) Repeat Step (a) until one of the following occurs:


(i) We meet a node N such that ITEM = N. In this case the search is
successful.
(ii) We meet an empty subtree, which indicates that the search is
unsuccessful, and we insert ITEM in place of the empty subtree.
Write a function to insert an item into an ordered binary search
tree (duplicate items are not allowed)

struct node *insert(struct node *root, int item)


{
if(root == NULL)
{
root = (struct node *)malloc(sizeof(struct node));
root->left = root->right = NULL;
root->data = item;
return root;
}
else if(item < root->data )
root->left = insert(root->left,item);
else if(item > root->data )
root->right = insert(root->right,item);
else
printf(" Duplicate Element !! Not Allowed !!!");
return(root);
}
}

Deletion Operation in BST

Deleting a node from Binary search tree has following three cases...
Case 1: Deleting a Leaf node (A node with no children)
Case 2: Deleting a node with one child
Case 3: Deleting a node with two children
Joining and splitting binary tree

ThreeWayJoin(small,mid,big): this creates a binary search tree


consisting of the pairs initially in the binary search trees small and
big, as well as the pair mid.
TwoWayJoin(small, big):
This joins the two binary search trees small and big to obtain a single
binary search tree that contains all the pairs originally in small and
big.

Splitting binary Search tree


Split(k,small,mid,big): BST is split into three parts: –
small: a BST that contains all pairs that have key less than k
mid: the pair contains the key k
big: a BST that contains all pairs that have key larger than k
BST applications

1. Databases: Many database systems use BSTs for indexing data, which allows
for fast retrieval of records based on keys.
2. Symbol Tables: Compilers and interpreters use BSTs to store and search for
identifiers (e.g., variable names) efficiently.
3. File Systems: BSTs are employed in file systems to organize directory
structures and quickly locate files.
4. Caches: In computer architecture, BSTs are used in caches to efficiently
manage and search for cached data.
5. Network Routing: Routing tables in network routers often use BSTs for efficient
routing decisions.

Example: -1 Construct binary tree from the traversal order given


below.
preorder A B D E F C G H
Inorder D B F E A G C L

Example: -2

Preorder : 5-3-2-4-8-6-10
Inorder : 2-3-4-5-6-8-10

Solution:

1) find the root of tree from given preorder traversal


2) check left and right nodes from inorder traversal
Given
inorder sequence: DJGBHEAFKIC and
postorder sequence : JGDHEBKIFCA construct binary tree and
give preorder traversal.
SELECTION TREE Refer class
FORESTS notes
REPRESENTATION OF DISJOINT SETS
COUNTING BINARY TREES

GRAPHS: The Graph Abstract Data Types, Elementary Graph


Operations.

Graph

Graph is a pair of sets (V, E), where V is the set of vertices and E is
the set of edges, connecting the pairs of vertices. G=(V,E)

Ex:

Graph Classifications
There are several common kinds of graphs
 Weighted or un weighted
 Directed or For undirected
 Cyclic or acyclic
 Multi graphs

Weighted graph: edges have a weight


 Weight typically shows cost of traversing
 Example: weights are distances between cities
Unweighted graph: edges have no weight Edges simply show
connections.

Undirected Graph: no implied direction on edge between nodes

Directed Graphs
Digraph: A graph whose edges are directed
o Edge drawn as arrow
o Edge can only be traversed in direction of arrow
o Example: E = {(A,B), (A,C), (A,D), (B,C), (D,C)}
Degree of a Node
The degree of a node is the number of edges incident on it.
In-degree: Number of edges pointing to a node
Out-degree: Number of edges pointing from a node

inDegree of B is 1
Out Degree of b is 1

Self edge(self loops) : A selft loop is an edge which starts and ends
are the same vertex.

Complete graph: a Graph G=(V,E) is said to be a complete graph if


there exists an edge between every pair of vertices.
Multi graph: A graph with self loops and parallel edges is called a
multi graph.

Representing graphs:
 Adjacency lists
 Adjacency matrix

Adjacency lists

It is a way in which graphs can be represented in the computer’s


memory.
Let G=(V,E) be a graph . An adjacency linked list is an array of ‘n’
linked lists where n is the number of vertices in graph G.
Each location of the array gives a vertex of the graph
Adjacency Matrix:
Let G=(V,E) be a graph . Let N be the number of vertices in graph G .
The adjacency matrix a of a graph g is defined as :

A[i][j] = 1 if there exists an edge from


vertex i to j
0 if there is no edge from i to j .

It is a Boolean square matrix with n rows and n columns with entries


1’s and 0’s
Example:2 Adjacency Matrix representation
Example :2 Adjacency lists representation
Abstract data type Graph
Abstract data type Graph

Graph Traversals --> BFS & DFS


Breadth First Search Breadth First Search (BFS) algorithm traverses a
graph in a breadthward motion and uses a queue to remember to get
the next vertex to start a search.

BFS Algorithm :

Step1 − Visit the adjacent unvisited vertex. Mark it as visited. Display


it. Insert it in a queue.

Step 2 − If no adjacent vertex is found, remove the first vertex from


the queue.

Step 3 − Repeat Rule 1 and Rule 2 until the queue is empty.


Depth First Search: Depth First Search (DFS) algorithm traverses a
graph in a depthward motion and uses a stack to remember to get the
next vertex to start a search

DFS Algorithm :

Step 1 − Visit the adjacent unvisited vertex. Mark it as visited.


Display it. Push it in a stack.

Step 2 − If no adjacent vertex is found, pop up a vertex from the


stack. (which do not have adjacent vertices.)

Step 3 − Repeat Rule 1 and Rule 2 until the stack is empty.


Biconnected Components And Articulation Points

An articulation point is a vertex v of G such that the deletion of v,


together with all edges incident on v, produces a graph, G', that has at
least two connected components

A biconnected component of a connected undirected graph is a


maximal biconnected subgraph.

You might also like