Data Structure and Algorithm with Java (old course)

A binary tree is a tree data structure in which each node has at most two children, called the left child and the right child. It may be empty. A binary tree with $n$ nodes has height at least $\lceil \log_2(n+1) \rceil - 1$ and at most $n-1$. It is used for expression trees, binary search trees and heaps.

A skip list is a probabilistic data structure built from several layers of sorted linked lists. The bottom layer contains all the elements, and each higher layer is a sparser "express lane" that skips over elements of the layer below. Search, insertion and deletion take $O(\log n)$ on average.

Build a max-heap by inserting the keys one by one and sifting up (swap with the parent while larger).

Final heap array: [44, 33, 22, 20, 12, 15, 18, 19, 20]

                 44
             /        \
           33          22
         /    \       /   \
       20     12    15    18
      /  \
    19    20

Every parent is greater than or equal to its children, so this is a valid max-heap.

An array-based linear queue with front, rear and size/capacity fields:

class Queue {
    int[] arr;
    int front = 0, rear = -1, capacity;

    Queue(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
    }

    void enqueue(int item) {
        if (rear == capacity - 1) {          // overflow check
            System.out.println("Queue is full (overflow)");
            return;
        }
        arr[++rear] = item;                   // insert at rear
        System.out.println(item + " inserted");
    }
}

The function first checks for overflow, then increments rear and stores the item there. Time complexity is $O(1)$.

An array-based linear queue with front, rear and size/capacity fields:

class Queue {
    int[] arr;
    int front = 0, rear = -1, capacity;

    Queue(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
    }

    void enqueue(int item) {
        if (rear == capacity - 1) {          // overflow check
            System.out.println("Queue is full (overflow)");
            return;
        }
        arr[++rear] = item;                   // insert at rear
        System.out.println(item + " inserted");
    }
}

The function first checks for overflow, then increments rear and stores the item there. Time complexity is $O(1)$.

Build a max-heap from $12, 23, 44, 56, 33, 67, 37$ (array indices 1 to 7, children of $i$ are $2i$ and $2i+1$).

Initial array: $[12, 23, 44, 56, 33, 67, 37]$

1. Heapify node 44 (children 67, 37): swap with 67 gives $[12, 23, 67, 56, 33, 44, 37]$.
2. Heapify node 23 (children 56, 33): swap with 56 gives $[12, 56, 67, 23, 33, 44, 37]$.
3. Heapify node 12 (children 56, 67): swap with 67 gives $[67, 56, 12, 23, 33, 44, 37]$, then 12 swaps with 44 (children 44, 37), giving the max-heap:

$[67, 56, 44, 23, 33, 12, 37]$

        67
      /    \
    56      44
   /  \    /  \
  23  33  12  37

Heap sort: swap the root with the last element of the heap, reduce the heap size and re-heapify.

Sorted result:

$12, 23, 33, 37, 44, 56, 67$

Theta ($\Theta$) notation gives a tight bound on the growth of a function. $f(n) = \Theta(g(n))$ if there are positive constants $c_1, c_2, n_0$ such that

$c_1\, g(n) \le f(n) \le c_2\, g(n) \quad \text{for all } n \ge n_0$

That is, $f(n)$ is bounded both above (Big-O) and below ($\Omega$) by $g(n)$. For example, $3n^2 + 2n = \Theta(n^2)$.

A self-adjusting data structure changes its own organisation automatically as it is accessed, so that frequently used elements become cheaper to reach. It needs no extra balance or count information. Examples are the splay tree (an accessed node is moved to the root by rotations) and the self-organising list (move-to-front, transpose, frequency count). It gives good amortised performance.

A priority queue is an abstract data type in which every element has a priority and the element with the highest priority (or lowest, in a min priority queue) is removed first, regardless of the order of insertion. Elements with equal priority are served in order of arrival. It is commonly implemented with a heap, giving $O(\log n)$ insertion and deletion.

A recursive function is tail recursive if the recursive call is the last operation it performs, so nothing remains to be done after the call returns. Such calls can be converted into a loop (tail-call optimisation), which saves stack space. Example:

int factTail(int n, int acc) {
    if (n <= 1) return acc;
    return factTail(n - 1, n * acc);
}

An expression tree is a binary tree that represents an arithmetic expression. Each leaf holds an operand and each internal node holds an operator whose children are its operands. For example, $(a+b)*c$ has * as root, with + (children a, b) as its left child and c as its right child. Its inorder traversal gives the infix, postorder the postfix and preorder the prefix form.

The best-case complexity of an algorithm is the minimum amount of time (or space) it takes over all inputs of size $n$, that is, the running time on the most favourable input. For example, linear search finds the key at the first position, so its best case is $O(1)$; insertion sort on an already sorted array has best case $O(n)$.

Linear probing is an open-addressing collision resolution method in hashing. If the slot $h(k)$ is already occupied, the table is searched sequentially for the next free slot:

$h(k, i) = (h(k) + i) \bmod m, \quad i = 0, 1, 2, \dots$

It is simple but suffers from primary clustering. For example, with $m = 10$ and $h(k) = k \bmod 10$, key 25 goes to slot 5, and key 35 (also hashing to 5) goes to slot 6.

