UNIT-3

Trees-II

Red - Black Tree

Red - Black Tree is another variant of Binary Search Tree in which every node is colored either RED or

BLACK. We can define a Red Black Tree as follows...

Red Black Tree is a Binary Search Tree in which every node is colored either RED or BLACK.

In Red Black Tree, the color of a node is decided based on the properties of Red-Black Tree. Every Red

Black Tree has the following properties.

Properties of Red Black Tree

 Property #1: Red - Black Tree must be a Binary Search Tree.

 Property #2: The ROOT node must be colored BLACK.

 Property #3: The children of Red colored node must be colored BLACK. (There should not be two

consecutive RED nodes).

 Property #4: In all the paths of the tree, there should be same number of BLACK colored nodes.

 Property #5: Every new node must be inserted with RED color.

 Property #6: Every leaf (e.i. NULL node) must be colored BLACK.

Example

Following is a Red-Black Tree which is created by inserting numbers from 1 to 9.

The above tree is a Red-Black tree where every node is satisfying all the properties of Red-Black Tree.

Every Red Black Tree is a binary search tree but every Binary Search Tree need not be Red Black tree.
Insertion into RED BLACK Tree

In a Red-Black Tree, every new node must be inserted with the color RED. The insertion operation in Red

Black Tree is similar to insertion operation in Binary Search Tree. But it is inserted with a color property.

After every insertion operation, we need to check all the properties of Red-Black Tree. If all the properties

are satisfied then we go to next operation otherwise we perform the following operation to make it Red

Black Tree.

 1. Recolor

 2. Rotation

 3. Rotation followed by Recolor

The insertion operation in Red Black tree is performed using the following steps...

 Step 1 - Check whether tree is Empty.

 Step 2 - If tree is Empty then insert the newNode as Root node with color Black and exit from the

operation.

 Step 3 - If tree is not Empty then insert the newNode as leaf node with color Red.

 Step 4 - If the parent of newNode is Black then exit from the operation.

 Step 5 - If the parent of newNode is Red then check the color of parentnode's sibling of newNode.

 Step 6 - If it is colored Black or NULL then make suitable Rotation and Recolor it.

 Step 7 - If it is colored Red then perform Recolor. Repeat the same until tree becomes Red Black

Tree.

Example
Deletion Operation in Red Black Tree

The deletion operation in Red-Black Tree is similar to deletion operation in BST. But after every deletion

operation, we need to check with the Red-Black Tree properties. If any of the properties are violated then

make suitable operations like Recolor, Rotation and Rotation followed by Recolor to make it Red-Black

Tree.

Splay Tree

Splay tree is another variant of a binary search tree. In a splay tree, recently accessed element is placed at

the root of the tree. A splay tree is defined as follows...

Splay Tree is a self - adjusted Binary Search Tree in which every operation on element rearranges the

tree so that the element is placed at the root position of the tree.
In a splay tree, every operation is performed at the root of the tree. All the operations in splay tree are
involved with a common operation called "Splaying".
Splaying an element, is the process of bringing it to the root position by performing suitable rotation
operations.
In a splay tree, splaying an element rearranges all the elements in the tree so that splayed element is
placed at the root of the tree.

By splaying elements we bring more frequently used elements closer to the root of the tree so that any
operation on those elements is performed quickly. That means the splaying operation automatically brings
more frequently used elements closer to the root of the tree.

Every operation on splay tree performs the splaying operation. For example, the insertion operation first
inserts the new element using the binary search tree insertion process, then the newly inserted element is
splayed so that it is placed at the root of the tree. The search operation in a splay tree is nothing but
searching the element using binary search process and then splaying that searched element so that it is
placed at the root of the tree.

In splay tree, to splay any element we use the following rotation operations...

Rotations in Splay Tree

 1. Zig Rotation
 2. Zag Rotation
 3. Zig - Zig Rotation
 4. Zag - Zag Rotation
 5. Zig - Zag Rotation
 6. Zag - Zig Rotation

