Chapter 8 — Data Structures

What is a data structure? A data structure is a way to organise, store and manage data in memory so that different operations (like search, insertion, deletion and traversal) can be performed efficiently. Data structures are the practical forms that realise abstract models of collections of items. Choosing a suitable structure determines both the running time and memory use of a program.

Abstract Data Type (ADT) An ADT specifies the operations allowed on a collection of values and the expected behaviour or semantics of those operations. For example, a List ADT defines operations such as add, remove, get and size without specifying how these are implemented. The separation between the ADT (interface) and its implementation is central to modular software design.

Interface versus implementation Designing with ADTs lets code that uses a structure remain independent of implementation choices. For example, a List ADT can be implemented using an array or a linked list; both provide the same external operations but have different performance trade-offs. This separation makes programs easier to maintain and optimise later: swap an implementation without changing callers.

Basic operations and their costs Typical operations include traversal (visiting elements), insertion, deletion, lookup/search and update. Each operation incurs time and sometimes extra memory. We measure these costs asymptotically (big-O notation) to understand behaviour for large inputs. For example, arrays give constant-time random access but insertion in the middle may cost O(n); linked lists allow O(1) insertion at known positions but random access is O(n).

Memory organisation Some structures use contiguous memory (arrays) while others use nodes with pointers (linked lists, trees). Contiguous layouts benefit from CPU cache locality and simple address arithmetic; pointer-based structures excel when dynamic growth and frequent insert/delete operations are needed.

Trade-offs and selection No single data structure is best for every problem. Choosing a right structure depends on the expected operations and their frequency. For example, if many lookups by key are needed, a hash table or balanced search tree is appropriate; for smallest memory overhead with predictable size, an array may be better. Understanding these trade-offs is the core goal of this introductory topic and sets the stage for studying concrete structures in detail.

Definition and storage An array is a collection of elements of the same data type stored in contiguous memory locations. Each element is accessible by an index, usually starting at 0. Because elements are adjacent in memory, the address of an element can be computed by a simple formula: base_address + index * size_of(element). This gives arrays the important advantage of constant-time random access: accessing A[i] is O(1).

One-dimensional arrays One-dimensional arrays model lists and tables of values with fixed capacity. You declare an array with a capacity and fill positions as needed. Traversing the entire array to perform an operation on each element costs O(n). Insertion at the end (if space exists) can be O(1), but insertion or deletion in the middle requires shifting elements, costing O(n) in the worst case.

Dynamic arrays Languages often provide resizable arrays (dynamic arrays or array lists) that grow automatically. When full, they allocate a larger block (commonly doubling capacity) and copy existing elements. Amortised cost of appending elements is O(1) despite occasional costly copies, because copies happen infrequently.

Multidimensional arrays Multidimensional arrays (e.g., 2D arrays or matrices) are arrays of arrays conceptually. A 2D array with m rows and n columns occupies m × n contiguous elements in one of two common orders: row-major (rows stored one after another) or column-major (columns stored consecutively). For performance, it is important to access elements in the memory order (row-major prefer iterating rows first) to use CPU caches effectively.

Operations and complexity Common operations include indexing (O(1)), traversal (O(n)), searching unsorted arrays (O(n)), and searching sorted arrays using binary search (O(log n)). Sorting an array costs O(n log n) with efficient algorithms. Arrays are ideal when you need fast random access, predictable memory layout and simple indexing arithmetic.

Limitations and use-cases Arrays have fixed capacity (unless dynamic) and resizing can be costly. They are poor at frequent insertions/deletions in the middle. Arrays are well-suited for implementing heaps, storing matrices in numerical computations, look-up tables, and cases where elements are accessed by position often.

Practical notes Choose array size carefully and prefer dynamic arrays for variable-size collections. Understand the memory layout (row-major/column-major) when working with multidimensional arrays to write cache-friendly loops and improve performance.

Structure and node layout A linked list stores data in nodes where each node contains the data value and one or more pointers (references) to other nodes. In a singly linked list each node has a pointer to the next node; in a doubly linked list each node also stores a pointer to the previous node. The list maintains a head pointer to the first node and optionally a tail pointer to the last node. Nodes need not be contiguous in memory; they may be allocated individually and linked together.