Topological sorting is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every edge $u \to v$, vertex $u$ comes before $v$ in the ordering. It is possible only if the graph has no cycle. It can be found with DFS (reverse finishing order) or by repeatedly removing vertices of in-degree zero (Kahn's algorithm). It is used in task scheduling and in resolving course prerequisites.

The elementary (simple) sorting algorithms, each taking $O(n^2)$ time in the average and worst case, are:

1. Bubble sort: repeatedly swaps adjacent elements that are out of order.
2. Selection sort: repeatedly selects the smallest remaining element and places it in position.
3. Insertion sort: inserts each element into its correct place in the sorted part of the array.

Insertion sort in Java:

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];   // shift larger element right
            j--;
        }
        a[j + 1] = key;
    }
}

Each element a[i] is inserted into its correct place in the already sorted part a[0..i-1]. Time complexity is $O(n^2)$ in the worst case and $O(n)$ in the best case.

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}

class LinkedList {
    Node head;

    void insertEnd(int data) {
        Node n = new Node(data);
        if (head == null) { head = n; return; }
        Node t = head;
        while (t.next != null) t = t.next;
        t.next = n;
    }

    void display() {
        for (Node t = head; t != null; t = t.next)
            System.out.print(t.data + " -> ");
        System.out.println("null");
    }
}

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertEnd(10);
        list.insertEnd(20);
        list.insertEnd(30);
        list.display();   // 10 -> 20 -> 30 -> null
    }
}

class Stack {
    private int[] arr;
    private int top = -1;

    Stack(int size) { arr = new int[size]; }

    void push(int x) {
        if (top == arr.length - 1) {
            System.out.println("Stack overflow");
            return;
        }
        arr[++top] = x;
    }

    void display() {
        for (int i = top; i >= 0; i--)
            System.out.println(arr[i]);
    }
}

public class StackDemo {
    public static void main(String[] args) {
        Stack s = new Stack(5);
        s.push(10);
        s.push(20);
        s.push(30);
        s.display();   // 30 20 10 (top first)
    }
}

The program stores numbers in an array using the hash function $h(k) = k \bmod m$, with linear probing to resolve collisions.

public class HashDemo {
    static final int SIZE = 10;
    static int[] table = new int[SIZE];

    static void insert(int key) {
        int idx = key % SIZE;
        int count = 0;
        while (table[idx] != -1 && count < SIZE) {   // collision: probe next slot
            idx = (idx + 1) % SIZE;
            count++;
        }
        if (count == SIZE) System.out.println("Table full");
        else table[idx] = key;
    }

    public static void main(String[] args) {
        java.util.Arrays.fill(table, -1);            // -1 means empty
        int[] data = {25, 36, 15, 45, 7};
        for (int k : data) insert(k);
        for (int i = 0; i < SIZE; i++)
            System.out.println(i + " : " + (table[i] == -1 ? "-" : table[i]));
    }
}

Here 25 goes to index 5, 36 to 6, 15 collides at 5 and goes to 7, 45 goes to 8 and 7 collides at 7 and goes to 9.

Graph: a graph $G = (V, E)$ is a set of vertices $V$ and a set of edges $E$ connecting pairs of vertices. It may be directed or undirected, weighted or unweighted.

Dijkstra's algorithm (single-source shortest paths, non-negative weights):

1. Set $dist[s] = 0$ and $dist[v] = \infty$ for every other vertex; mark all vertices unvisited.
2. Pick the unvisited vertex $u$ with the smallest $dist[u]$ and mark it visited.
3. For each neighbour $v$ of $u$: if $dist[u] + w(u,v) < dist[v]$, set $dist[v] = dist[u] + w(u,v)$ and $prev[v] = u$.
4. Repeat steps 2 and 3 until all vertices are visited (or the destination is visited).

With a simple array it takes $O(V^2)$ time; with a min-heap, $O((V+E)\log V)$.

Example: edges A-B = 4, A-C = 2, B-C = 1, B-D = 5, C-D = 8, C-E = 10, D-E = 2. Source A.

Shortest distances from A: B = 3 (A-C-B), C = 2, D = 8 (A-C-B-D), E = 10 (A-C-B-D-E).

A B-tree of order $m$ is a balanced multiway search tree in which:

• every node has at most $m$ children and $m-1$ keys;
• every non-root internal node has at least $\lceil m/2 \rceil$ children;
• the root has at least 2 children (unless it is a leaf);
• all leaves are at the same level;
• keys inside a node are sorted, and a node with $k$ keys has $k+1$ children.

For order 3, each node holds 1 or 2 keys and has 2 or 3 children (a 2-3 tree). It is widely used in databases and file systems because the height is small, which reduces disk accesses.

Insertion: insert the key in the proper leaf. If the leaf overflows (3 keys), split it and push the middle key up to the parent; splits may propagate to the root, which is the only way the tree grows taller.

Example: insert 10, 20, 30, 40, 50, 60, 70.

1. Insert 10, 20: [10 20].
2. Insert 30: overflow [10 20 30], so 20 moves up. Root [20], leaves [10] and [30].
3. Insert 40: leaf [30 40].
4. Insert 50: leaf [30 40 50] overflows, so 40 moves up. Root [20 40], leaves [10], [30], [50].
5. Insert 60: leaf [50 60].
6. Insert 70: leaf [50 60 70] overflows, so 60 moves up and the root becomes [20 40 60], which overflows, so 40 moves up to a new root.