Example

Zig Rotation
The Zig Rotation in splay tree is similar to the single right rotation in AVL Tree rotations. In zig rotation,
every node moves one position to the right from its current position. Consider the following example...

Zag Rotation
The Zag Rotation in splay tree is similar to the single left rotation in AVL Tree rotations. In zag rotation,
every node moves one position to the left from its current position. Consider the following example...

Zig-Zig Rotation
The Zig-Zig Rotation in splay tree is a double zig rotation. In zig-zig rotation, every node moves two
positions to the right from its current position. Consider the following example...

Zag-Zag Rotation
The Zag-Zag Rotation in splay tree is a double zag rotation. In zag-zag rotation, every node moves two
positions to the left from its current position. Consider the following example...
Zig-Zag Rotation
The Zig-Zag Rotation in splay tree is a sequence of zig rotation followed by zag rotation. In zig-zag rotation,
every node moves one position to the right followed by one position to the left from its current position.
Consider the following example...

Zag-Zig Rotation
The Zag-Zig Rotation in splay tree is a sequence of zag rotation followed by zig rotation. In zag-zig rotation,
every node moves one position to the left followed by one position to the right from its current position.
Consider the following example...

Every Splay tree must be a binary search tree but it is need not to be balanced tree.

Insertion Operation in Splay Tree

The insertion operation in Splay tree is performed using following steps...

 Step 1 - Check whether tree is Empty.

  Step 2 - If tree is Empty then insert the newNode as Root node and exit from the operation.
 Step 3 - If tree is not Empty then insert the newNode as leaf node using Binary Search tree insertion
logic.
 Step 4 - After insertion, Splay the newNode

Insertion operation in Splay tree

In the insertion operation, we first insert the element in the tree and then perform the splaying operation
on the inserted element.

15, 10, 17, 7

Step 1: First, we insert node 15 in the tree. After insertion, we need to perform splaying. As 15 is a root
node, so we do not need to perform splaying.

Step 2: The next element is 10. As 10 is less than 15, so node 10 will be the left child of node 15, as shown
below:

Now, we perform splaying. To make 10 as a root node, we will perform the right rotation, as shown below:

Step 3: The next element is 17. As 17 is greater than 10 and 15 so it will become the right child of node 15.

Now, we will perform splaying. As 17 is having a parent as well as a grandparent so we will perform zig zig
rotations.
In the above figure, we can observe that 17 becomes the root node of the tree; therefore, the insertion is
completed.

Step 4: The next element is 7. As 7 is less than 17, 15, and 10, so node 7 will be left child of 10.

Now, we have to splay the tree. As 7 is having a parent as well as a grandparent so we will perform two
right rotations as shown below:

Still the node 7 is not a root node, it is a left child of the root node, i.e., 17. So, we need to perform one
more right rotation to make node 7 as a root node as shown below:
Deletion Operation in Splay Tree
The deletion operation in splay tree is similar to deletion operation in Binary Search Tree. But before
deleting the element, we first need to splay that element and then delete it from the root position. Finally
join the remaining tree using binary search tree logic.

Types of Deletions:

There are two types of deletions in the splay trees:

1. Bottom-up splaying
2. Top-down splaying

Bottom-up splaying

In bottom-up splaying, first we delete the element from the tree and then we perform the splaying on the
deleted node.

Let's understand the deletion in the Splay tree.

Suppose we want to delete 12, 14 from the tree shown below:

o First, we simply perform the standard BST deletion operation to delete 12 element. As 12 is a leaf
node, so we simply delete the node from the tree.

The deletion is still not completed. We need to splay the parent of the deleted node, i.e., 10. We have to
perform Splay(10) on the tree. As we can observe in the above tree that 10 is at the right of node 7, and
node 7 is at the left of node 13. So, first, we perform the left rotation on node 7 and then we perform the
right rotation on node 13, as shown below:

Still, node 10 is not a root node; node 10 is the left child of the root node. So, we need to perform the right
rotation on the root node, i.e., 14 to make node 10 a root node as shown below:

