1-2 brother trees 1-2 neighbour trees 1-2 son trees 1-2 trees 2-3 brother trees 2-3 trees 2-3-4 trees \%-2 \% rule accesses accessing books addition addition chain address region address-calculation sort addressing methods album algorithm definition algorithm descriptions algorithm format algorithms code alignment problem alphabet size alternating selection alternation amortized worst case approximate matrix multiplication approximate string matching arbitrary precision approximating arctan(x) arithmetic algorithms arithmetic-geometric mean array indices array merging array of digits array Search array sorting ASCII asymptotic expansions asymptotic expansions of sums \sub containing ${\prm e}^{-x^{ }}$ asymptotic expansions of definite integrals containing ${\prm e}^{-x^{ }}$ asymptotic matrix multiplication asymptotic notation atomic operations automaton simulation average minimum accesses AVL trees B*-trees B+-trees $B_{k}$ tree $BB( \alpha )$ trees B-Tree insertion B-tree variations B-trees balance of a node balanced binary trees balanced merge sort balanced multiway trees balanced nodes balanced Quicksort balanced trees balancing by internal path reduction balancing rules basic algorithms basic concepts basic operations basic operations multiplication/division basic sequential search basic sorting methods bibliographic databases biharmonic numbers binary addition binary decisions binary trees used as priority queues binary trie binomial queues bipartition search bisection search bit indexing bit inspections bit-map display blocking factor BNF productions boolean expressions order bottom-up construction bottom-up radix sort bounded balance trees bounded disorder Boyer--Moore text searching Bradford's law break Brent's algorithm Brent's hashing Brent--Salamin browsing text brute force search brute force text searching bubble sort bucket bucket address bucket binary tries bucket sort bucket tries buckets building procedures business applications C calculated entry search cascade merge sort cellar hashing centred search chain chaining hashing circular paths classical matrix multiplication clustering clustering free coalesced hashing coalesced hashing with cellar coalescing chains cocktail shaker sort collision collision resolution scheme commutativity products complete binary trees complex arithmetic complexity measures complexity of multiplication complexity of squaring composite keys composition composition of Quicksort compressed files compressed tries computed entry search computing $\pi $ computing inverses complexity computing logarithms conformation constraints for data objects constructor contamination contamination hashing continuous growth control dictionary control function conventional data structures corpora counter heuristics cyclic structures d-prefix D-trees DASG data processing data processing sorting data structure description data processing distribution database searching DAWG decimal operations decreasing probability order deletions in binary trees deletions hashing depth nodes depth trie derivatives descending factorials determinants deterministic finite automaton {\it see} DFA DFA dichotomic search dictionaries sub external dictionary structures digit digital B-trees digital cardinality digital decomposition digital indexing digital search trees digital tree digital trie digitization digits diminishing increment sort direct chaining hashing directed acyclic subsequence graph {\it see} DASG directed acyclic word graph {\it see} DAWG directory sub hashing discrete rectangular distribution disk cylinder disk track dispersion phase distribution of authorship distribution phase distribution probability distributions derived from empirical observation distributions sort distributive partitioning divide and conquer division sub finite fields double-direction bubblesort double hashing double left rotation double right rotation double rotation double-ended double-ended priority queues doubly exponential forms dummy sequences dynamic hashing dynamic programming dynamic set sorting dynamic size hashing Dynamic trees editing cost empirical distributions end-of-string {\it see} EOS English entropy searching EOS equations systems of error conditions estimated entry search Euler's constant Euler--Maclaurin summation formula exchange with parent expansions asymptotic expectation expected value exponent exponential function exponential integral exponential-type expansions extended precision extendible hashing external accesses external hashing sub using minimal internal storage external merge sorting external merging external path external Quicksort external searching external sorting extract maximum factorial function failure function false drops fast Fourier transform fast multiplication Fibonacci numbers finite state machine finite universe of keys first generalization of a Zipfian distribution first-come-first-served FCFS Floyd's heap-construction folklore distributions for loops forest format of simulation results format of tables found frequency of references frequency of words fringe reorganization full expansion full stability gamma function gamma-type expansions general trees generalized harmonic generating function go to table goto grammar for data objects graphics greedy trees growth at root B-trees growth continuous Hamming distance harmonic numbers hashed increments hashing hashing algorithms hashing function hashing methods for text searching hashing table hashing tries hashing value hashing memoryless HB[k] trees header heap Heapsort height balance height balancing height increase transformation height trees height-balanced trees heuristic organization schemes on binary trees heuristics sub for known probabilities hierarchical balance hierarchical order homogeneous indexing horizontal pointers Horner's rule Hu--Tucker algorithm Huffman encoding Hwang and Lin merging hybrid algorithm hybrid methods of sorting hybrid Quicksort hybrid sorting hybrid tries hyperrules implementation of lists implementation of trees implementing lists in arrays implicit data structures in place sorting in-place merging increment sequences index and indexed sequential files index B-trees index file index point index sequential access method {\it see ISAM} indexed file indices infix traversal input structure insert in decreasing probability order insertion order insertion sort inspect queue interchangeability interleaving internal path internal/external differences interpolation interpolation formula interpolation search interpolation sort interpolation--sequential search introduction inverse of a function inverse square distribution inverse trigonometric functions inversion inverted file inverted search ISAM iterative application iterative formula iterative powering iterative zero-finder jump search {\pit k}-balancing k-clustering k-d tree k-dimensional trees {\pit k}-height balanced k-prefix Karp--Rabin text searching KMP algorithm known probabilities heuristics Knuth--Morris--Pratt text searching language dictionaries last-come-first-served hashing LCFS hashing LCS leaf-pages left single rotation leftist trees Legendre's identity length sub of longest probe sequence Levenshtein distance lexicographical order lexicographical trees linear combinations linear hashing linear insertion sort linear lists linear probing linear probing hashing linear probing sort linear search linked list sub search list merging lists sub search load factor logarithms longest common subsequence {\it see} LCS longest probe sequence Lotka's distribution Lotka's law lower bounds selection lower-upper triangular factoring $m$-ary search trees main file matrix determinant matrix inversion matrix multiplication matrix partitioning maximum search maximum-minimum search mean-centred search median median selection median split median split trees memoryless merge merge sort mergeable priority queues merging merging pass merging phase meta-production minave minimal perfect hashing function minimal-comparison merging minimax minimum accesses minimum height trees minimum search mod mode of a set mode-centred search modular arithmetic move-to-front heuristic move-to-root multidimensional search multilevel indices multiple alignment problem multiple precision multiplication multiple-precision multiplication multiplicity multiway decisions multiway merging multiway trees naming of variables natural merge natural merge sort natural selection nearest neighbour search negative search Newton's iteration node inspections node splittings non-atomic keys non-recursive bucket sort normalization notfound number number of binary trees numbering systems on-line algorithm one-sided height balanced open-addressing optimal binary tree search optimal external hashing optimal hashing optimal merging optimal polynomial evaluation optimal polyphase merge optimal powering optimal sequential search optimality order relation ordered arrays ordered binary tree ordered hashing ordering rules organization organization of handbook oscillating merge sort OSHB trees other arithmetic functions other text searching problems output function overflow overflow area overflow records overflow techniques P-strings P-trees pagodas parameters parsed strings partial-match searching partially sorted partition methods partitioning matrices Pascal pass \PAT \PAT tree path path trees path-balanced trees Patricia tree pattern matching pattern matching machine perfect binary trees perfect distribution perfect hashing perfectly balanced k-d trees permanents physical record planar coordinates Poisson distribution polynomial evaluation polynomial roots polyphase merge sort population of cities positive search postfix traversals powering a number practical hashing functions practical recommendations preconditioning prefix B-trees prefix search prefix traversals preprocessing text presortedness primality testing primary clustering primary key access primary key search prime table size priority queue priority queue order priority trees probabilistic algorithms probabilities probability distribution probability notation probability universe product commutativity product matrices programming languages prolix author proximity searching pseudo-random probing psi function punched cards quad trees quad tries quadratic convergence quadratic hashing Quickersort Quicksort Quicksort for lists radix sort random binary trees random heaps random probing random probing hashing random search trees random string random variables randomization randomly generated binary trees range search ranking read backwards real timings recommendations recursion recursion termination recursive matrix multiplication recursive structures search red-black trees rehashing reordering of arrays reorganization schemes reorganization repeated selection repetition replacement replacement selection replacement selection reservoir resulting structure return Riemann zeta function right single rotation Robin Hood hashing roots of polynomials rotations sub in binary trees runs Samplesort sampling SBB trees scatter storage searching algorithms searching buckets with overflow searching longest common subsequences searching preprocessed text searching sets of strings searching text with automata secant method second generalization of a Zipfian distribution secondary clustering secondary key search selection Algorithms selection by sampling selection by sorting selection by tail recursion selection of $k$th element selection of the mode selection phase techniques selection sorting selector self-adjusting hashing self-organization self-organizing heuristics self-organizing search self-organizing sequential search sub move-to-front method sub transpose method semantic rules semi-infinite spiral semi-infinite string sentinel sentinel sorting separate chaining hashing separator sequence of reals sequence of scalars sequences sequential lists sequential order sequential processing sequential search series asymptotic shape heuristics shape parameter shared structures Shellsort shift-or text searching shortest common supersequence siftup sign signature signature encoding signature file simple exchange simulation results format single rotation sispiral sistring Smoothsort solution of simultaneous equations sorted array search sorted list sorted/unsorted lists sorting Algorithms sorting arrays sorting by distribution sorting other data structures splay trees splaying split transformation split-sequence hashing splitting elements Quicksort square matrices squaring complexity stable merging stable priority queues stable sorting stable tables standard matrix multiplication static object definition static tables static tree stop words storage utilization Strassen's matrix multiplication string matching with errors string matching with mismatches string searching string similarity searching strings subtraction suffix arrays suffix arrays and \PAT arrays summary of direct text searching summation constant summation formulas summations sums containing descending factorials superimposed coding superimposition symmetric binary B-trees {\it see} SBB trees synonyms syntactic rules systems of equations tables format tail of distribution tail recursion tape searching techniques for sorting arrays test for equality testing algorithms text algorithms text editing text searching sub without preprocessing text-dominated databases third-order iteration threaded binary tree timings real top-down construction top-down radix sort tournament transcendental functions transition table transpose heuristic transpose heuristic trees tree searching tree traversals trees used for text searching Treesort tries tries for word-dictionaries trigonometric functions trilinear forms truncated Zipfian distribution two-dimensional search two-dimensional two-level grammar unary node uncertainty searching uniform probing hashing uniqueness universal class of hashing functions unsorted list unwinding recursion upper bounds selection Van Emde-Boas priority queues van Wijngaarden grammar var variable length keys variable names variable-length array implementations variable-length keys variable-length signatures variance vertical pointers virtual hashing $w(x)$ function W-grammar weight balance weight-balanced trees Williams' insertion algorithm Winograd matrix multiplication with word dictionaries word number worst-case behaviour worst-case minimum accesses zero-finder zeta function Zipf's law Zipfian distribution