Final tree:

              [40]
           /        \
        [20]        [60]
        /  \        /  \
     [10] [30]   [50] [70]

All leaves are at the same level and every node satisfies the order-3 rules.

A data structure is a particular way of organising, storing and managing data in a computer so that it can be accessed and modified efficiently. Examples are arrays, linked lists, stacks, queues, trees and graphs. They are classified as linear (array, list, stack, queue) and non-linear (tree, graph).

Big Oh notation gives an upper bound on the growth rate of an algorithm's running time or space as the input size $n$ grows. It lets us compare algorithms independently of hardware, language and constant factors, and tells us the worst-case behaviour, e.g. $f(n)=3n^2+5n+2$ is $O(n^2)$.

Linked lists are preferred when the size is not known in advance or changes often. They grow and shrink dynamically, so no memory is wasted or overflowed, and insertion or deletion needs only pointer changes ($O(1)$ once the position is known) without shifting elements as in an array.

A linear queue is a linear data structure that follows the FIFO (First In First Out) principle. Insertion (enqueue) is done at the rear and deletion (dequeue) at the front. Its drawback is that once rear reaches the last index, no more insertions are possible even if front positions have been freed.

An activation record (stack frame) is the block of memory created on the call stack each time a function is called. It stores the function's parameters, local variables, return address and saved registers, and is removed when the function returns. In recursion, each call gets its own activation record.

A B-tree is a balanced multi-way search tree in which every node can hold several keys and have several children, and all leaves are at the same level. Keys inside a node are kept sorted, and the tree stays balanced through node splitting and merging. It is widely used for disk-based indexes and databases because it keeps the height small, so fewer disk accesses are needed.

Kruskal's algorithm is used to find the minimum spanning tree (MST) of a connected, weighted, undirected graph. It repeatedly picks the smallest-weight edge that does not form a cycle until $V-1$ edges are chosen.

Sorting is the process of arranging the elements of a list or file in a specified order, either ascending or descending (numerical or alphabetical), according to some key. Examples are bubble sort, merge sort, quick sort and heap sort.

Assume a singly circular linked list whose last node points back to the first node, with head pointing to the first node.

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}

class CircularList {
    Node head;

    void deleteLast() {
        if (head == null) {                       // empty list
            System.out.println("List is empty");
            return;
        }
        if (head.next == head) {                  // only one node
            head = null;
            return;
        }
        Node prev = head;
        while (prev.next.next != head) {          // stop at second last node
            prev = prev.next;
        }
        prev.next = head;                         // second last now points to head
    }
}

The loop stops at the second-last node, which is then linked to head, so the old last node is dropped. Time complexity is $O(n)$.

Taking the Fibonacci series as $0, 1, 1, 2, 3, 5, \dots$ the fourth element is $2$.

public class Fibonacci {
    public static void main(String[] args) {
        int n = 4;
        int a = 0, b = 1, result = 0;
        if (n == 1) result = a;
        else if (n == 2) result = b;
        else {
            for (int i = 3; i <= n; i++) {
                result = a + b;
                a = b;
                b = result;
            }
        }
        System.out.println("The " + n + "th element of Fibonacci series is " + result);
    }
}

Trace: $i=3$: result $=0+1=1$; $i=4$: result $=1+1=2$. Output: The 4th element of Fibonacci series is 2.

Use the hash function $h(k)=k \bmod 10$ and linear probing, i.e. on a collision try $(h(k)+i)\bmod 10$ for $i=1,2,\dots$

Final table:

Merge sort repeatedly divides the list into halves until single elements remain, then merges the sorted halves.

Divide

• $[36, 48, 23, 59, 68, 44, 97, 99, 91, 18, 33]$
• $[36, 48, 23, 59, 68, 44]$ and $[97, 99, 91, 18, 33]$
• $[36, 48, 23]$, $[59, 68, 44]$, $[97, 99, 91]$, $[18, 33]$
• $[36, 48]$, $[23]$, $[59, 68]$, $[44]$, $[97, 99]$, $[91]$, $[18]$, $[33]$
• single elements: 36, 48, 23, 59, 68, 44, 97, 99, 91, 18, 33

Merge

• $[36,48]+[23] \to [23, 36, 48]$
• $[59,68]+[44] \to [44, 59, 68]$
• $[97,99]+[91] \to [91, 97, 99]$
• $[18]+[33] \to [18, 33]$
• $[23,36,48]+[44,59,68] \to [23, 36, 44, 48, 59, 68]$
• $[91,97,99]+[18,33] \to [18, 33, 91, 97, 99]$
• $[23,36,44,48,59,68]+[18,33,91,97,99] \to$

$[18, 23, 33, 36, 44, 48, 59, 68, 91, 97, 99]$

Time complexity is $O(n\log n)$.

Let the B-tree have order $m$, so a node holds at most $m-1$ keys and at most $m$ children.

Steps