o Now, we have to delete the 14 element from the tree, which is shown below:

As we know that we cannot simply delete the internal node. We will replace the value of the node either
using inorder predecessor or inorder successor. Suppose we use inorder successor in which we replace the
value with the lowest value that exist in the right subtree. The lowest value in the right subtree of node 14
is 15, so we replace the value 14 with 15. Since node 14 becomes the leaf node, so we can simply delete it
as shown below:

Still, the deletion is not completed. We need to perform one more operation, i.e., splaying in which we
need to make the parent of the deleted node as the root node. Before deletion, the parent of node 14 was
the root node, i.e., 10, so we do need to perform any splaying in this case.
Top-down splaying

In top-down splaying, we first perform the splaying on which the deletion is to be performed and then
delete the node from the tree. Once the element is deleted, we will perform the join operation.

Let's understand the top-down splaying through an example.

Suppose we want to delete 16 from the tree which is shown below:

Step 1: In top-down splaying, first we perform splaying on the node 16. The node 16 has both parent as
well as grandparent. The node 16 is at the right of its parent and the parent node is also at the right of its
parent, so this is a zag zag situation. In this case, first, we will perform the left rotation on node 13 and
then 14 as shown below:
The node 16 is still not a root node, and it is a right child of the root node, so we need to perform left
rotation on the node 12 to make node 16 as a root node.

Once the node 16 becomes a root node, we will delete the node 16 and we will get two different trees, i.e.,
left subtree and right subtree as shown below:

As we know that the values of the left subtree are always lesser than the values of the right subtree. The
root of the left subtree is 12 and the root of the right subtree is 17. The first step is to find the maximum
element in the left subtree. In the left subtree, the maximum element is 15, and then we need to perform
splaying operation on 15.
As we can observe in the above tree that the element 15 is having a parent as well as a grandparent. A
node is right of its parent, and the parent node is also right of its parent, so we need to perform two left
rotations to make node 15 a root node as shown below:

After performing two rotations on the tree, node 15 becomes the root node. As we can see, the right child
of the 15 is NULL, so we attach node 17 at the right part of the 15 as shown below, and this operation is
known as a join operation.

Hash Table
Hashing : Hashing is a technique that is used to uniquely identify a specific object from a group of similar
objects. Some examples of how hashing is used in our lives include:

 In universities, each student is assigned a unique roll number that can be used to retrieve
information about them.
 In libraries, each book is assigned a unique number that can be used to determine information
about the book, such as its exact position in the library or the users it has been issued to etc.

In both these examples the students and books were hashed to a unique number.

Assume that you have an object and you want to assign a key to it to make searching easy. To store the

key/value pair, you can use a simple array like a data structure where keys (integers) can be used directly
as an index to store values. However, in cases where the keys are large and cannot be used directly as an

index, you should use hashing.

Hash Tables:
Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in
an array format, where each data value has its own unique index value. Access of data becomes very fast
if we know the index of the desired data.
Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the
size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an
index where an element is to be inserted or is to be located from.

The idea of hashing is to distribute entries (key/value pairs) uniformly across an array. Each element is
assigned a key (converted key). By using that key you can access the element in O(1) time. Using the key,
the algorithm (hash function) computes an index that suggests where an entry can be found or inserted.

Hashing is implemented in two steps:

1. An element is converted into an integer by using a hash function. This element can be used as an
index to store the original element, which falls into the hash table.

2. The element is stored in the hash table where it can be quickly retrieved using hashed key.

hash = hashfunc(key)
index = hash % array_size

In this method, the hash is independent of the array size and it is then reduced to an index (a number
between 0 and array_size − 1) by using the modulo operator (%).

Hash Functions and Hashes

Hash Function Definition: A hash function is a function that takes a set of inputs of any arbitrary size and
fits them into a table or other data structure that contains fixed-size elements.

