What is hashing technique? Describe in
brief.
In
general, in all searching techniques, search time is dependent on the number of
items. Sequential search, binary search and all the search trees are totally
dependent on number of items and many key comparisons are involved.
Hashing
is a technique where search time is independent of the number of items or
elements. In this technique a hash function is used to generate an address from
a key. The hash function takes a key as input and returns the hash value of
that key which is used as an address index in the array.
We
can write hash function as follows
h(k)=a;
Where
h is hash function, k is the key, a is the hash value of the key.
While
choosing a hash function we should consider some important points.
- It should be easy to compute
- It should generate address with minimum
collision.
What are different techniques for
making hash function? Explain with example.
Techniques
for making hash function.
- Truncation Method
- Midsquare Method
- Folding Method
- Division Method
Truncation
Method
This
is the simplest method for computing address from a key.In this method we take
only a part of the key as address.
Example:
Let
us take some 8 digit keys and find addresses for them. Let the table size is
100 and we have to take 2 rightmost digits for getting the hash table address.
Suppose the keys are. 62394572,87135565,93457271,45393225.
So
the address of above keys will be 72,65,71 and 25 respectively.
This
method is easy to compute but chances of collision are more because last two
digits can be same in more than one keys.
Midsquare
Method
In
this method the key is squared and some digits from the middle of this square
are taken as address.
Example:
Suppose
that table size is 1000 and keys are as follows
Key
|
1123
|
2273
|
3139
|
3045
|
Square
of key
|
1261129
|
5166529
|
9853321
|
9272025
|
Address
|
612
|
665
|
533
|
720
|
Folding Method
In
this technique the key is divided into different part where the length of each
part is same as that of the required address, except possibly the last part.
Example:
Let
key is 123945234 and the table size is 1000 then we will broke this key as
follows
123945234
----> 123 945 234
Now
we will add these broken parts. 123+945+234=1302. The sum is 1302, we will
ignore the final carry 1, so the address for the key 123945234 is 302.
Division
Method (Modulo-Division)
In
Modulo-Division method the key is divided by the table size and the remainder
is taken as the address of the hash table.
Let
the table size is n then
H
(k) =k mod n
Example
Let
the keys are 123, 945,234 and table size is 11 then the address of these keys
will be.
123
% 11=2
945%11=10
235%11=4
So
the hash address of above keys will be 2,10,4.
Note:
- Collisions can be minimized if the table size is taken to be a prime number.
What are different methods of collision
resolution in hashing.
A
collision occurs whenever a key is mapped to an address that is already
occupied. Collision Resolution technique provides an alternate place in hash
table where this key can be placed. Collision Resolution technique can be
classified as:
1)
Open Addressing (Closed Hashing)
a)
Linear Probing
b) Quadratic Probing
c) Double Hashing
2)
Separate Chaining (Open Hashing)
Describe Linear Probing with an
example.
In
this method if address given by hash function is already occupied, then the key
will be inserted in the next empty position in hash table. Let the table size
is 7 and hash function returns address 4 for a key then we will search the
empty location in this sequence.
4,
5, 6, 7, 0, 1, 2, 3
Example:
Let
the keys are 28, 47, 20, 36, 43, 23, 25, 54 and table size is 11 then
Describe the following term in a tree.
a)
Level b) Height c) Degree.
Let’s
take an example to define the above term.
Level:
Level
of any node is defined as the distance of that node from the root. The level of
root node is always zero. Node B, C, M, E are at level 1.Nodes K,G,H,I,J,F,L
are at level 2.Nodes A,N,O,P,D,S are at level 3.
Height:
Height
is also known as depth of the tree. The height of root node is one. Height of a
tree is equal to one more than the largest level number of tree. The height of
the above tree is 4.
Degree:
The
number of children of a node is called its degree. The degree of node R is 4,
the degree of node B is 3.The degree of node S is 0.The degree of a tree is the
maximum degree of the node of the tree. The degree of the above given tree is
4.
Describe binary tree and its property.
In a
binary tree a node can have maximum two children, or in other words we can say
a node can have 0,1, or 2 children.
Properties
of binary tree.
1)
The maximum number of nodes on any level i is 2i where i>=0.
2)
The maximum number of nodes possible in a binary tree of height h is 2h-1.
3)
The minimum number of nodes possible in a binary tree of height h is equal to
h.
4)
If a binary tree contains n nodes then its maximum possible height is n and
minimum height possible is log2 (n+1).
5)
If n is the total no of nodes and e is the total no of edges then e=n-1.The
tree must be non-empty binary tree.
6)
If n0 is the number of
nodes with no child and n2 is
the number of nodes with 2 children, then n0=n2+1.
Describe full binary tree and complete
binary tree.
Full
binary tree: A binary tree is full binary tree if all the levels have maximum
number of nodes.
A
full binary tree of height h has (2h– 1) nodes.
Complete
binary tree:In a complete binary tree all the levels have maximum number of
nodes except possibly the last level.
The
minimum no of nodes in a complete binary tree is 2h-1and the maximum
number of nodes possible is (2h– 1).Where h is the height of the
tree.
Explain Extended Binary tree.
A
binarytree can be converted to an extended binary tree by adding special nodes
to leaf nodes and nodes that have only one child.Extended binary tree is also
called 2-tree.
In
the above figure external nodes are shown by squares and internal nodes by
circles. The extended binary tree is a strictly binary tree means each node has
either 0 or 2 children. The path length of any node is the number of edges
traversed from that node to the root node. Internal path length of a binary
tree is the sum of path lengths of all internal nodes and external path length
of a binary tree is the sum of path lengths of all external nodes.
What are different dynamic memory
allocation technique in C .
The
process of allocating memory at run time is called dynamic memory allocation.
The allocation and release of this memory space can be done with the help of
some predefined function. These functions allocate memory from a memory area
called heap and free this memory whenever not required. The functions that are
used to allocate memory at runtime are as follows:
-
malloc()
- calloc()
- realloc()
1.
malloc()
This
function allocates memory dynamically. It is generally used as:
ptr=
(datatype *) malloc(specified size);
Here
ptr is a pointer of type datatype ( can be int, float, double….) and specified
size is the size in bytes. The expression (datatype *) is used to typecast the
pointer returned by malloc().
Example:
int
*ptr;
ptr=(int *)malloc(4*sizeof(int));
It
allocates the memory space to hold four integer values and the address of first
byte is stored in the pointer variable ptr. The allocated memory contains
garbage value.
2.
calloc()
The
calloc() function is used to allocate multiple blocks of memory.
Example:
int *ptr;
ptr=(int *)calloc(4, sizeof(int));
It allocates 4 blocks of memory and each block contains 2 bytes.
3.
realloc()
We
can increase or decrease the memory allocated by malloc() or calloc() function.
The realloc() function is used to change the size of the memory block. It
changes the memory block without destroying the old data.
Example:
int
*ptr;
ptr=(int *)malloc(4*sizeof(int));
ptr=(int *)realloc(ptr,newsize);
This function takes two argument, first is a pointer to the block of memory
that was previously allocated by malloc() or calloc() and second argument is
the new size of memory block.
ptr=(int *)realloc(ptr, 4*sizeof(int)); // newsize
Q.2 What are the difference between
malloc() and calloc()?
Following
are the main difference between malloc() and calloc().
-
calloc() function takes two parameters but malloc() function takes only one
parameter.
-
Memory allocated by calloc() is initialized to zero while memory allocated by
malloc() contains garbage value.
Q.3 How will you free the memory that is
allocated at run time?
Memory
is one of the most important resources and it is limited. The dynamically
allocated memory is not automatically released; it will exist till the end of
program. So it is programmer’s responsibility to free the memory after completion.
The free() function is used to release the memory that is allocated at run
time.
Example:
free(ptr);
Here ptr is a pointer variable that contains the base address of a memory block
created by malloc() or calloc() function.
Q.4 What are different application of
stack.
Some
of the applications of stack are as follows:
-
Function calls.
- Reversal of a string.
- Checking validity of an expression containing nested parenthesis.
- Conversion of infix expression to postfix.
Q.5 How will you check the validity of
an expression containing nested parentheses?
One
of the applications of stack is checking validity of an expression containing
nested parenthesis. An expression will be valid if it satisfies the two
conditions.
-
The total number of left parenthesis should be equal to the total number of
right parenthesis in the expression.
-
For every right parenthesis there should be a left parenthesis of the same
time.
The
procedure for checking validity of an expression containing nested parenthesis:
1.
First take an empty stack
2. Scan the symbols of expression from left to right.
3. If the symbol is a left parenthesis then push it on the stack.
4. If the symbol is right parenthesis then
If the stack
is empty then the expression is invalid because Right parentheses are
more
than left
parenthesis.
else
Pop an
element from stack.
If popped
parenthesis does not match the parenthesis being scanned then it is invalid
because of
mismatched parenthesis.
5.
After scanning all the symbols of expression, if stack is empty then expression
is valid else it is invalid because left parenthesis is more than right
parenthesis.
Q.6 Give the example of validating the
parenthesis of expression using stack.
Q.7 Describe AVL tree or height
balanced binary search tree.
An
AVL tree is binary search tree (BST) where the difference in the height of left
and right subtrees of any node can be at most one. The technique for balancing
the binary search tree was introduced by Russian Mathematicians G. M. Adelson
and E. M. Landis in 1962. The height balanced binary search tree is called AVL
tree in their honor.
Example:
For
the leaf node 12, 40, 65 and 98 left and right subtrees are empty so difference
of heights of their subtrees is zero.
For
node 20 height of left subtree is 2 and height of right subtree is 3 so
difference is 1.
For
node 15 height of left subtree is 1 and height of right subtree is 0 so
difference is 1.
For
node 57 height of left subtree is 1 and height of right subtree is 2 so
difference is 1.
For
node 78 height of left subtree is 1 and height of right subtree is 1 so
difference is 0.
Each
node of an AVL tree has a balance factor, which is defined as the difference
between the heights of left subtree and right subtree of a node.
Balance
factor of a node=Height of its left subtree - Height of its right subtree.
In
AVL tree possible values for the balance factor of any node are -1, 0, 1.
Q.8 Describe Tree Rotation in AVL tree.
After
insertion or deletion operation the balance factor of the nodes in AVL tree can
be changed and the tree may not be balanced. We can balance this tree by
performing tree rotations. We know that AVL tree is binary search tree.
Rotation of the tree should be in such a way that the new converted tree
maintain the binary search tree property with inorder traversal same as that of
the original tree. There are two types of tree rotation
-
Right Rotation
- Left Rotation
Fig:
Right Rotation
Q.9 Give one example of Right Rotation.
Right
Rotation about node 25.
Thanks .. nice programs for beginners. Here are few more data structure programs for beginners.
ReplyDelete