1. Start at the root and search down the tree, comparing the key with the keys of each node to choose the correct child, until a leaf is reached. (If the key already exists, stop.)
2. Insert the key into that leaf at its sorted position.
3. If the leaf now has at most $m-1$ keys, stop.
4. If the leaf overflows (has $m$ keys), split it: take the median key, keep the keys left of the median in one node and the keys right of it in a new node.
5. Move the median key up into the parent, with the two new nodes as its adjacent children.
6. If the parent now overflows, repeat the split on the parent, and continue upwards as needed.
7. If the root splits, create a new root holding the median key. This is the only way the tree grows in height.

Example (order 3, max 2 keys per node): insert 10, 20, 30.

• 10 and 20 go into the root: $[10, 20]$.
• Inserting 30 gives $[10, 20, 30]$, which overflows. The median 20 moves up into a new root, with children $[10]$ and $[30]$.

Inserting 40 then goes to the leaf $[30, 40]$, and inserting 50 makes $[30, 40, 50]$, which splits and pushes 40 up to give root $[20, 40]$ with children $[10]$, $[30]$, $[50]$.

Deleting a node from a binary (search) tree has three cases, depending on the number of children of the node to be deleted.

Case 1: node is a leaf. Simply remove it by setting the parent's pointer to null.

Example: deleting 20 from the tree below.

    50            50
   /  \    ->    /  \
  30   70       30   70
 /               
20               

Case 2: node has one child. Replace the node by its only child, i.e. link the parent directly to that child.

Example: delete 30 (which has only the left child 20); 50's left pointer now points to 20.

Case 3: node has two children. Replace the node's value with its inorder successor (the smallest node in the right subtree) or its inorder predecessor (the largest in the left subtree), then delete that successor node, which has at most one child and falls under case 1 or 2.

Example:

      50                60
     /  \              /  \
   30    70    ->     30    70
        /  \                 \
      60    80                80

To delete 50, the inorder successor is 60 (the minimum of the right subtree). Copy 60 to the root and delete the original 60 node.

The time taken is $O(h)$, where $h$ is the height of the tree.

A doubly linked list is a linked list in which each node has three fields: the data, a pointer prev to the previous node and a pointer next to the next node. It can therefore be traversed in both forward and backward directions.

A cut vertex (articulation point) is a vertex of a connected graph whose removal, together with its incident edges, disconnects the graph or increases the number of connected components.

A spanning tree of a connected graph $G=(V,E)$ is a subgraph that includes all the vertices of $G$, is connected and contains no cycle. It has exactly $V-1$ edges.

A circular queue is a queue in which the last position is connected back to the first position, so the array is treated as a circle. When rear reaches the end, it wraps around using $rear=(rear+1)\bmod n$, so freed positions at the front are reused. This avoids the wasted space of a linear queue.

Worst-case complexity gives an upper bound that guarantees the algorithm will never take longer than that for any input of size $n$. The best case is rarely met and gives no useful guarantee, and the average case needs assumptions about the input distribution and is hard to compute. The worst case is also often close to the average, and it matters for critical applications.

Nested recursion is a form of recursion in which a recursive function passes a recursive call to itself as its own argument. An example is the Ackermann function, where $A(m,n)=A(m-1,A(m,n-1))$ for $m,n>0$.

Hashing is a technique for storing and retrieving data directly using a hash function $h(k)$ that maps a key $k$ to an index of a hash table, giving average access time of $O(1)$. A collision occurs when two different keys map to the same index.

Collision resolution approaches

1. Separate chaining (open hashing): each table slot holds a linked list of all the keys that hash to that slot.
2. Open addressing (closed hashing): all keys are stored in the table itself, and another empty slot is probed on a collision:
   • Linear probing: try $(h(k)+i)\bmod m$ for $i=1,2,\dots$
   • Quadratic probing: try $(h(k)+i^2)\bmod m$.
   • Double hashing: try $(h_1(k)+i\cdot h_2(k))\bmod m$ using a second hash function.
3. Rehashing: build a larger table with a new hash function when the table becomes too full.

The order of a B-tree is the maximum number of children a node can have. A B-tree of order $m$ has at most $m$ children and $m-1$ keys per node, and every non-root internal node has at least $\lceil m/2\rceil$ children.

A heap is a complete binary tree in which every node satisfies the heap property. In a max-heap each parent is greater than or equal to its children, so the largest element is at the root. In a min-heap each parent is less than or equal to its children, so the smallest is at the root. It is commonly stored in an array and used in heap sort and priority queues.

Assume a singly circular linked list with head pointing to the first node and positions numbered from 1.

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}

class CircularList {
    Node head;

    void deleteAt(int pos) {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        if (pos == 1) {                           // delete first node
            if (head.next == head) {              // only one node
                head = null;
            } else {
                Node last = head;
                while (last.next != head) last = last.next;
                head = head.next;
                last.next = head;
            }
            return;
        }
        Node prev = head;
        for (int i = 1; i < pos - 1; i++) {       // move to node before target
            prev = prev.next;
            if (prev == head) {
                System.out.println("Invalid position");
                return;
            }
        }
        Node target = prev.next;
        if (target == head) {
            System.out.println("Invalid position");
            return;
        }
        prev.next = target.next;                  // unlink target
    }
}

For position 1 the last node must be re-linked to the new head; for any other position the previous node simply skips the target. Time complexity is $O(n)$.