Hashes Definition: A hash is a value in the table or data structure generated by the hash function used to
generate that particular table or data structure. The table or data structure
generated is usually called a hash table. It is also generally assumed that the time
complexity of accessing data in a hash table is O(1), or constant.

Calculating a Hash Table:

Formal definitions of hash functions vary from application to application. Let’s

take a simple example by taking each number mod 10, and putting it into a hash
table that has 10 slots.

Numbers to hash: 22, 3, 18, 29

We take each value, apply the hash function to it, and the result tells us what slot to put that value in, with
the left column denoting the slot, and the right column denoting what value is in that slot, if any.

Our hash function here is to take each value mod 10. The table to the right shows the resulting hash table.
We hash a series of values as we get them, so the first value we hash is the first value in the string of
values, and the last value we hash is the last value in the string of values.

22 mod 10 = 2, so it goes in slot 2.

3 mod 10 = 3, so it goes in slot 3.
18 mod 10 = 8, so it goes in slot 8.
29 mod 10 = 9, so it goes in slot 9.

Collisions

Definition: A collision occurs when more than one value to be hashed by a particular hash function hash to
the same slot in the table or data structure (hash table) being generated by the hash function.

Example Hash Table With Collisions:

Let’s take the exact same hash function from before: take the value to
be hashed mod 10, and place it in that slot in the hash table.

Numbers to hash: 22, 9, 14, 17, 42

As before, the hash table is shown to the right.

As before, we hash each value as it appears in the string of values to

hash, starting with the first value. The first four values can be entered
into the hash table without any issues. It is the last value, 42, however,
that causes a problem. 42 mod 10 = 2, but there is already a value in
slot 2 of the hash table, namely 22. This is a collision.

The value 42 must end up in one of the hash table’s slots,

but arbitrarly assigning it a slot at random would make accessing data in
a hash table much more time consuming, as we obviously want to
retain the constant time growth of accessing our hash table. There are
two common ways to deal with collisions: chaining, and open
addressing.

How to handle Collisions?

There are mainly two methods to handle collision:
1. Open Hashing(Closed Addressing)
i. Chaining
2. Closed Hashing(Open Addressing)
i. Linear Probing
ii. Quadratic Probing
iii. Double Hashing

1) Chaining:
The idea is to make each cell of hash table point to a linked list of records that have same hash function
value.
Let us consider a simple hash function as “key mod 7” and sequence of keys as 50, 700, 76, 85, 92, 73,
101.
Chaining Advantages:
1) Simple to implement.
2) Hash table never fills up, we can always add more elements to the chain.
3) Less sensitive to the hash function or load factors.
4) It is mostly used when it is unknown how many and how frequently keys may be inserted or deleted.
Chaining Disadvantages:
1) Cache performance of chaining is not good as keys are stored using a linked list. Open addressing
provides better cache performance as everything is stored in the same table.
2) Wastage of Space (Some Parts of hash table are never used)
3) If the chain becomes long, then search time can become O(n) in the worst case.
4) Uses extra space for links.

2) Linear Probing:
In linear probing, we linearly probe for next slot. For example, the typical gap between two
probes is 1 as seen in the example below.

Let us consider a simple hash function as “key mod 7” and a sequence of keys as 50, 700, 76, 85, 92, 73,
101.
Challenges in Linear Probing :
1. Primary Clustering: One of the problems with linear probing is Primary clustering, many consecutive
elements form groups and it starts taking time to find a free slot or to search for an element.
2. Secondary Clustering: Secondary clustering is less severe, two records only have the same collision
chain (Probe Sequence) if their initial position is the same.

3. Quadratic Probing in Hashing

Hashing is an improvement over Direct Access Table. The idea is to use a hash function that converts a
given phone number or any other key to a smaller number and uses the small number as the index in a
table called a hash table.
Hash Function: A function that converts a given big number to a small practical integer value. The
mapped integer value is used as an index in the hash table. In simple terms, a hash function maps a big
number or string to a small integer that can be used as an index in the hash table.
In this article, the collision technique, quadratic probing is discussed.
Quadratic Probing: Quadratic probing is an open-addressing scheme where we look for i2‘th slot in i’th
iteration if the given hash value x collides in the hash table.