Creation and traversal To traverse a singly linked list, start at head and follow next pointers until a null terminator is reached. Traversal visits all nodes and costs O(n). A doubly linked list allows traversal in both directions using next and prev pointers, which is helpful when operations need access to both neighbours.

Insertion and deletion Insertion at the beginning of a singly linked list is O(1): create a node, set its next to head and update head. Insertion at a given position requires locating the previous node (O(n) worst-case) and updating pointers. Deleting the head is O(1); deleting an arbitrary node in singly linked list requires access to its previous node to update its pointer. In doubly linked lists deletion of a node is simpler because prev pointer is available; updates adjust next and prev of neighbouring nodes. Maintaining a tail pointer allows O(1) insertion at the end.

Special forms and variants Circular linked lists connect the tail back to the head, making traversal wrap around; they are useful in round-robin scheduling. Sentinel or dummy nodes can simplify code by removing special-case checks for empty lists or head/tail operations.

Advantages and disadvantages Linked lists allow dynamic growth without copying and efficient insert/delete when node location is known. However, random access by index is slow (O(n)), and extra memory is used for pointers. Pointer manipulation requires careful handling to avoid segmentation faults, memory leaks or broken lists. Also linked lists have worse cache performance than arrays because nodes are scattered in memory.

Applications Linked lists are used to implement stacks and queues (pointer-based), adjacency lists for graph representation, dynamic memory pools, and when frequent insertions/deletions are required. They are also used internally in many library containers where iterator stability is important.

Definition and core operations A stack is an abstract data type that follows Last-In-First-Out (LIFO) order: the last element inserted is the first to be removed. The principal operations are push (place an element on top), pop (remove and return the top element), and peek/top (inspect the top element without removing it). Stacks can be implemented using arrays or linked lists; both provide constant-time push and pop when implemented correctly.

Array-based implementation An array-based stack maintains an index (top) that points to the current top position. To push, increment top and store the value at that index; to pop, read the value at top and decrement top. Array-based stacks have fixed capacity unless implemented with a dynamic resizing scheme. One must handle overflow (push on full stack) and underflow (pop on empty stack).

Linked-list implementation A stack implemented with a linked list uses the head of the list as the top. Push creates a new node and links it as the new head; pop removes the head node. This avoids fixed capacity limits and gives push/pop O(1) performance until memory is exhausted.

Applications in computing Stacks are central to many programming tasks: function call management (runtime call stack) stores return addresses and local variables; expression evaluation and parsing use stacks to manage operators and operands; implementing undo functionality in editors, depth-first search in graphs, backtracking algorithms and syntax checking (parentheses matching) all rely on stacks.

Expression parsing and evaluation Converting infix expressions to postfix (or prefix) uses stacks to reorder operators respecting precedence and associativity. Postfix expressions are evaluated easily by scanning and using a stack: push operands, and when encountering an operator pop operands, apply operator and push result. This avoids managing operator precedence at evaluation time.

Error conditions and performance In array-based stacks, overflow occurs when pushing into a full array; in linked-list stacks, pushing may fail if memory allocation fails. Underflow occurs when popping from an empty stack. Time complexity for push, pop and peek is O(1) and space required is O(n) to store n elements. Choose implementation based on expected maximum size, memory constraints and required performance properties.

Queue basics A queue is a linear data structure that follows First-In-First-Out (FIFO) ordering: elements are removed in the same order they were added. Main operations are enqueue (insert element at the rear) and dequeue (remove element from the front). Queues can be implemented using arrays or linked lists; with a linked list maintaining both head and tail pointers, enqueue and dequeue are O(1).

Circular queue A fixed-size array-based queue suffers from wasted space when front moves forward; a circular queue solves this by treating the array as circular and using modulo arithmetic for indices. Maintain front and rear indices and optionally a count of elements. Enqueue places element at rear and increments rear = (rear + 1) % capacity; dequeue removes element from front and updates front likewise. Correct empty/full checks and management of size are important to avoid confusion between full and empty states.