Quick sort picks the first element as pivot, places elements smaller than the pivot to its left and the rest to its right, then sorts each part recursively.

Data: $5, 66, 3, 8, 91, 45, 88, 91, 33$

1. Pivot 5: left $[3]$, right $[66, 8, 91, 45, 88, 91, 33]$, giving $[3]\ 5\ [66, 8, 91, 45, 88, 91, 33]$.
2. Sort the right part, pivot 66: left $[8, 45, 33]$, right $[91, 88, 91]$.
3. Left part $[8, 45, 33]$, pivot 8: left empty, right $[45, 33]$.
4. $[45, 33]$, pivot 45: left $[33]$, giving $33, 45$. So the left part becomes $8, 33, 45$.
5. Right part $[91, 88, 91]$, pivot 91: left $[88]$, right $[91]$, giving $88, 91, 91$.

Combining everything:

$3, 5, 8, 33, 45, 66, 88, 91, 91$

Average time is $O(n\log n)$ and worst case is $O(n^2)$.

The edges are $A\to B$, $A\to D$, $B\to C$, $D\to E$, $E\to C$, $F\to D$. The constraints are: $A$ and $F$ come before $D$; $D$ before $E$; $E$ and $B$ before $C$; $A$ before $B$.

In-degrees: $A=0$, $F=0$, $B=1$, $D=2$, $E=1$, $C=2$. So $A$ and $F$ are the possible starting vertices. Repeatedly removing a vertex with in-degree 0 and exploring all choices gives exactly 7 orderings:

1. $A, B, F, D, E, C$
2. $A, F, B, D, E, C$
3. $A, F, D, B, E, C$
4. $A, F, D, E, B, C$
5. $F, A, B, D, E, C$
6. $F, A, D, B, E, C$
7. $F, A, D, E, B, C$

Problem with binary (search) trees: their performance depends on the shape of the tree. Search, insertion and deletion take $O(h)$, and if keys arrive in sorted or nearly sorted order the tree degenerates into a skewed tree, like a linked list, with height $n$, so operations become $O(n)$ instead of $O(\log n)$. Plain binary trees also do not exploit the fact that some nodes are accessed more often than others.

Self-adjusting tree: a binary search tree that restructures itself after each access so that frequently accessed nodes move nearer to the root. It needs no balance information stored in the nodes. The common approaches are:

• Move-to-root: after accessing a node, rotate it up until it becomes the root.
• Splay tree: after accessing a node, perform splaying, a sequence of rotations (zig, zig-zig, zig-zag) that brings it to the root. This gives $O(\log n)$ amortized time per operation.

Example: in the chain 10 (root) with right child 20, whose right child is 30, accessing 30 splays it:

10                      30
  \                    /
   20     splay 30    20
     \    ------->   /
      30            10

Here a zig-zig step rotates the parent and grandparent in turn, so 30 becomes the root. Repeated accesses to 30 are then $O(1)$, and splaying a deeper node also roughly halves the depth of the nodes along its access path, which keeps the amortized cost at $O(\log n)$.

Limitations of B-tree

• Nodes are not always full, so up to about half of the node space can be wasted.
• Insertion and deletion are complex (splitting, borrowing and merging).
• Searching within a node is needed, so in-memory use is less efficient than for simpler trees.
• Keys and data are stored in internal nodes too, so sequential access to all records is awkward (this is solved by the B+ tree).

Deletion of a key (order $m$; every non-root node must keep at least $\lceil m/2\rceil-1$ keys)

1. Search for the key.
2. If it is in a leaf, remove it. If the leaf still has the minimum number of keys, stop.
3. If it is in an internal node, replace it by its inorder predecessor or successor (taken from a leaf), and delete that key from the leaf.
4. If a node has fewer than the minimum keys (underflow):
   • Borrow: if an adjacent sibling has more than the minimum, rotate a key from the sibling through the parent.
   • Merge: otherwise merge the node with a sibling and the separating key from the parent. This may cause an underflow in the parent, so repeat upwards.
5. If the root becomes empty, the merged node becomes the new root and the height decreases by one.

Example (order 3, max 2 keys, min 1 key): root $[20, 40]$ with leaves $[10]$, $[30]$, $[50]$.

• Delete 30: the leaf becomes empty (underflow), and its siblings $[10]$ and $[50]$ have only the minimum, so merge. The leaf $[30]$ merges with $[10]$ and the separator 20, giving $[10, 20]$. The root is now $[40]$ with children $[10, 20]$ and $[50]$.
• Delete 10 next: the leaf $[10,20]$ becomes $[20]$, which is fine.

A data structure is a particular way of organizing, storing and managing data in a computer so that it can be accessed and modified efficiently. Examples are arrays, linked lists, stacks, queues, trees and graphs.

A stack follows LIFO (Last In First Out): insertion and deletion both happen at one end, the top, using push and pop. A queue follows FIFO (First In First Out): insertion happens at the rear and deletion at the front, using enqueue and dequeue.

A doubly linked list can be traversed in both directions because each node has prev and next pointers. A node can also be deleted given only a pointer to it, since its predecessor is directly available, whereas in a singly linked list the list must be traversed to find the previous node. The cost is extra memory for the additional pointer.

