Trees, heaps, hashing & graph traversal

An AVL tree is a binary search tree that keeps itself height-balanced. The balance factor of a node is the height of its left subtree minus that of its right subtree. The invariant is that this factor is always one of minus-one, zero, or plus-one. Whenever an insertion or deletion pushes a node out of range, the tree rebalances with rotations.

There are four cases, named by the shape of the offending path. LL (left-left, factor plus-two with left child leaning left) needs one right rotation. RR needs one left rotation. LR needs a left rotation on the child then a right rotation on the node; RL is the mirror. A rotation re-parents three subtrees in constant time while preserving the BST ordering.

Because the height of an AVL tree with n keys is at most about 1.44·log₂(n), search, insert and delete are all guaranteed O(log n) — the degenerate chains a plain BST can form never occur.

A binary heap is a complete binary tree stored compactly in an array: the node at index i has children at 2i+1 and 2i+2 and parent at (i-1)/2 (integer division). The heap property says every parent dominates its children — in a min-heap the parent is no larger, so the smallest key sits at the root; in a max-heap the largest sits at the root.

Insertion appends the new key at the end and sifts it up, swapping with its parent while the property is violated. Extract-root removes the top, moves the last element to the root, and sifts it down, swapping with its smaller (or larger) child until order is restored. Both touch only one root-to-leaf path, so both cost O(log n).

Build-heap from an arbitrary array sifts down every internal node from the last parent up to the root; a careful accounting shows this is O(n), not O(n log n). Heaps are the engine behind priority queues and heapsort.

A hash table stores keys in an array of m buckets, placing a key at index h(k) = k mod m. When two keys hash to the same bucket a collision occurs, and the resolution scheme decides what happens next.

Separate chaining keeps a linked list at each bucket; colliding keys are appended. Search scans only the chain at h(k). Linear probing is open addressing: on a collision it scans forward — h(k), h(k)+1, h(k)+2, modulo m — for the next free slot. It is cache-friendly but suffers primary clustering as runs of occupied slots grow.

Deletion under linear probing must leave a tombstone rather than a true empty, otherwise it would break the probe chain for later keys. Average operations are O(1) at low load; performance degrades as α approaches one.

A stack is last-in-first-out: push adds to the top, pop removes from the top. It models recursion, undo, and expression evaluation. A queue is first-in-first-out: enqueue adds at the rear, dequeue removes from the front — the model for buffering and scheduling.

A naive array queue wastes space as the front advances. A circular queue fixes this: front and rear indices wrap with modulo arithmetic, reusing slots a plain queue would abandon. With capacity C, the rear advances as (rear+1) mod C. Overflow is signalled when the structure is full; underflow when a pop or dequeue is attempted on an empty structure.

All operations — push, pop, enqueue, dequeue — are O(1): they touch only the top or the two end pointers, never the interior.

A linked list stores each element in a node that holds a value and a pointer to the next node; the list is reached through a head reference. Unlike an array, nodes need not be contiguous, so insertion and deletion are pointer rewires rather than bulk shifts — but there is no random access, so reaching position k costs O(k).

In a singly linked list each node points only forward. Insertion at the head is O(1): the new node points to the old head and becomes the head. Insertion at the tail or a position requires walking there first. Deletion splices a node out by linking its predecessor to its successor.

A doubly linked list adds a prev pointer, enabling backward traversal and O(1) deletion of a known node, at the cost of an extra pointer per node. Reversal of a singly list walks once, flipping each next pointer to the previous node — an O(n), O(1)-extra-space classic.

A graph is a set of vertices joined by edges. The two canonical ways to explore one from a source differ only in the order they pull vertices from their frontier. Breadth-first search uses a queue (FIFO): it visits the source, then all neighbours, then their neighbours — expanding outward in rings of increasing distance. On an unweighted graph BFS finds shortest paths in edges.

Depth-first search uses a stack (LIFO, often the call stack): it plunges as deep as possible along one branch before backtracking. DFS underlies cycle detection, topological sort, and connectivity.

Each search marks vertices as visited to avoid revisiting, and records a discovery (tree) edge when it first reaches a vertex. Those edges form the traversal tree drawn in green. Both run in O(V + E) time.