Double-ended queue (Deque) A deque (double-ended queue) supports insertion and deletion at both ends. It generalises stacks and queues and is useful for problems where both ends need efficient access, such as sliding-window algorithms and some scheduling problems. Deques can be implemented using circular arrays or doubly linked lists.

Priority queues Unlike ordinary queues, priority queues remove the element with the highest (or lowest) priority, not necessarily the earliest inserted. They are commonly implemented using heaps (binary heaps, binomial heaps, Fibonacci heaps). Binary heaps give O(log n) time for insertion and extract-max/extract-min; a priority queue is essential to algorithms like Dijkstra's and event-driven simulation.

Applications Queues model real-world waiting lines, CPU scheduling (ready queue), IO buffering and level-order traversal of trees (BFS uses a queue). Circular buffers are used in streaming or producer-consumer problems. Priority queues are used for scheduling by priority, shortest-path algorithms and any situation requiring efficient retrieval of the highest-priority item.

Edge cases and complexities For array-based queues of capacity m, operations are O(1) but the array can overflow if not resized. For priority queues implemented with heaps, insert and extract are O(log n). Dealing with underflow (dequeue on empty) and overflow (enqueue on full fixed array) are essential in robust implementations.

What is a tree? A tree is a hierarchical, non-linear data structure composed of nodes connected by edges. One node is designated the root; every other node has exactly one parent and zero or more children. Trees model hierarchical relationships such as file directories, organisation charts, and parsed expressions. Key concepts include root, parent, child, sibling, leaf (node with no children), depth (distance from root) and height (longest path to a leaf).

Binary trees and variants A binary tree restricts each node to at most two children commonly named left and right. Special binary tree shapes include full trees (each node has 0 or 2 children), perfect trees (all levels completely filled), and complete trees (all levels filled except possibly the last which is filled from left). Complete binary trees are convenient for array representation, while pointer-based binary trees are more flexible for dynamic operations.

Binary tree operations Common operations include insertion (often at specific positions depending on the tree type), deletion, searching and traversal. Traversal means systematic visiting of all nodes. Binary trees support several traversal orders with different uses and properties.

Depth-first traversals Preorder (root, left, right) is useful to copy a tree or produce prefix notation for expressions; inorder (left, root, right) gives symmetric order and for a binary search tree yields sorted keys; postorder (left, right, root) is useful when deleting or freeing nodes or producing postfix notation. These traversals are naturally implemented by recursion; iterative implementations use an explicit stack to avoid recursion depth limits.

Breadth-first (level-order) traversal Level-order visits nodes level by level from the root, using a queue to track the next nodes to visit. Level-order is practical for finding shortest path in trees, printing tree by levels, or when operations depend on tree height.

Implementation considerations Recursive code is concise but consumes stack space proportional to tree height. For tall trees, iterative methods that use explicit stacks or queues are safer. When storing a complete binary tree in an array, children indices of node at i are left = 2i + 1 and right = 2i + 2 (0-based), which simplifies many algorithms like heap operations.

Applications Trees are central to many data structures and algorithms: binary search trees for ordered data, expression trees for compilers, file-system directory trees, and specialised trees like tries, AVL and B-trees for efficient lookup and indexing. Mastering tree terminology and traversals is essential for understanding these applications.

Definition and ordering property A binary search tree (BST) is a binary tree where every node satisfies the BST property: all keys in the left subtree are less than the node's key and all keys in the right subtree are greater (or follow a consistent <=/>= rule if duplicates are allowed). This ordering enables efficient searching, insertion and deletion by eliminating half the tree at each comparison in a well-balanced tree.

Search operation Searching for a key k starts at the root: compare k with node's key; if equal return success; if k is smaller follow the left child; if larger follow the right child. Repeat until found or a null child means not present. For a balanced BST average search time is O(log n); for a degenerate (skewed) BST it degrades to O(n).

Insertion To insert a key, search downwards to find the null child where the key should be placed and insert a new leaf there. No rebalancing occurs in a basic BST, so insertion order affects tree shape. Inserting sorted keys produces a chain (worst-case height n).