• Recursive code is shorter, simpler and easier to read and understand.
• It is the natural way to express problems that are defined recursively, such as tree traversal, factorial, Tower of Hanoi and divide-and-conquer algorithms.
• It reduces the need to manage loop variables and temporary state explicitly, so there are fewer chances of logical errors.
• Backtracking problems are much easier to write recursively.

A Binary Search Tree (BST) is a binary tree in which, for every node, all keys in its left subtree are smaller than the node's key and all keys in its right subtree are larger. An inorder traversal gives the keys in sorted order, and search, insertion and deletion take $O(h)$ time, where $h$ is the height.

A multi-way tree (m-way tree) is a tree in which each node can have more than two children, up to $m$ children and $m-1$ keys, with the keys in a node kept sorted. It generalises the binary search tree, and B-trees are balanced multi-way search trees.

A weighted graph is a graph $G=(V,E)$ in which each edge is assigned a numerical value called its weight (cost, distance or time). Weighted graphs are used in problems such as shortest path and minimum spanning tree.

A graph can be represented in a computer in two main ways: the adjacency matrix, which is a $V\times V$ array where entry $(i,j)$ shows whether an edge exists, and the adjacency list, which keeps a linked list of the neighbours of each vertex. (An incidence matrix or an edge list can also be used.)

Tail recursion is a form of recursion in which the recursive call is the very last operation performed by the function, so nothing remains to be done after the call returns. It can be converted easily into a loop and optimised by compilers to avoid growing the call stack. For example, gcd(a,b) returning gcd(b, a % b) is tail recursive.

Common hash functions are:

• Division method: $h(k) = k \bmod m$.
• Multiplication method: $h(k) = \lfloor m\,(kA \bmod 1)\rfloor$, with $0<A<1$.
• Mid-square method: square the key and take the middle digits as the address.
• Folding method: split the key into parts, add them (shift or boundary folding) and take the result modulo table size.
• Digit analysis and truncation methods: select or drop certain digits of the key.

A stack can be implemented with an array and a top index. Push adds at top, pop removes from top, and traversal prints elements from top to bottom.

class Stack {
    int[] data = new int[100];
    int top = -1;

    void push(int x) {
        if (top == data.length - 1) {
            System.out.println("Stack overflow");
            return;
        }
        data[++top] = x;
    }

    int pop() {
        if (top == -1) {
            System.out.println("Stack underflow");
            return -1;
        }
        return data[top--];
    }

    void traverse() {
        if (top == -1) {
            System.out.println("Stack is empty");
            return;
        }
        for (int i = top; i >= 0; i--)
            System.out.print(data[i] + " ");
        System.out.println();
    }
}

Each of push and pop takes $O(1)$ time, and traversal takes $O(n)$.

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; }
}

class DoublyLinkedList {
    Node head;

    // insert value x at position pos (1-based)
    void insertAt(int x, int pos) {
        Node n = new Node(x);
        if (pos == 1) {                  // insert at beginning
            n.next = head;
            if (head != null) head.prev = n;
            head = n;
            return;
        }
        Node cur = head;
        for (int i = 1; i < pos - 1 && cur != null; i++)
            cur = cur.next;
        if (cur == null) {
            System.out.println("Invalid position");
            return;
        }
        n.next = cur.next;
        n.prev = cur;
        if (cur.next != null) cur.next.prev = n;
        cur.next = n;
    }
}

The function walks to the node just before the required position, then links the new node by setting its next and prev pointers and updating the neighbouring nodes. Time complexity is $O(n)$.

Insert the keys one by one at the next free leaf and sift up while the node is larger than its parent. The array is shown after each insertion.

1. Insert 17: [17]
2. Insert 27: it is greater than 17, so swap: [27, 17]
3. Insert 16: [27, 17, 16]
4. Insert 29: swap with parent 17, then with parent 27: [29, 27, 16, 17]
5. Insert 35: swap with parent 27, then with 29: [35, 29, 16, 17, 27]
6. Insert 20: swap with parent 16: [35, 29, 20, 17, 27, 16]
7. Insert 75: swap with parent 20, then with 35: [75, 29, 35, 17, 27, 16, 20]
8. Insert 18: swap with parent 17: [75, 29, 35, 18, 27, 16, 20, 17]
9. Insert 35: swap with parent 18, then with 29 (the parent 75 is larger, so stop): [75, 35, 35, 29, 27, 16, 20, 17, 18]

Final max heap (array form): 75, 35, 35, 29, 27, 16, 20, 17, 18.

            75
          /    \
        35      35
       /  \    /  \
     29   27  16   20
    /  \
  17   18

Using the division method with linear probing to resolve collisions:

class HashTable {
    int size = 10;
    int[] table = new int[size];

    HashTable() {
        java.util.Arrays.fill(table, -1);   // -1 means empty
    }

    int hash(int key) {
        return key % size;
    }

    void insert(int key) {
        int index = hash(key);
        int count = 0;
        while (table[index] != -1 && count < size) {
            index = (index + 1) % size;      // linear probing
            count++;
        }
        if (count == size) {
            System.out.println("Hash table is full");
            return;
        }
        table[index] = key;
    }
}

hash() maps the key to a slot. If the slot is taken, insert() moves to the next slot (wrapping around) until a free one is found.

Radix sort processes digits from the least significant to the most significant, using a stable bucket pass for each digit.