In this section we will see what is quadratic probing technique in open addressing scheme. There is an
ordinary hash function h’(x) : U → {0, 1, . . ., m – 1}. In open addressing scheme, the actual hash function
h(x) is taking the ordinary hash function h’(x) and attach some another part with it to make one quadratic
equation.

h´ = (𝑥) = 𝑥𝑚𝑜𝑑𝑚
ℎ(𝑥, 𝑖) = (ℎ´(𝑥) + 𝑖2)𝑚𝑜𝑑𝑚

We can put some other quadratic equations also using some constants
The value of i = 0, 1, . . ., m – 1. So we start from i = 0, and increase this until we get one free space. So
initially when i = 0, then the h(x, i) is same as h´(x).
Quadratic Probing Example:
we have a list of size 20 (m = 20). We want to put some elements in linear probing fashion. The elements
are {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

Hash Table

4. Double Hashing

Double hashing is a collision resolving technique in Open Addressed Hash tables. Double hashing uses
the idea of applying a second hash function to key when a collision occurs.
Advantages of Double hashing
 The advantage of Double hashing is that it is one of the best form of probing, producing a uniform
distribution of records throughout a hash table.
 This technique does not yield any clusters.
 It is one of effective method for resolving collisions.

Double hashing can be done using : (hash1(key) + i * hash2(key)) % TABLE_SIZE

Here hash1() and hash2() are hash functions and TABLE_SIZE

is size of hash table.
(We repeat by increasing i when collision occurs)
First hash function is typically hash1(key) = key % TABLE_SIZE
A popular second hash function is : hash2(key) = PRIME – (key % PRIME) where PRIME is a prime smaller
than the TABLE_SIZE.
A good second Hash function is:

 It must never evaluate to zero

 Must make sure that all cells can be probed

Double Hashing Example:

Suppose we have a list of size 20 (m = 20). We want to put some elements in linear probing fashion. The
elements are {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}
h1(x)=xmod20h1(x)=xmod20
h2(x)=xmod13h2(x)=xmod13
x h(x, i) = (h1 (x) + ih2(x)) mod 20

Output:
Difference between separate chaining and open addressing:

S.No. Separate Chaining Open Addressing

Open Addressing requires more

1. Chaining is Simpler to implement. computation.

In chaining, Hash table never fills up, we can

2. always add more elements to chain. In open addressing, table may become full.

Chaining is Less sensitive to the hash function or Open addressing requires extra care to
3. load factors. avoid clustering and load factor.

Chaining is mostly used when it is unknown how

many and how frequently keys may be inserted Open addressing is used when the
4. or deleted. frequency and number of keys is known.

Open addressing provides better cache

Cache performance of chaining is not good as performance as everything is stored in the
5. keys are stored using linked list. same table.

Wastage of Space (Some Parts of hash table in In Open addressing, a slot can be used even
6. chaining are never used). if an input doesn’t map to it.

7. Chaining uses extra space for links. No links in Open addressing

advantages and disadvantages of various collision resolution strategies

The advantages and disadvantages of some of the collision resolution techniques are explained below −
Separate Chaining hashing
Separate chaining is a hashing technique in which there is a list to handle collisions. So there are many
elements at the same position and they are in a list. The sequences are maintained in a linked list.
The advantages of separate chaining hashing are as follows −
 Separate chaining technique is not sensitive to the size of the table.
 The idea and the implementation are simple.
The disadvantages of separate chaining hashing are as follows −
 Keys are not evenly distributed in separate chaining.
 Separate chaining can lead to empty spaces in the table.
 The list in the positions can be very long.
Linear Probing
Linear probing is a simple collision resolution technique for resolving collisions in hash tables, data
structures for maintaining collection of values in a hash table. If there is a collision for the position of the
key value then the linear probing technique assigns the next free space to the value.
The advantages of linear probing are as follows −
 Linear probing requires very less memory.
 It is less complex and is simpler to implement.
The disadvantages of linear probing are as follows −
 Linear probing causes a scenario called "primary clustering" in which there are large blocks of
occupied cells within the hash table.
 The values in linear probing tend to cluster which makes the probe sequence longer and lengthier.

UNIT-3 10-Marks Questions

1. Explain Red-Black tree and its operations?

2. Construct a Red-Black tree by inserting numbers from 1 to 9?
3. Write insertion algorithm in Red-Black tree? Explain with example?
4. What is splay tree? What are the Rotations in splay tree?
5. Write insertion algorithm in splay tree? Explain with example?
6. Write deletion algorithm in splay tree? Explain with example?
7. What is open addressing and explain it with an example?
8. What is Hash Table & structure of hash table?
9. What is a Collision? What are the techniques used to solve collision?
10. What is chaining? Explain with example?
11. What is linear probing? Explain with example?
12. What is quadratic probing? Explain with example?
13. What is double hashing? Explain with example?
14. Define bucket hashing and explain it with an example. Also analyse it with an example
15. Discuss the common collision resolution strategies used in closed hashing system.
16. Given the input { 4371, 1323, 6173, 4199, 4344, 9679, 1989 } and a hash function of h(X)=X (mod 3.
show the resulting:
a. Separate Chaining hash table
b. Open addressing hash table using linear probing
c. Explain Re-hashing and Extendible hashing.
17. Show the result of inserting the keys 2,3,5,7,11,13,15,6,4 into an initially empty extendible hashing
data structure with M=3.
18. what are the advantages and disadvantages of various collision resolution strategies?

2-mark questions:
 1. What are red-black trees? What problem do they solve

Binary search trees work well when they are ordered and balanced. But when new items are inserted into
an ordered binary search tree, the binary search tree becomes unbalanced. With unbalanced trees the
efficiency of searches degrades.
Red-black trees are specialized binary search trees with additional features which ensures that the trees
are balanced.

2. How are red-black trees maintained in a balanced state?

Red-black trees are balanced during insertion and deletion od items to the tree. The insertion and deletion
routines of the red-black tree check that certain characteristics of the tree are not violated. If these
characteristics are violated, the routines re-structure the tree so that the tree remains in a balanced state.

3. What are the characteristics of red-black trees?

Following are the two characteristics of red-black trees.

1. Colored nodes: The nodes in a red-black tree are colored. Each node can be either red or black.
2. Red-black rules: When a node is inserted or deleted in a red-black tree. certain rules have to be followed
to ensure that the tree remains balanced after the node deletion or insertion.

4. What are the rules that have to be followed when an item is inserted or deleted from a tree?

Followed are the rules that must be followed when a node is inserted or deleted from a red-black tree.
1. Every node is either a red node or a black node
2. The root node of the red-black tree is always black.
3. If a node is red then is child nodes must be black. The converse is not true. I.e. if a node is black then its
child nodes can either be red or black.
4. Every path from the root node to a leaf node, or to a null node, must contain the same number of black
nodes.

5. How do you fix rule violations when a node is inserted or deleted from a red-black tree?

There are two ways to fix rule violations in red-black trees.

1. Fix rule violations by changing the color of nodes.
2. Fix rule violations by performing rotations. A rotation is rearrangement of nodes that makes the tree
more balanced.

6. What is the time efficiency of insertion, deletion and search operations on red-black trees?
Insertions, deletions and searches are the common operations performed on red-black trees.
The time efficiency of these operation on binary search trees is O(logN).

7. Define hashing function

A hashing function is a key-to-transformation, which acts upon a given key to compute the relative position
of the key in an array.
A simple hash function
HASH(KEY_Value)= (KEY_Value)mod(Table-size)
8.What is open addressing?
Open addressing is also called closed hashing, which is an alternative to resolve the collisions with linked
lists. In this hashing system, if a collision occurs, alternative cells are tired until an empty cell is found.
There are three strategies in open addressing:
 Linear probing
 Quadratic probing
 Double hashing
9. What are the collision resolution methods?
The following are the collision resolution methods
 Separate chaining
 Open addressing
 Multiple hashing
10. Define separate chaining
It is an open hashing technique. A pointer field is added to each record location, when an overflow occurs,
this pointer is set to point to overflow blocks making a linked list. In this method, the table can never
overflow, since the linked lists are only extended upon the arrival of new keys
11. Define Hashing.
Hashing is the transformation of string of characters into a usually shorter fixed length value or key that
represents the original string. Hashing is used to index and retrieve items in a database because it is faster to
find the item using the short hashed key than to find it using the original value.
12..What do you mean by hash table?
The hash table data structure is merely an array of some fixed size, containing the keys. A key is a string
with an associated value. Each key is mapped into some number in the range 0 to tablesize-1 and placed in
the appropriate cell.
13. What do you mean by hash function?
A hash function is a key to address transformation which acts upon a given key to compute the relative
position of the key in an array. The choice of hash function should be simple and it must distribute the data
evenly. A simple hash function is hash_key=key mod tablesize.

14. Write the importance of hashing.

• Maps key with the corresponding value using hash function.
• Hash tables support the efficient addition of new entries and the time spent on searching for the required
data is independent of the number of items stored.
15. What do you mean by collision in hashing?
When an element is inserted, it hashes to the same value as an already inserted element, and then it produces
collision.
16. What are the collision resolution methods?
• Separate chaining or External hashing
• Open addressing or Closed hashing
17. What do you mean by separate chaining?
Separate chaining is a collision resolution technique to keep the list of all elements that hash to the same
value. This is called separate chaining because each hash table element is a separate chain (linked list). Each
linked list contains all the elements whose keys hash to the same index.
18. Write the disadvantages of separate chaining.
• The elements are evenly distributed. Some elements may have more elements and some may not have
anything.
• It requires pointers. This leads to slow the algorithm down a bit because of the time required to allocate
new cells, and also essentially requires the implementation of a second data structure.
19. What do you mean by open addressing?
Open addressing is a collision resolving strategy in which, if collision occurs alternative cells are tried until
an empty cell is found. The cells h0(x), h1(x), h2(x),…. are tried in succession, where
hi(x)=(Hash(x)+F(i))mod Tablesize with F(0)=0. The function F is the collision resolution strategy.
20. What are the types of collision resolution strategies in open addressing?
• Linear probing
• Quadratic probing
• Double hashing
21. What do you mean by linear probing?
Linear probing is an open addressing collision resolution strategy in which F is a linear function of i, F(i)=i.
This amounts to trying sequentially in search of an empty cell. If the table is big enough, a free cell can
always be found, but the time to do so can get quite large.
22. What do you mean by primary clustering?
In linear probing collision resolution strategy, even if the table is relatively empty, blocks of occupied cells
start forming. This effect is known as primary clustering means that any key hashes into the cluster will
require several attempts to resolve the collision and then it will add to the cluster.
23. What do you mean by quadratic probing?
Quadratic probing is an open addressing collision resolution strategy in which F(i)=i2. There is no guarantee
of finding an empty cell once the table gets half full if the table size is not prime. This is because at most
half of the table can be used as alternative locations to resolve collisions.

24. What do you mean by secondary clustering?

 Although quadratic probing eliminates primary clustering, elements that hash to the same position will
probe the same alternative cells. This is known as secondary clustering.
25. What do you mean by double hashing?
Double hashing is an open addressing collision resolution strategy in which F(i)=i.hash2(X). This formula
says that we apply a second hash function to X and probe at a distance hash2(X), 2hash2(X),….,and so on.
A function such as hash2(X)=R-(XmodR), with R a prime smaller than
26. What do you mean by rehashing?
If the table gets too full, the running time for the operations will start taking too long and inserts might fail
for open addressing with quadratic resolution. A solution to this is to build another table that is about twice
as big with the associated new hash function and scan down the entire original hash table, computing the
new hash value for each element and inserting it in the new table. This entire operation is called rehashing.
27. What is the need for extendible hashing?
If either open addressing hashing or separate chaining hashing is used, the major problem is that collisions
could cause several blocks to be examined during a Find, even for a welldistributed hash table. Extendible
hashing allows a find to be performed in two disk accesses. Insertions also require few disk accesses.

Bits
1. What is the special property of red-black trees and what root should always be?
a) a color which is either red or black and root should always be black color only
b) height of the tree
c) pointer to next node
d) a color which is either green or black
2. Why do we impose restrictions like
.root property is black
. every leaf is black
. children of red node are black
. all leaves have same black
a) to get logarithm time complexity
b) to get linear time complexity
c) to get exponential time complexity
d) to get constant time complexity
3. Which of the following is an application of Red-black trees and why?
a) used to store strings efficiently
b) used to store integers efficiently
c) can be used in process schedulers, maps, sets
d) for efficient sorting
4. Why Red-black trees are preferred over hash tables though hash tables have constant time
complexity?
a) no they are not preferred
b) because of resizing issues of hash table and better ordering in redblack trees
c) because they can be implemented using trees
d) because they are balanced
5. When to choose Red-Black tree, AVL tree and B-trees?
a) many inserts, many searches and when managing more items respectively
b) many searches, when managing more items respectively and many inserts respectively
c) sorting, sorting and retrieval respectively
d) retrieval, sorting and retrieval respectively
6. What are splay trees?
a) self adjusting binary search trees
b) self adjusting binary trees
 c) a tree with strings