Deletion Deleting a node has three main cases: (1) node is a leaf — remove it directly; (2) node has one child — replace the node with its child; (3) node has two children — replace the node's key with its inorder successor (smallest key in right subtree) or predecessor and then delete that successor/predecessor node, which will fall into case (1) or (2). Correct pointer updates are essential to maintain structure.

Traversals and sorted output An inorder traversal of BST produces keys in sorted order, which is an important property used in sorting and in-order operations. Preorder and postorder remain useful for tree copying and destruction.

Performance and balancing Basic BST operations are O(h) where h is tree height. Balanced BST variants (AVL, Red-Black) maintain h = O(log n) and guarantee logarithmic worst-case times. When datasets are dynamic with arbitrary insertion orders, prefer self-balancing trees to avoid poor worst-case times. For fast average-case lookups without ordering guarantees, hash tables may be faster.

Applications BSTs support ordered sets, maps, symbol tables, and are foundational to many algorithms. Understanding insertion, deletion cases, and traversal properties is crucial for correctness and performance in implementations.

Heap concept and heap property A heap is a specialised tree-based structure used to implement priority queues. In a max-heap every parent node's key is greater than or equal to its children's keys; in a min-heap every parent key is less than or equal to its children's keys. Heaps are typically complete binary trees: all levels are fully filled except possibly the last, which is filled from left to right. The completeness allows compact array representation.

Array representation and index arithmetic Because heaps are complete, they map neatly to arrays. For a node at index i (0-based), its left child is at 2i + 1 and right child at 2i + 2; parent is at floor((i - 1)/2). This arithmetic avoids explicit pointers and is cache-friendly, making heaps efficient in practice.

Heap operations Insertion places the new key at the end of array and performs sift-up (up-heap) comparing with parent and swapping as needed until heap property is restored; this is O(log n) time. Extract-max (or extract-min) removes the root, replaces it with the last element, and performs sift-down (down-heap) swapping with the larger (or smaller) child until the heap property holds; this is O(log n). Building a heap from an unsorted array can be done by repeated insertions (O(n log n)) or by bottom-up heapify in O(n) time using downward sifts starting from the last non-leaf node.

Heaps as priority queues A heap efficiently implements a priority queue where insert and extract operations run in O(log n). For algorithms such as Dijkstra's shortest-path or event simulation, heaps are the usual choice for managing the frontier of candidate vertices or events. However, direct search for an arbitrary key in a heap is O(n), so heaps are not suitable when fast arbitrary-key search is required.

HeapSort HeapSort sorts an array by building a heap and repeatedly extracting the root into the end of the array; in-place HeapSort runs in O(n log n) time and uses O(1) extra space. HeapSort is not stable and has less predictable memory access patterns than merge sort, but is useful when constant extra space is required.

Variants and trade-offs More advanced heap variants (Fibonacci heaps) support faster decrease-key operations amortised, which benefits graph algorithms, but are more complex to implement. Choose binary heaps for simplicity and good practical performance in most cases.

Motivation and idea Hashing is a technique to store and retrieve key-value pairs quickly by mapping keys to indices in an array (hash table) through a hash function. The aim is to achieve average-case constant-time operations for insert, search and delete. Hash tables are widely used for dictionaries, symbol tables, caches and sets.

Hash function design A hash function converts a key to an integer hash code and then maps that code to a table index, commonly by taking modulo table_size. A good hash function distributes keys uniformly across slots to minimise collisions. For integer keys simple arithmetic may suffice; for strings polynomial rolling or more sophisticated mixing functions are used. Choosing table size (often a prime) and hash function together improves distribution.

Collisions and resolution strategies A collision occurs when two keys map to the same index. Two main approaches resolve collisions: chaining and open addressing. In chaining, each table slot holds a linked list (or dynamic container) of elements hashing to that slot; insertion adds to the chain. Searching traverses the chain to find a key. In open addressing elements are stored directly in table slots; on collision a probing sequence (linear probing, quadratic probing, or double hashing) finds the next free slot. Open addressing requires careful handling of deletions using special markers to preserve probe sequences.