Data: 23, 76, 53, 40, 67, 1, 213, 21

Pass 1 (units digit):

• 0: 40
• 1: 1, 21
• 3: 23, 53, 213
• 6: 76
• 7: 67

Result: 40, 1, 21, 23, 53, 213, 76, 67

Pass 2 (tens digit):

• 0: 1
• 1: 213
• 2: 21, 23
• 4: 40
• 5: 53
• 6: 67
• 7: 76

Result: 1, 213, 21, 23, 40, 53, 67, 76

Pass 3 (hundreds digit):

• 0: 1, 21, 23, 40, 53, 67, 76
• 2: 213

Result: 1, 21, 23, 40, 53, 67, 76, 213

B-tree: a B-tree of order $m$ is a self-balancing multiway search tree in which:

• every node has at most $m$ children and at most $m-1$ keys, stored in sorted order;
• every non-root internal node has at least $\lceil m/2 \rceil$ children, and the root has at least 2 children if it is not a leaf;
• all leaves are on the same level;
• the keys of a node separate the key ranges of its children, as in a search tree.

Insertion splits a full node and pushes the middle key up. Deletion borrows from or merges with siblings. Both keep the tree balanced.

Benefits over a binary search tree:

1. A BST can become skewed (height $O(n)$), while a B-tree is always balanced with height $O(\log n)$.
2. A B-tree node holds many keys, so the height is much smaller and fewer node accesses are needed. This matters when nodes are disk blocks, since each access is costly.
3. It suits databases and file systems that store large data on secondary storage.
4. Search, insertion and deletion are all guaranteed $O(\log n)$ in the worst case.
5. Nodes are kept at least half full, which makes good use of space.

Depth first search (DFS) visits a graph by going as deep as possible along each branch before backtracking. Starting from a vertex, it marks the vertex visited, then recursively visits each unvisited neighbour (or uses an explicit stack). When a vertex has no unvisited neighbours, the search backtracks to the previous vertex.

DFS(v):
    mark v as visited
    for each neighbour w of v:
        if w is not visited:
            DFS(w)

Its time complexity is $O(V+E)$ with an adjacency list.

Cycle detection using DFS:

• Undirected graph: run DFS, tracking the parent of each vertex. If a vertex has a visited neighbour that is not its parent, a back edge exists, so the graph has a cycle.
• Directed graph: keep a "currently in recursion stack" flag for each vertex. If DFS reaches a vertex that is already in the recursion stack, a back edge exists and there is a cycle. Equivalently, if a topological sort cannot include all vertices, the graph has a cycle.

If DFS finishes with no back edge, the graph is acyclic.

In a queue, front is the end from which elements are removed (dequeued), and rear is the end at which new elements are inserted (enqueued). A queue follows the FIFO (first in, first out) rule.

Big Oh notation gives an asymptotic upper bound on an algorithm's running time. $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $f(n) \le c\,g(n)$ for all $n \ge n_0$.

Recursion is a technique in which a function calls itself, directly or indirectly, to solve a smaller instance of the same problem. It needs a base case to stop the calls and a recursive case that reduces the problem, for example $n! = n\times(n-1)!$ with $0! = 1$.

A B-tree is a self-balancing multiway search tree of order $m$ in which each node holds up to $m-1$ sorted keys and up to $m$ children, and all leaves are at the same level. It gives $O(\log n)$ search, insertion and deletion and is widely used in databases and file systems.

Breadth first traversal visits a graph level by level. It starts from a source vertex, visits all its neighbours, then all their unvisited neighbours, and so on, using a queue. Its time complexity is $O(V+E)$.

A linked list is a linear data structure made of nodes, where each node stores data and a reference (pointer) to the next node. The nodes need not be contiguous in memory, so insertion and deletion are easy and the size can grow dynamically. Types include singly, doubly and circular linked lists.

• Binary search takes $O(\log n)$ comparisons, while linear search takes $O(n)$, so it is much faster for large data.
• It halves the search range at each step, so it needs very few comparisons (about 20 for a million items).

It requires the data to be sorted and to allow direct access, as in an array.

The shortest path problem is the problem of finding a path between two vertices of a weighted graph so that the sum of the edge weights along the path is minimum. Dijkstra's algorithm (non-negative weights) and the Bellman-Ford algorithm are used to solve it.

An AVL tree is a self-balancing binary search tree in which the heights of the left and right subtrees of every node differ by at most 1. The balance factor (height of left subtree minus height of right subtree) of every node is $-1$, $0$ or $+1$. When an insertion or deletion breaks this, rotations restore balance, so operations remain $O(\log n)$.

class Stack {
    private int[] arr;
    private int top;
    private int capacity;

    Stack(int size) {
        capacity = size;
        arr = new int[size];
        top = -1;
    }

    boolean isEmpty() { return top == -1; }
    boolean isFull()  { return top == capacity - 1; }

    void push(int x) {
        if (isFull()) {
            System.out.println("Stack overflow");
            return;
        }
        arr[++top] = x;
    }

    int pop() {
        if (isEmpty()) {
            System.out.println("Stack underflow");
            return -1;
        }
        return arr[top--];
    }

