Data Structures — Unit IV: Non-Linear Data Structures
UNIT IV NOTES — DATA STRUCTURES
NON-LINEAR DATA STRUCTURES
Trees • Binary Trees • Tree Traversals • Expression Trees • Binary Search Tree • Hashing • Hash Functions •
Separate Chaining • Open Addressing • Linear Probing • Quadratic Probing • Double Hashing • Rehashing
1. TREES
1.1 Definition
A Tree is a non-linear, hierarchical data structure consisting of a finite set of nodes connected by edges, such
that there is one special node called the ROOT, and every other node is connected to the root through exactly
one path. A tree with n nodes always has exactly n − 1 edges, and it contains no cycles.
Real-life analogy: a family genealogy chart or an organisation's reporting hierarchy — one person at the top
(root), with each subsequent level branching into subordinates.
1.2 Basic Terminology
Term Meaning
Root The topmost node of the tree; it has no parent
Parent A node that has one or more child nodes directly below it
Child A node directly connected below another node (its parent)
Siblings Nodes that share the same parent
Leaf / External Node A node with no children
Internal Node A node that has at least one child
Edge The link connecting a parent node to a child node
Degree of a Node The number of children a node has
Degree of a Tree The maximum degree among all nodes in the tree
Depth / Level of a Node The number of edges from the root to that node (root is at level 0)
Height of a Node The number of edges on the longest path from that node to a leaf
Height of a Tree The height of the root node (i.e., the maximum depth of any leaf)
Ancestor Any node lying on the path from the root to a given node
Descendant Any node reachable by moving downward from a given node
Subtree A tree formed by a node and all of its descendants
Forest A collection of disjoint trees (a tree without its root becomes a forest of its
subtrees)
1.3 Properties of Trees
● A tree with n nodes contains exactly n − 1 edges.
● There is exactly one unique path between the root and every other node.
● A tree is a connected, acyclic graph.
Page 1
Data Structures — Unit IV: Non-Linear Data Structures
● Every node except the root has exactly one parent.
● A tree with zero nodes is called a null / empty tree.
1.4 Representation of Trees
1.4.1 List Representation
Each node is represented as a list where the first element is the node's data and the remaining elements are its
children — e.g. (A (B (D E)) (C)) represents A with children B and C, where B further has children D and E.
1.4.2 Left-Child Right-Sibling Representation
Each node stores a pointer to its first (leftmost) child and a pointer to its next sibling. This allows a tree of any
degree to be represented using only two pointers per node, regardless of how many children a node actually
has.
struct Node {
int data;
struct Node *firstChild;
struct Node *nextSibling;
};
1.5 Applications of Trees
● Representing hierarchical data — file/directory systems, organisation charts.
● Binary Search Trees for fast searching, insertion and deletion.
● Expression trees used by compilers to evaluate arithmetic expressions.
● Decision trees in artificial intelligence and machine learning.
● Routing tables and network structures, and the DOM tree in web browsers.
● Huffman coding trees for data compression, and heaps for priority queues.
2. BINARY TREES
2.1 Definition
A Binary Tree is a tree in which every node has at most two children, referred to as the LEFT child and the RIGHT
child. Unlike a general tree, the two children in a binary tree are distinguished — a node may have only a left
child, only a right child, both, or neither, and each position is ordered.
2.2 Types of Binary Trees
Type Description
Full / Strict Binary Tree Every node has either 0 or exactly 2 children (no node has only one child)
Complete Binary Tree All levels are completely filled except possibly the last, which is filled strictly
from left to right
Perfect Binary Tree All internal nodes have exactly 2 children and all leaf nodes are at the same
level
Skewed Binary Tree Every node has only a left child (left-skewed) or only a right child (right-
skewed) — degenerates into a linked list
Page 2
Data Structures — Unit IV: Non-Linear Data Structures
Balanced Binary Tree The height of the left and right subtrees of every node differs by at most a
fixed constant (e.g. AVL tree: at most 1)
Extended Binary Tree (2-tree) Every node has either 0 or 2 children; used to represent expressions,
obtained by adding external nodes to a binary tree
2.3 Properties of Binary Trees
Property Formula / Statement
Maximum nodes at level i 2^i (root is level 0)
Maximum nodes in a binary tree of height h 2^(h+1) − 1
Minimum height for n nodes ⌈log2(n + 1)⌉ − 1
Relationship (Full Binary Tree) Number of leaf nodes L = Number of internal nodes (with 2
children) I, + 1 i.e. L = I + 1
Total nodes in a Full Binary Tree n = 2I + 1, where I = number of internal nodes
2.4 Representation of Binary Trees
2.4.1 Array Representation
For a node stored at index i (0-based) in an array, its left child is at index 2i + 1, its right child at 2i + 2, and its
parent at ⌊(i − 1)/2⌋. This representation is compact and efficient for complete binary trees (e.g. heaps), but
wastes space for sparse/skewed trees.
2.4.2 Linked Representation
Each node is a structure containing the data field and two pointers, left and right, pointing to its left and right
children respectively. This is the most common representation.
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node* createNode(int value) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
Exam Tip: A very common 2-mark question asks to differentiate Full, Complete and Perfect binary trees with a diagram —
remember: every Perfect tree is also Complete and Full, but not vice-versa.
Page 3
Data Structures — Unit IV: Non-Linear Data Structures
3. TREE TRAVERSALS
3.1 Definition
Tree traversal is the process of visiting (accessing/processing) every node in a tree exactly once, in a systematic
order. Traversals are broadly classified into Depth-First Traversals (Preorder, Inorder, Postorder) and Breadth-
First Traversal (Level Order).
3.2 Sample Tree Used for Examples
A
/ \
B C
/ \ \
D E F
/
G
3.3 Preorder Traversal (Root → Left → Right)
void preorder(struct Node *root) {
if (root == NULL) return;
printf("%d ", root->data); // visit root
preorder(root->left); // traverse left subtree
preorder(root->right); // traverse right subtree
}
For the sample tree above, Preorder = A B D E G C F
3.4 Inorder Traversal (Left → Root → Right)
void inorder(struct Node *root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
For the sample tree above, Inorder = D B G E A C F
Note: Inorder traversal of a Binary Search Tree always produces the elements in ascending sorted order — this is
one of the most important facts for exams.
3.5 Postorder Traversal (Left → Right → Root)
void postorder(struct Node *root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
For the sample tree above, Postorder = D G E B F C A
Page 4
Data Structures — Unit IV: Non-Linear Data Structures
3.6 Level Order Traversal (Breadth-First)
Level order traversal visits nodes level by level, from left to right, using a Queue: the root is enqueued first; then,
repeatedly, a node is dequeued, processed, and its children are enqueued.
void levelOrder(struct Node *root) {
if (root == NULL) return;
Queue q; enqueue(q, root);
while (!isEmpty(q)) {
struct Node *current = dequeue(q);
printf("%d ", current->data);
if (current->left != NULL) enqueue(q, current->left);
if (current->right != NULL) enqueue(q, current->right);
}
}
For the sample tree above, Level Order = A B C D E F G
3.7 Comparison of Traversal Techniques
Traversal Order Data Structure Used Typical Use
Preorder Root, Left, Right Recursion / Stack Copying / cloning a tree;
producing prefix expression
Inorder Left, Root, Right Recursion / Stack Retrieving BST elements in
sorted order
Postorder Left, Right, Root Recursion / Stack Deleting a tree; producing
postfix expression
Level Order Level by level Queue Finding shortest path /
printing tree level-wise
Exam Tip: 20-mark questions on this topic usually ask you to draw a tree, then give all four traversal outputs with the
recursive algorithm for each — practise tracing recursion carefully using a stack diagram.
4. EXPRESSION TREES
4.1 Definition
An Expression Tree is a special binary tree used to represent an arithmetic or logical expression. Every leaf
(external) node holds an operand, and every internal node holds an operator. The left and right subtrees of an
operator node represent its left and right operands respectively (which may themselves be sub-expressions).
4.2 Constructing an Expression Tree from Postfix Expression
Algorithm:
1. Create an empty stack of tree-node pointers.
2. Scan the postfix expression from left to right, for each token:
a. If token is an operand -> create a leaf node and push its pointer.
b. If token is an operator -> pop two nodes from the stack
(right = first popped, left = second popped);
create a new node with this operator as data,
attach 'left' as its left child and 'right' as its right child;
Page 5
Data Structures — Unit IV: Non-Linear Data Structures
push the pointer to this new node.
3. After the scan, the single node left in the stack is the root
of the expression tree.
Worked Example
Construct the expression tree for the postfix expression: A B + C D − *
Token Action Stack (bottom→top, showing subtree
roots)
A push leaf(A) A
B push leaf(B) A, B
+ pop B,A -> new node(+) with left=A, right=B -> push (A+B)
C push leaf(C) (A+B), C
D push leaf(D) (A+B), C, D
− pop D,C -> new node(−) with left=C, right=D -> push (A+B), (C−D)
* pop (C−D),(A+B) -> new node(*) with left=(A+B), ((A+B)*(C−D))
right=(C−D) -> push
Resulting Expression Tree:
*
/ \
+ −
/ \ / \
A B C D
4.3 Traversing an Expression Tree
Traversal of Expression Tree Produces
Preorder (Root, Left, Right) Prefix expression: * + A B − C D
Inorder (Left, Root, Right) Infix expression (with brackets added): (A + B) * (C − D)
Postorder (Left, Right, Root) Postfix expression: A B + C D − *
4.4 Evaluating an Expression Tree
Evaluation is done recursively using postorder logic — a leaf node simply returns its own value, and an operator
node returns the result of applying the operator to the evaluated values of its left and right subtrees.
int evaluate(struct Node *root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL)
return root->data; // leaf holds an operand
int leftVal = evaluate(root->left);
int rightVal = evaluate(root->right);
switch (root->data) {
case '+': return leftVal + rightVal;
case '-': return leftVal - rightVal;
case '*': return leftVal * rightVal;
case '/': return leftVal / rightVal;
Page 6
Data Structures — Unit IV: Non-Linear Data Structures
}
return 0;
}
4.5 Applications of Expression Trees
● Used internally by compilers to parse and evaluate arithmetic expressions.
● Allow easy conversion between infix, prefix and postfix forms using simple traversals.
● Used in calculators and interpreters for expression evaluation.
● Form the basis of syntax trees used in parsing programming languages.
5. BINARY SEARCH TREE (BST)
5.1 Definition
A Binary Search Tree is a binary tree that satisfies the BST property: for every node, all keys in its left subtree are
strictly less than the node's key, and all keys in its right subtree are strictly greater than the node's key. This
property must hold for every node in the tree, not just the root, and no duplicate keys are usually allowed.
5.2 Operations on BST
5.2.1 Searching in a BST
Starting at the root, the key is compared with the current node: if equal, the node is found; if smaller, search
continues in the left subtree; if larger, search continues in the right subtree. Since at each step roughly half the
remaining nodes are eliminated (in a balanced tree), this gives O(log n) average time.
struct Node* search(struct Node *root, int key) {
if (root == NULL || root->data == key)
return root;
if (key < root->data)
return search(root->left, key);
else
return search(root->right, key);
}
5.2.2 Insertion in a BST
A new key is always inserted as a leaf node, at the position dictated by repeatedly comparing the key with
existing nodes and moving left or right, until a NULL pointer is reached.
struct Node* insert(struct Node *root, int key) {
if (root == NULL)
return createNode(key);
if (key < root->data)
root->left = insert(root->left, key);
else if (key > root->data)
root->right = insert(root->right, key);
return root; // key already exists -> no duplicate inserted
}
Worked Example: Insert 50, 30, 70, 20, 40, 60, 80 into an empty BST, in this order.
Page 7
Data Structures — Unit IV: Non-Linear Data Structures
50
/ \
30 70
/ \ / \
20 40 60 80
5.2.3 Deletion in a BST
Deletion has three cases, depending on the number of children of the node to be deleted:
Case Rule
Node is a leaf (no children) Simply remove the node and set the parent's pointer to NULL
Node has exactly one child Remove the node and connect its parent directly to its single child
Node has two children Find the inorder successor (the smallest key in the right subtree, i.e. leftmost
node of the right subtree) — or alternatively the inorder predecessor (largest
key in the left subtree); copy that value into the node to be deleted, then delete
the successor/predecessor node (which now falls under case 1 or 2)
struct Node* findMin(struct Node *root) {
while (root->left != NULL)
root = root->left;
return root;
}
struct Node* deleteNode(struct Node *root, int key) {
if (root == NULL) return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
// node found
if (root->left == NULL) {
struct Node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node *temp = root->left;
free(root);
return temp;
}
// node with two children: get inorder successor
struct Node *successor = findMin(root->right);
root->data = successor->data;
root->right = deleteNode(root->right, successor->data);
}
return root;
}
5.3 Complexity of BST Operations
Operation Average Case Worst Case (Skewed Tree)
Search O(log n) O(n)
Page 8
Data Structures — Unit IV: Non-Linear Data Structures
Insertion O(log n) O(n)
Deletion O(log n) O(n)
The worst case O(n) occurs when the BST degenerates into a skewed tree (essentially a linked list) — for
example, when keys are inserted in already-sorted order. Self-balancing trees such as AVL trees and Red-Black
trees are used to guarantee O(log n) in the worst case.
5.4 Applications of BST
● Efficient searching, insertion, and deletion of dynamic data sets.
● Implementing associative arrays / ordered maps and sets.
● Retrieving sorted data through inorder traversal.
● Used as an underlying structure in database indexing and multi-level indexing.
Exam Tip: For 20-mark BST questions, always show the tree built step by step for a given insertion sequence, and clearly
explain all three deletion cases with a small diagram for the two-children case.
6. HASHING
6.1 Definition
Hashing is a technique used to map data (keys) to specific positions (called slots or buckets) in a table, called a
Hash Table, using a mathematical function called a Hash Function. It allows average-case O(1) time for search,
insertion, and deletion — significantly faster than the O(log n) of a balanced BST or O(n) of a linear list.
6.2 Basic Terminology
Term Meaning
Hash Table An array-based data structure that stores key-value pairs at positions computed
by a hash function
Hash Function h(k) A function that converts a key k into a valid array index (0 to tableSize − 1)
Bucket / Slot A position in the hash table that can hold one (or more, in chaining) elements
Collision A situation where two different keys are mapped by the hash function to the
same index
Load Factor (α) α = (number of elements stored) / (table size) — indicates how full the table is
6.3 Advantages and Disadvantages of Hashing
Advantages Disadvantages
Very fast average-case search/insert/delete — O(1) Worst-case performance can degrade to O(n) if many
collisions occur
Efficient use for implementing sets, maps, caches, Requires a good hash function and adequate table size
symbol tables to minimise collisions
Simple concept, widely used in real systems Hash tables do not preserve any sorted order of
(databases, compilers) elements
Page 9
Data Structures — Unit IV: Non-Linear Data Structures
7. HASH FUNCTIONS
7.1 Definition and Properties of a Good Hash Function
● Should be easy and fast to compute.
● Should distribute keys uniformly across all the slots of the table (minimising collisions).
● Should minimise clustering of keys in nearby slots.
● Should use the entire key, not just part of it, to compute the index.
● Should produce few collisions on typical/real-world input data.
7.2 Types of Hash Functions
7.2.1 Division Method
The most common and simplest method: h(k) = k mod m, where m is the size of the hash table. It is best when
m is chosen as a prime number not close to a power of 2, which helps spread keys more uniformly.
Example: For table size m = 7 and key k = 23, h(23) = 23 mod 7 = 2 → stored at index 2.
7.2.2 Multiplication Method
Formula: h(k) = ⌊m × (k·A mod 1)⌋, where A is a constant between 0 and 1 (Knuth suggests A ≈ 0.6180339887,
the golden ratio conjugate). This method works well for any table size m and does not require m to be prime.
7.2.3 Mid-Square Method
The key is squared, and an appropriate number of digits (matching the required index range) are extracted from
the middle of the squared result to form the index.
Example: key = 60, table size = 100 (2-digit index). 60² = 3600 → middle digits = 60 → index 60.
7.2.4 Folding Method
The key is divided into equal-sized parts (matching the digit-width of the table size), and the parts are added
together (discarding any final carry) to obtain the index.
Example: key = 123456789, split into 3-digit groups: 123 + 456 + 789 = 1368 → take last 3 digits (or apply mod
table size) → 368.
7.2.5 Digit / Character Analysis
Applicable when the key set is known in advance; specific digit positions that show maximum variation across
the keys are chosen and combined to form the index, discarding positions with little variation.
Exam Tip: The Division Method h(k) = k mod m is by far the most frequently asked and used in worked examples for
chaining/probing questions — make sure you can compute it instantly for any key/table-size pair.
8. SEPARATE CHAINING
8.1 Definition
Separate Chaining is a collision-resolution technique in which each slot of the hash table holds a pointer to a
linked list (chain) of all the keys that hash to that same slot. When a collision occurs, the new key is simply
appended (or prepended) to the linked list at that index, instead of being placed elsewhere in the table.
Page 10
Data Structures — Unit IV: Non-Linear Data Structures
8.2 Algorithm
insert(key):
index = h(key)
add 'key' to the front (or end) of the linked list at table[index]
search(key):
index = h(key)
traverse the linked list at table[index] looking for 'key'
delete(key):
index = h(key)
locate 'key' in the linked list at table[index] and remove that node
8.3 Worked Example
Insert keys 19, 27, 36, 10, 24, 17 into a hash table of size m = 7 using the division method h(k) = k mod 7, with
separate chaining.
Key h(key) = key mod 7
19 5
27 6
36 1
10 3
24 3
17 3
Resulting Hash Table (chains):
Index 0 : empty
Index 1 : 36
Index 2 : empty
Index 3 : 10 -> 24 -> 17 (collision chain — all three map to index 3)
Index 4 : empty
Index 5 : 19
Index 6 : 27
8.4 Advantages and Disadvantages
Advantages Disadvantages
Simple to implement; no limit on number of elements Requires extra memory for pointers (linked list
per slot overhead)
Table never 'overflows' — load factor α can exceed 1 Performance degrades to O(chain length) if many keys
hash to the same slot
Deletion is straightforward (simple linked-list removal) Poor cache/locality performance compared to open
addressing
Page 11
Data Structures — Unit IV: Non-Linear Data Structures
9. OPEN ADDRESSING
9.1 Definition
Open Addressing is a collision-resolution technique in which all keys are stored directly inside the hash table
array itself (no external linked lists). When a collision occurs at slot h(k), the table is systematically 'probed' —
examined in a fixed sequence — until an empty slot is found to place the key. Because all elements live in the
array, the table size must always be greater than or equal to the number of keys to be stored, i.e. load factor α ≤
1.
9.2 General Probing Formula
The index examined at probe attempt i is given by: h(k, i) = ( h′(k) + f(i) ) mod m, where h′(k) is an auxiliary/base
hash function, f(i) is the probing function (differs by technique), m is the table size, and i = 0, 1, 2, … until an
empty slot is located.
9.3 Types of Open Addressing
Technique Probing Function f(i)
Linear Probing f(i) = i
Quadratic Probing f(i) = c1·i + c2·i² (commonly f(i) = i²)
Double Hashing f(i) = i × h2(k) (a second hash function)
9.4 Deletion in Open Addressing
Deletion cannot simply set the slot to 'empty', because that would break the probe sequence for other keys that
were placed after probing past this slot. Instead, deleted slots are marked with a special 'DELETED' marker (a
tombstone) — search continues past DELETED markers, while insertion may reuse a DELETED slot.
9.5 Clustering Problems
Problem Description Occurs In
Primary Clustering Long runs of consecutively occupied slots build up, Linear Probing
causing many keys to probe through the same long
chain
Secondary Clustering Keys that collide at the same initial slot follow the Quadratic Probing
exact same probe sequence, clustering together
(though less severe than primary)
10. LINEAR PROBING
10.1 Definition and Formula
In Linear Probing, if the target slot is occupied, the table is searched sequentially, one slot at a time, until an
empty slot is found:
h(k, i) = ( h(k) + i ) mod m, i = 0, 1, 2, 3, ...
Page 12
Data Structures — Unit IV: Non-Linear Data Structures
10.2 Worked Example
Insert keys 19, 27, 36, 10, 24, 17 into a hash table of size m = 7 using h(k) = k mod 7 with Linear Probing.
Key h(key) Probing / Action Final Index
19 5 slot 5 empty -> place directly 5
27 6 slot 6 empty -> place directly 6
36 1 slot 1 empty -> place directly 1
10 3 slot 3 empty -> place directly 3
24 3 slot 3 occupied -> try (3+1)mod7=4, empty -> place 4
17 3 slot 3 occupied, slot 4 occupied -> try (3+2)mod7=5, 0
occupied -> try (3+3)mod7=6, occupied -> try (3+4)mod7=0,
empty -> place
Final Table:
Index 0 : 17
Index 1 : 36
Index 2 : empty
Index 3 : 10
Index 4 : 24
Index 5 : 19
Index 6 : 27
10.3 Advantages and Disadvantages
Advantages Disadvantages
Simple to implement; good cache performance Suffers heavily from primary clustering as the table
(sequential access) fills up
No extra memory needed for pointers (unlike Performance degrades sharply when load factor α
chaining) approaches 1
11. QUADRATIC PROBING
11.1 Definition and Formula
Quadratic Probing resolves collisions by probing slots at increasing quadratic distances from the original hash
position, instead of a fixed linear step:
h(k, i) = ( h(k) + c1·i + c2·i² ) mod m, i = 0, 1, 2, 3, ...
(a common simplified form uses c1 = 0, c2 = 1: h(k,i) = ( h(k) + i² ) mod m )
To guarantee that every slot in the table can eventually be probed, the table size m is usually chosen to be a
prime number, and c1, c2 are chosen appropriately (e.g. c1 = c2 = 0.5 with m prime, or the simplified i² form).
11.2 Worked Example
Insert keys 19, 27, 36, 10, 24, 17 into a hash table of size m = 7 using h(k) = k mod 7 with Quadratic Probing, h(k,i)
= (h(k) + i²) mod 7.
Key h(key) Probing / Action Final Index
Page 13
Data Structures — Unit IV: Non-Linear Data Structures
19 5 slot 5 empty -> place 5
27 6 slot 6 empty -> place 6
36 1 slot 1 empty -> place 1
10 3 slot 3 empty -> place 3
24 3 slot 3 occupied -> try (3+1²)mod7=4, empty -> place 4
17 3 slot 3 occupied -> try (3+1²)mod7=4, occupied -> try 0
(3+2²)mod7=0, empty -> place
Final Table:
Index 0 : 17
Index 1 : 36
Index 2 : empty
Index 3 : 10
Index 4 : 24
Index 5 : 19
Index 6 : 27
11.3 Advantages and Disadvantages
Advantages Disadvantages
Reduces primary clustering significantly compared to Still suffers from secondary clustering (same start slot
linear probing -> same probe sequence)
Better distribution of keys across the table May fail to find an empty slot even if one exists,
unless table size/constants are chosen carefully
(works best when m is prime and α ≤ 0.5)
12. DOUBLE HASHING
12.1 Definition and Formula
Double Hashing uses a second, independent hash function h2(k) to determine the probe step size, rather than a
fixed sequence. This spreads out keys that collide at the same initial slot in very different directions, virtually
eliminating clustering:
h(k, i) = ( h1(k) + i × h2(k) ) mod m, i = 0, 1, 2, 3, ...
A commonly used second hash function: h2(k) = R − ( k mod R ), where R is
a prime number smaller than m
h2(k) must never evaluate to 0 (else probing would repeatedly hit the same slot), and m is usually chosen as
prime to guarantee that every slot is eventually probed.
12.2 Worked Example
Insert keys 19, 27, 36, 10 into a hash table of size m = 7 using h1(k) = k mod 7 and h2(k) = 5 − (k mod 5), with
Double Hashing h(k,i) = (h1(k) + i·h2(k)) mod 7.
Key h1(key) h2(key) Probing / Action Final Index
19 5 5-(19 mod 5)=1 slot 5 empty -> place 5
27 6 5-(27 mod 5)=3 slot 6 empty -> place 6
Page 14
Data Structures — Unit IV: Non-Linear Data Structures
36 1 5-(36 mod 5)=4 slot 1 empty -> place 1
10 3 5-(10 mod 5)=5 slot 3 empty -> place 3
(No collisions occurred in this example, so double hashing's benefit is best observed when several keys share the
same h1 value — each will jump by a different step size h2(k), avoiding the clustering seen in linear/quadratic
probing.)
12.3 Advantages and Disadvantages
Advantages Disadvantages
Produces the most uniform distribution among open More complex — requires computing two hash
addressing methods functions
Eliminates both primary and secondary clustering Slightly slower per probe due to the extra
computation of h2(k)
13. REHASHING
13.1 Definition
Rehashing is the process of creating a new, larger hash table (usually roughly double the previous size, and
typically chosen as the next prime number) and re-inserting every existing element into this new table using a
hash function based on the new table size, whenever the load factor of the current table exceeds a defined
threshold (commonly α > 0.7).
13.2 Why Rehashing Is Needed
● As more keys are inserted, the load factor α increases, which increases the probability and length of
collisions.
● In open addressing especially, performance degrades sharply as the table becomes full — search/insert
can approach O(n) instead of O(1).
● Rehashing restores an acceptable load factor, keeping average-case operations close to O(1) again.
13.3 Rehashing Algorithm
rehash():
1. Create a new table 'newTable' of larger size
(commonly next prime >= 2 * oldTableSize)
2. For every key present in the old table:
compute new_index = newHashFunction(key) // based on new size
insert key into newTable at new_index
(resolving any collisions using the chosen collision method)
3. Discard the old table; newTable becomes the current hash table
13.4 When Rehashing Is Triggered
Condition Typical Threshold
Separate Chaining Rehash when α (elements / table size) exceeds
about 1.0
Open Addressing (Linear/Quadratic/Double Hashing) Rehash when α exceeds about 0.7, since
performance degrades rapidly as the table nears
Page 15
Data Structures — Unit IV: Non-Linear Data Structures
full
13.5 Advantages of Rehashing
● Maintains a low load factor, preserving fast average-case O(1) performance.
● Prevents insertion failure in open addressing (which cannot exceed α = 1).
● Improves distribution of keys and reduces clustering/collision chains.
Exam Tip: For 20-mark hashing questions, always (1) compute the hash values, (2) show a clear step-by-step probing
table like the ones above, (3) draw the final hash table, and (4) mention the relevant advantage/disadvantage — this
structure covers the full mark split-up examiners look for.
14. QUICK REVISION: COLLISION RESOLUTION TECHNIQUES
Technique Storage Formula Main Drawback
Separate Chaining Linked list per slot index = h(k); append to list Extra memory for
pointers
Linear Probing Within table array h(k,i) = (h(k)+i) mod m Primary clustering
Quadratic Probing Within table array h(k,i) = (h(k)+i²) mod m Secondary clustering
Double Hashing Within table array h(k,i) = (h1(k)+i·h2(k)) mod m Extra computation
of h2(k)
15. PROBABLE 20-MARK EXAM QUESTIONS
1. Define Tree and explain the basic terminology associated with trees, with a suitable diagram.
2. Explain the different types of binary trees with diagrams and state their properties.
3. Write recursive algorithms for Preorder, Inorder, Postorder and Level Order traversals. Trace all four
traversals for a given binary tree.
4. Construct an expression tree for a given postfix expression and explain how it can be evaluated and
converted back to infix/prefix/postfix.
5. Explain insertion, deletion and searching operations in a Binary Search Tree with algorithms and a worked
example.
6. What is hashing? Explain any three types of hash functions with examples.
7. Explain collision resolution using Separate Chaining with a worked example.
8. Explain Linear Probing, Quadratic Probing and Double Hashing with worked examples, and compare them.
9. What is Rehashing? Explain why and when it is required, with its algorithm.
Page 16