Load factor and resizing The load factor α = n/m (n elements, m slots) measures table occupancy. For chaining expected search time is O(1 + α); for open addressing performance degrades as α approaches 1 and clustering may occur. To maintain performance, hash tables are resized (rehashing) when α exceeds a threshold: allocate a larger table and reinsert existing keys using the hash function for the new size.

Practical issues and performance Average-case operations in well-designed hash tables are O(1), but worst-case (many collisions) can be O(n). For predictable worst-case times, balanced search trees are preferable. Hash tables do not preserve order of keys; if ordered iteration is required, choose tree-based maps or maintain auxiliary order structures.

Applications Hash tables implement fast lookups in compilers (symbol tables), databases (indexes), web caches and language runtime structures. Understanding hash function choice, collision handling and resizing policies is key to building robust table implementations.

Graph basics A graph is a set of vertices (nodes) connected by edges. Graphs may be directed (edges have direction) or undirected; edges can carry weights. Graphs model many real-world systems such as road maps, computer networks and social networks. Fundamental tasks include traversal, connectivity checking, shortest paths and spanning trees.

Representing graphs Two common representations are adjacency matrix and adjacency list. An adjacency matrix is an n×n matrix A where A[i][j] indicates presence (and possibly weight) of edge from i to j. It uses O(n^2) space and supports O(1) edge existence checks. An adjacency list stores for each vertex a list of neighbours and requires O(n + e) space for e edges, making it efficient for sparse graphs.

Breadth-First Search (BFS) BFS explores vertices level by level from a source vertex using a queue. It discovers shortest paths in unweighted graphs and computes distances (in number of edges) from the source to each reachable vertex. BFS runs in O(n + e) time using adjacency lists and is useful for connectivity, shortest unweighted path and bipartiteness checking.

Depth-First Search (DFS) DFS explores as far as possible along each branch before backtracking, implemented by recursion or a stack. DFS also runs in O(n + e) and is used for topological sorting of DAGs, cycle detection, and finding connected components. DFS discovery and finish times help reason about edge types and graph structure.

Shortest-path algorithms For weighted graphs with non-negative weights, Dijkstra's algorithm finds shortest paths from a source using a priority queue to pick the nearest unvisited vertex and relaxing adjacent edges; complexity with binary heap is O((n + e) log n). For graphs with arbitrary weights, Bellman-Ford handles negative weights (but no negative cycles) at O(n e) time. For all-pairs shortest paths, Floyd-Warshall is a dynamic programming approach with O(n^3) time.

Minimum spanning tree (MST) An MST connects all vertices with minimum total edge weight. Kruskal's algorithm sorts edges and uses a disjoint-set (union-find) structure to add edges that connect different components, O(e log e) time. Prim's algorithm grows the tree from a source using a priority queue, similar to Dijkstra.

Choosing representation and algorithm For dense graphs adjacency matrix is acceptable; for sparse graphs adjacency lists save space and time. Algorithm choice depends on edge weights, directed vs undirected, and required output (single-source vs all-pairs). Mastery of BFS/DFS and basic weighted algorithms is essential for many advanced problems in networks and optimization.

Linear search Linear (sequential) search checks each element in a list one by one until the target is found or the list ends. It works on unsorted collections and is simple to implement. The worst-case and average-case time complexity is O(n) because the element may be absent or at the end. For small or unsorted datasets, linear search is often acceptable.

Binary search Binary search is designed for sorted arrays. It repeatedly compares the target value to the middle element of the current search interval and halves the interval based on comparison results. Because the range halves each step, binary search takes O(log n) time. Binary search requires random access (e.g., arrays) and sorted order; it is not efficient on linked lists because finding the middle element takes O(n).

Implementational details Binary search can be implemented iteratively or recursively. Care is needed with index arithmetic to avoid overflow in fixed-width integer types; use mid = low + (high - low) / 2. For duplicate keys, binary search variants find first or last occurrence by adjusting the search boundaries when a match is found.

When to use which Use linear search for small arrays or unsorted data where sorting would be more expensive than repeated linear searches. Use binary search when the array is sorted and many searches are required; maintaining sorted order with frequent insertions may be costly, so consider balanced BSTs or other structures if updates are frequent. For associative lookups without ordering, hash tables provide average-case O(1) lookup.