    public static void main(String[] args) {
        Stack s = new Stack(5);
        s.push(10);
        s.push(20);
        s.push(30);
        System.out.println(s.pop());   // 30
        System.out.println(s.pop());   // 20
    }
}

Both push and pop run in $O(1)$ time. The stack is LIFO: the last element pushed is the first popped.

Assumptions: each node has data, prev and next; head points to the first node; the list is circular, so head.prev is the last node and the last node's next is head.

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; }
}

class CircularDLL {
    Node head;

    void insertAtEnd(int x) {
        Node n = new Node(x);
        if (head == null) {          // empty list
            n.next = n;
            n.prev = n;
            head = n;
            return;
        }
        Node last = head.prev;       // current last node
        n.next = head;
        n.prev = last;
        last.next = n;
        head.prev = n;
    }
}

Because the last node is reached through head.prev, the insertion takes $O(1)$ time.

Hash function: $h(k) = k \bmod 10$, with linear probing for collisions.

int[] table = new int[10];          // 0 means empty (no key is 0)

void insert(int key) {
    int i = key % 10;
    while (table[i] != 0)
        i = (i + 1) % 10;           // linear probing
    table[i] = key;
}

Inserting 24, 20, 37, 84, 50, 47, 67, 74:

Final table:

Kruskal's algorithm builds a minimum spanning tree by sorting all edges by weight and adding each edge in turn if it does not form a cycle. Cycles are detected with a disjoint-set (union-find) structure.

Algorithm:

1. Sort all edges in non-decreasing order of weight.
2. Make each vertex its own set.
3. For each edge $(u,v)$ in order: if find(u) differs from find(v), add the edge to the tree and union the sets.
4. Stop when $V-1$ edges have been chosen.

import java.util.*;

class Edge {
    int u, v, w;
    Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
}

class Kruskal {
    static int[] parent;

    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }

    static void kruskal(int V, List<Edge> edges) {
        Collections.sort(edges, (a, b) -> a.w - b.w);
        parent = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;

        int count = 0, total = 0;
        for (Edge e : edges) {
            int ru = find(e.u), rv = find(e.v);
            if (ru != rv) {
                parent[ru] = rv;
                System.out.println(e.u + " - " + e.v + " : " + e.w);
                total += e.w;
                if (++count == V - 1) break;
            }
        }
        System.out.println("Total weight = " + total);
    }
}

Time complexity is $O(E \log E)$, dominated by sorting.

Topological sort is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every edge $u \to v$, vertex $u$ comes before $v$. It exists only if the graph has no cycle. It is used for task scheduling, course prerequisites and build order.

Algorithm (Kahn's, using in-degrees):

1. Compute the in-degree of every vertex.
2. Put all vertices of in-degree 0 into a queue.
3. Remove a vertex from the queue, output it, and reduce the in-degree of its neighbours by 1. Enqueue any that become 0.
4. Repeat until the queue is empty. If fewer than all vertices were output, the graph has a cycle.

Alternatively, run DFS and output vertices in reverse order of finishing time.

Example: edges $A\to B$, $A\to C$, $B\to D$, $C\to D$.

• In-degrees: A=0, B=1, C=1, D=2.
• Output A; B and C drop to 0.
• Output B (D becomes 1), then C (D becomes 0).
• Output D.

Topological order: A, B, C, D (A, C, B, D is also valid).

Time complexity is $O(V+E)$.

No. For large inputs an $O(n\log n)$ algorithm is better than an $O(n^2)$ algorithm, because $n\log n$ grows much more slowly than $n^2$. Big Oh describes the growth rate for large $n$ and hides constant factors, so for small $n$ an $O(n^2)$ algorithm with a small constant can still be faster.

Example (comparison counts, ignoring constants):

Bubble sort ($O(n^2)$) on one million items needs about $10^{12}$ steps. Merge sort ($O(n\log n)$) needs about $2\times10^{7}$ steps, which is roughly 50,000 times fewer.

The reverse can hold for small $n$. For example, if the $O(n^2)$ algorithm takes $n^2$ steps and the $O(n\log n)$ one takes $100\,n\log_2 n$ steps, the quadratic one is faster for small $n$ (below about 600) because of the large constant. Beyond the crossover point, $O(n\log n)$ wins and the gap keeps widening.

So $O(n\log n)$ is better asymptotically, but it need not win for small inputs.

Limitations of a binary search tree (BST):

1. The shape depends on the order of insertion. Inserting sorted data (1, 2, 3, ...) produces a skewed tree like a linked list, with height $n$.
2. In that worst case, search, insertion and deletion take $O(n)$ instead of $O(\log n)$.
3. There is no automatic balancing, so performance is unpredictable.
4. Each node holds only one key, so for large data on disk the tree is deep and needs many accesses.

Splaying: a splay tree is a self-adjusting BST. After every access (search, insert or delete), the accessed node is moved to the root by a sequence of rotations (zig, zig-zig, zig-zag). Splaying is used because:

• recently accessed items stay near the root, so repeated or nearby accesses are fast (locality of reference);
• it keeps the tree roughly balanced without storing height or balance information, so no extra memory is needed;
• the amortized cost of each operation is $O(\log n)$, even though a single operation may take $O(n)$;
• the rotations also shorten long paths, so a skewed tree gradually becomes more balanced.