d) a tree with probability distributions
7. Which of the following property of splay tree is correct?
a) it holds probability usage of the respective sub trees
b) any sequence of j operations starting from an empty tree with h nodes atmost, takes
O(jlogh) time complexity
c) sequence of operations with h nodes can take O(logh) time complexity
d) splay trees are unstable trees
8. Why to prefer splay trees?
a) easier to program
b) space efficiency
c) easier to program and faster access to recently accessed items
d) quick searching
9. Which of the following options is an application of splay trees?
a) cache Implementation
b) networks
c) send values
d) receive values
10. When we have red-black trees and AVL trees that can perform most of operations in logarithmic
times, then what is the need for splay trees?
a) no there is no special usage
b) In real time it is estimated that 80% access is only to 20% data, hence most used ones
must be easily available
c) redblack and avl are not upto mark
d) they are just another type of self balancing binary search trees
11. What is the disadvantage of using splay trees?
a) height of a splay tree can be linear when accessing elements in non decreasing order.
b) splay operations are difficult
c) no significant disadvantage
d) splay tree performs unnecessary splay when a node is only being read
12. What is a hash table?
a) A structure that maps values to keys
b) A structure that maps keys to values
c) A structure used for storage
d) A structure used to implement stack and queue
13. If several elements are competing for the same bucket in the hash table, what is it called?
a) Diffusion
b) Replication
c) Collision
d) Duplication
14. What is direct addressing?
a) Distinct array position for every possible key
b) Fewer array positions than keys
c) Fewer keys than array positions
d) Same array position for all keys
15. What is the search complexity in direct addressing?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)
16. What is a hash function?
a) A function has allocated memory to keys
b) A function that computes the location of the key in the array
c) A function that creates an array
d) A function that computes the location of the values in the array
17. Which of the following is not a technique to avoid a collision?
a) Make the hash function appear random
 b) Use the chaining method
c) Use uniform hashing
d) Increasing hash table size
18. What is simple uniform hashing?
a) Every element has equal probability of hashing into any of the slots
b) A weighted probabilistic method is used to hash elements into the slots
c) Elements has Random probability of hashing into array slots
d) Elements are hashed based on priority
19. In simple chaining, what data structure is appropriate?
a) Singly linked list
b) Doubly linked list
c) Circular linked list
d) Binary trees
20. In simple uniform hashing, what is the search complexity?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)