Limitations and edge cases Binary search assumes random access; on linked lists its advantage disappears. For floating-point comparisons, incorporate tolerance due to precision errors. When using binary search to find insertion positions, design the loop boundaries carefully to return correct index for insertion.

Practical value Understanding these search algorithms helps in algorithm selection and understanding the trade-offs between preprocessing (sorting) and query time. Binary search is foundational and appears as a subroutine in many algorithmic solutions beyond simple lookups.

Purpose of sorting Sorting arranges elements in order (ascending or descending). Sorted data simplifies searching, enables binary search and improves performance of other algorithms. This topic covers simple methods useful for learning (selection, insertion, bubble) and efficient divide-and-conquer methods (merge sort, quick sort) used in practice.

Selection sort Selection sort repeatedly finds the minimum element from the unsorted portion and swaps it into its final position. It performs O(n^2) comparisons regardless of initial order and O(n) swaps. It is in-place but not stable by default. Selection sort is easy to trace and useful for small datasets or teaching loop invariants.

Insertion sort Insertion sort builds the sorted list one element at a time by shifting larger elements to the right to make room for the next key. Its worst-case time is O(n^2) when input is reversed, but its best-case is O(n) for nearly-sorted input. Insertion sort is stable and adaptive, making it a good choice for small arrays and nearly-sorted data. It is often used as the base case for divide-and-conquer sorts.

Bubble sort Bubble sort repeatedly compares adjacent elements and swaps them if out of order. Each pass moves the largest unsorted element to its final position. Basic bubble sort is O(n^2) but an optimized version stops early when no swaps occur. Bubble sort is stable but rarely used in practice due to inefficiency.

Merge sort Merge sort is a divide-and-conquer algorithm that splits the array into halves, recursively sorts each half and merges the sorted halves. Merging two sorted lists takes linear time, and because the recurrence divides work evenly, merge sort runs in O(n log n) time in all cases. Merge sort is stable but requires O(n) additional space for merging when implemented on arrays. It is excellent for external sorting and linked lists.

Quick sort Quick sort picks a pivot, partitions elements into those less than and greater than the pivot, and recursively sorts partitions. Average-case time is O(n log n) and quick sort is typically fast in practice due to low constant factors and good cache behaviour. Worst-case time is O(n^2) with poor pivot choices (e.g., sorted input with naive pivot). Randomised pivot selection or median-of-three heuristics reduce the chance of worst-case. Quick sort can be implemented in-place and usually uses O(log n) stack space.

Choosing a sort For small arrays or nearly-sorted data, insertion sort is often best. For stable guaranteed O(n log n) behaviour, use merge sort. For typical in-memory array sorting, quick sort (with good pivot rules) is often preferable due to speed and low extra memory. Understand stability, space requirements and worst-case behaviours when selecting an algorithm.

Why analyse algorithms? Algorithm analysis estimates the resources an algorithm requires as input size grows. The main goals are to compare algorithms, predict performance on large inputs and guide selection of appropriate methods and data structures. Analysis focuses on time (number of steps) and space (extra memory), abstracting away machine-specific details.

Asymptotic notations Big-O notation provides an upper bound on growth: f(n) = O(g(n)) means for large n, f does not exceed a constant times g. Big-Omega (Ω) gives a lower bound; Theta (Θ) means tight bound when both O and Ω apply. Common complexity classes include O(1), O(log n), O(n), O(n log n), O(n^2) and exponential classes like O(2^n).

Counting operations To estimate time, count elementary operations (comparisons, assignments) as functions of input size n. For loops multiply iterations by cost per iteration. For nested loops multiply costs unless inner loop length depends on outer index. For divide-and-conquer recurrences use techniques like recursion trees or Master Theorem. For example, merge sort satisfies T(n) = 2T(n/2) + O(n), giving T(n) = O(n log n).

Best, worst and average cases Worst-case time gives an upper guarantee irrespective of input and is useful for reliable performance bounds. Best-case is the minimum resource usage and average-case is expected usage over a distribution of inputs; average-case often requires probabilistic models. For critical systems prefer worst-case bounds; for average performance consider distributions and amortised analysis for sequences of operations.

Space complexity Measures additional memory used beyond input storage. Recursive algorithms also use call stack proportional to recursion depth. In-place algorithms use O(1) extra space. Trade-offs exist between time and space: caching results can speed up computations at cost of extra memory.

Practical guidance Big-O ignores constants and lower-order terms; for small n constants matter. Use asymptotic analysis to reason about scalability: an O(n) algorithm will outperform O(n^2) for large n even if constants differ. Consider both algorithmic complexity and implementation details like cache behaviour and parallelisability for practical performance.

Why external data structures? When data sizes exceed main memory, efficient algorithms must minimise disk I/O because reading from or writing to disk is many orders of magnitude slower than memory access. External data structures are designed to reduce expensive block transfers and seeks by organising data in blocks and optimising access patterns.

Block-oriented access model Disk and external storage read and write blocks (pages) of fixed size. Algorithms thus aim to maximise useful work per block transfer. Performance measures for external algorithms count number of block transfers (I/Os) rather than CPU operations. Buffering, caching and batched I/O reduce the effective cost of disk operations.

B-Trees and B+ Trees Balanced multi-way trees such as B-Trees and B+ Trees are tailored for disks: nodes contain many keys and child pointers so each node fits a block. This high branching factor keeps tree height small, reducing the number of disk reads per search or update. B-Trees store keys and records in internal nodes; B+ Trees store records only at leaves and link leaves for efficient range queries and sequential scans. These trees are widely used in databases and file systems where large indexes must be searched and updated with few disk accesses.

Hashing on disk External hashing schemes organise buckets as disk blocks; overflow chaining or dynamic hashing techniques (extensible hashing, linear hashing) adapt the table size to growth while limiting reorganisation cost. Maintaining low load factor per block keeps I/O per operation small.

External sorting External merge sort is the standard method to sort data larger than memory. It divides data into runs that fit in memory, sorts each run in-memory, writes runs to disk, and then merges runs in multi-way passes reading blocks sequentially. Multi-way merging minimises the number of passes and I/Os by using available memory as buffers.

Design principles Minimise random disk seeks, favour sequential reads/writes, use block-sized nodes/records, maintain small tree height, and tune buffer sizes to match hardware. Many real systems combine in-memory caching with external structures for high throughput. Understanding these external structures is essential for database design, large-scale search engines and any application managing huge datasets.

Need for balancing Ordinary binary search trees can become skewed depending on insertion order, leading to O(n) operations. Self-balancing trees maintain height O(log n) by performing rotations or structural adjustments during insertions and deletions. Balanced trees combine ordering with guaranteed performance.

AVL trees An AVL tree maintains a balance factor at each node equal to height(left subtree) − height(right subtree), which must be -1, 0 or +1. Insertions or deletions may violate this property; restoring balance requires single or double rotations (left, right, left-right, right-left) around unbalanced nodes. AVL trees are strictly balanced, providing fast lookups with worst-case O(log n) time, but may perform more rotations than other balanced trees during updates.

Red-Black trees Red-Black trees store a colour bit (red or black) at each node and enforce properties that guarantee the longest path is at most twice the shortest, keeping height O(log n). Insertions and deletions involve recolouring and possible rotations. Red-Black trees are less rigid than AVL trees, typically requiring fewer rotations in practice and are used in many standard library implementations of ordered maps and sets.

Tries (prefix trees) Tries are tree structures for storing strings where each edge corresponds to a character and keys are represented by paths from the root to terminal nodes. Lookup time is proportional to the length of the key (O(m)) independent of the number of keys. Tries excel at prefix searches, autocomplete, spell checking and IP routing tables. Raw tries can consume large memory; compressed tries (radix trees) and suffix trees reduce space usage.

Trade-offs and applications AVL trees provide stricter balance and faster lookups; Red-Black trees offer good average update performance with simpler amortised costs; tries offer very fast string operations but can use more memory. Choice depends on required operations: ordered associative maps favour AVL or Red-Black, while prefix-based string tasks favour tries.