List of terms relating to algorithms and data structures explained

The NIST Dictionary of Algorithms and Data Structures^[1] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data structures. For algorithms and data structures not necessarily mentioned here, see list of algorithms and list of data structures.

This list of terms was originally derived from the index of that document, and is in the public domain, as it was compiled by a Federal Government employee as part of a Federal Government work. Some of the terms defined are:

A

absolute performance guarantee
abstract data type (ADT)
abstract syntax tree (AST)
(a,b)-tree
accepting state
Ackermann's function
active data structure
acyclic directed graph
adaptive heap sort
adaptive Huffman coding
adaptive k-d tree
adaptive sort
address-calculation sort
adjacency list representation
adjacency matrix representation
adversary
algorithm
algorithm BSTW
algorithm FGK
algorithmic efficiency
algorithmically solvable
algorithm V
all pairs shortest path
alphabet
Alpha Skip Search algorithm
alternating path
alternating Turing machine
alternation
American flag sort
amortized cost
ancestor
and
and-or tree
American National Standards Institute (ANSI)
antichain
antisymmetric relation
AP
Apostolico–Crochemore
Apostolico–Giancarlo algorithm
approximate string matching
approximation algorithm
arborescence
arithmetic coding
array
array index
array merging
array search
articulation point
A* search algorithm
assignment problem
association list
associative
associative array
asymptotically tight bound
asymptotic bound
asymptotic lower bound
asymptotic space complexity
asymptotic time complexity
asymptotic upper bound
augmenting path
automaton
average case
average-case cost
AVL tree
axiomatic semantics

B

backtracking
bag
Baillie–PSW primality test
balanced binary search tree
balanced binary tree
balanced k-way merge sort
balanced merge sort
balanced multiway merge
balanced multiway tree
balanced quicksort
balanced tree
balanced two-way merge sort
BANG file
Batcher sort
Baum Welch algorithm
BB α tree
BDD
BD-tree
Bellman–Ford algorithm
Benford's law
best case
best-case cost
best-first search
biconnected component
biconnected graph
bidirectional bubble sort
big-O notation
binary function
binary fuse filter
binary GCD algorithm
binary heap
binary insertion sort
binary knapsack problem
binary priority queue
binary relation
binary search
binary search tree
binary tree
binary tree representation of trees
bingo sort
binomial heap
binomial tree
bin packing problem
bin sort
bintree
bipartite graph
bipartite matching
bisector
bitonic sort
bit vector
Bk tree
bdk tree (not to be confused with k-d-B-tree)^[2]
block
block addressing index
blocking flow
block search
Bloom filter
blossom (graph theory)
bogosort
boogol
Boolean
Boolean expression
Boolean function
bottleneck traveling salesman
bottom-up tree automaton
boundary-based representation
bounded error probability in polynomial time
bounded queue
bounded stack
Bounding volume hierarchy, also referred to as bounding volume tree (BV-tree, BVT)
Boyer–Moore string-search algorithm
Boyer–Moore–Horspool algorithm
bozo sort
B+ tree
BPP (complexity)
Bradford's law
branch (as in control flow)
branch (as in revision control)
branch and bound
breadth-first search
Bresenham's line algorithm
brick sort
bridge
British Museum algorithm
brute-force attack
brute-force search
brute-force string search
brute-force string search with mismatches
BSP-tree
B*-tree
B-tree
bubble sort
bucket
bucket array
bucketing method
bucket sort
bucket trie
buddy system
buddy tree
build-heap
Burrows–Wheeler transform (BWT)
busy beaver
Byzantine generals

C

cactus stack
Calculus of Communicating Systems (CCS)
calendar queue
candidate consistency testing
candidate verification
canonical complexity class
capacitated facility location
capacity
capacity constraint
Cartesian tree
cascade merge sort
caverphone
Cayley–Purser algorithm
C curve
cell probe model
cell tree
cellular automaton
centroid
certificate
chain (order theory)
chaining (algorithm)
child
Chinese postman problem
Chinese remainder theorem
Christofides algorithm
Christofides heuristic
chromatic index
chromatic number
Church–Turing thesis
circuit
circuit complexity
circuit value problem
circular list
circular queue
clique
clique problem
clustering (see hash table)
clustering free
coalesced hashing
coarsening
cocktail shaker sort
codeword
coding tree
collective recursion
collision
collision resolution scheme
Colussi
combination
comb sort
Communicating Sequential Processes
commutative
compact DAWG
compact trie
comparison sort
competitive analysis
competitive ratio
complement
complete binary tree
complete graph
completely connected graph
complete tree
complexity
complexity class
computable
concave function
concurrent flow
concurrent read, concurrent write
concurrent read, exclusive write
configuration
confluently persistent data structure
conjunction
connected components
connected graph
co-NP
constant function
continuous knapsack problem
Cook reduction
Cook's theorem
counting sort
covering
CRCW
Crew (algorithm)
critical path problem
CSP (communicating sequential processes)
CSP (constraint satisfaction problem)
CTL
cuckoo hashing
cuckoo filter
cut (graph theory)
cut (logic programming)
cutting plane
cutting stock problem
cutting theorem
cut vertex
cycle sort
cyclic redundancy check (CRC)

D

D-adjacent
DAG shortest paths
Damerau–Levenshtein distance
data structure
decidable
decidable language
decimation
decision problem
decision tree
decomposable searching problem
degree
dense graph
depoissonization
depth
depth-first search (DFS)
deque
derangement
descendant (see tree structure)
deterministic
deterministic algorithm
deterministic finite automata string search
deterministic finite automaton (DFA)
deterministic finite state machine
deterministic finite tree automaton
deterministic pushdown automaton (DPDA)
deterministic tree automaton
Deutsch–Jozsa algorithm
DFS forest
DFTA
diagonalization argument
diameter
dichotomic search
dictionary (data structure)
diet (see discrete interval encoding tree below)
difference (set theory)
digital search tree
digital tree
digraph
Dijkstra's algorithm
diminishing increment sort
dining philosophers
direct chaining hashing
directed acyclic graph (DAG)
directed acyclic word graph (DAWG)
directed graph
discrete interval encoding tree
discrete p-center
disjoint set
disjunction
distributed algorithm
distributional complexity
distribution sort
divide-and-conquer algorithm
divide and marriage before conquest
division method
data domain
don't-care term
Doomsday rule
double-direction bubble sort
double-ended priority queue
double hashing
double left rotation
Double Metaphone
double right rotation
double-ended queue
doubly linked list
dragon curve
dual graph
dual linear program
dyadic tree
dynamic array
dynamic data structure
dynamic hashing
dynamic programming
dynamization transformation

E

edge
eb tree (elastic binary tree)
edge coloring
edge connectivity
edge crossing
edge-weighted graph
edit distance
edit operation
edit script
8 queens
elastic-bucket trie
element uniqueness
end-of-string
epidemic algorithm
Euclidean algorithm
Euclidean distance
Euclidean Steiner tree
Euclidean traveling salesman problem
Euclid's algorithm
Euler cycle
Eulerian graph
Eulerian path
exact string matching
EXCELL (extendible cell)
exchange sort
exclusive or
exclusive read, concurrent write (ERCW)
exclusive read, exclusive write (EREW)
exhaustive search
existential state
expandable hashing
expander graph
exponential
extended binary tree
extended Euclidean algorithm
extended k-d tree
extendible hashing
external index
external memory algorithm
external memory data structure
external merge
external merge sort
external node
external quicksort
external radix sort
external sort
extrapolation search
extremal
extreme point

F

facility location
factor (see substring)
factorial
fast Fourier transform (FFT)
fathoming
feasible region
feasible solution
feedback edge set
feedback vertex set
Ferguson–Forcade algorithm
Fibonacci number
Fibonacci search
Fibonacci tree
Fibonacci heap
Find
find kth least element
finitary tree
finite Fourier transform (discrete Fourier transform)
finite state automaton
finite-state machine
finite state machine minimization
finite-state transducer
first come, first served
first-in, first-out (FIFO)
fixed-grid method
flash sort
flow
flow conservation
flow function
flow network
Floyd–Warshall algorithm
Ford–Bellman algorithm
Ford–Fulkerson algorithm
forest
forest editing problem
formal language
formal methods
formal verification
forward index
fractal
fractional knapsack problem
fractional solution
free edge
free list
free tree
free vertex
frequency count heuristic
full array
full binary tree
full inverted index
fully dynamic graph problem
fully persistent data structure
fully polynomial approximation scheme
function (programming)
function (mathematics)
functional data structure

G

Galil–Giancarlo
Galil–Seiferas
gamma function
GBD-tree
geometric optimization problem
global optimum
gnome sort
goobi
graph
graph coloring
graph concentration
graph drawing
graph isomorphism
graph partition
Gray code
greatest common divisor (GCD)
greedy algorithm
greedy heuristic
grid drawing
grid file
Grover's algorithm

H

halting problem
Hamiltonian cycle
Hamiltonian path
Hamming distance
Harter–Highway dragon
hash function
hash heap
hash table
hash table delete
Hausdorff distance
hB-tree
head
heap
heapify
heap property
heapsort
heaviest common subsequence
height
height-balanced binary search tree
height-balanced tree
heuristic
hidden Markov model
highest common factor
Hilbert curve
histogram sort
homeomorphic
horizontal visibility map
Huffman encoding
Hungarian algorithm
hybrid algorithm
hyperedge
hypergraph

I

Identity function
ideal merge
implication
implies
implicit data structure
in-branching
inclusion–exclusion principle
inclusive or
incompressible string
incremental algorithm
in-degree
independent set (graph theory)
index file
information theoretic bound
in-place algorithm
in-order traversal
in-place sort
insertion sort
instantaneous description
integer linear program
integer multi-commodity flow
integer polyhedron
interactive proof system
interface
interior-based representation
internal node
internal sort
interpolation search
interpolation-sequential search
interpolation sort
intersection (set theory)
interval tree
intractable
introsort
introspective sort
inverse Ackermann function
inverted file index
inverted index
irreflexive
isomorphic
iteration

J

K

Karmarkar's algorithm
Karnaugh map
Karp–Rabin string-search algorithm
Karp reduction
k-ary heap
k-ary Huffman encoding
k-ary tree
k-clustering
k-coloring
k-connected graph
k-d-B-tree (not to be confused with bdk tree)^[2]
k-dimensional
K-dominant match
k-d tree
key
KMP
KmpSkip Search
knapsack problem
knight's tour
Knuth–Morris–Pratt algorithm
Königsberg bridges problem
Kolmogorov complexity
Kraft's inequality
Kripke structure
Kruskal's algorithm
kth order Fibonacci numbers
kth shortest path
kth smallest element
KV diagram
k-way merge
k-way merge sort
k-way tree

L

labeled graph
language
last-in, first-out (LIFO)
Las Vegas algorithm
lattice (group)
layered graph
LCS
leaf
least common multiple (LCM)
leftist tree
left rotation
left-child right-sibling binary tree also termed first-child next-sibling binary tree, doubly chained tree, or filial-heir chain
Lempel–Ziv–Welch (LZW)
level-order traversal
Levenshtein distance
lexicographical order
linear
linear congruential generator
linear hash
linear insertion sort
linear order
linear probing
linear probing sort
linear product
linear program
linear quadtree
linear search
link
linked list
list
list contraction
little-o notation
Lm distance
load factor (computer science)
local alignment
local optimum
logarithm, logarithmic scale
longest common subsequence
longest common substring
Lotka's law
lower bound
lower triangular matrix
lowest common ancestor
l-reduction

M

Malhotra–Kumar–Maheshwari blocking flow (ru.)
Manhattan distance
many-one reduction
Markov chain
marriage problem (see assignment problem)
Master theorem (analysis of algorithms)
matched edge
matched vertex
matching (graph theory)
matrix
matrix-chain multiplication problem
max-heap property
maximal independent set
maximally connected component
Maximal Shift
maximum bipartite matching
maximum-flow problem
MAX-SNP
Mealy machine
mean
median
meld (data structures)
memoization
merge algorithm
merge sort
Merkle tree
meromorphic function
metaheuristic
metaphone
midrange
Miller–Rabin primality test
min-heap property
minimal perfect hashing
minimum bounding box (MBB)
minimum cut
minimum path cover
minimum spanning tree
minimum vertex cut
mixed integer linear program
mode
model checking
model of computation
moderately exponential
MODIFIND
monotone priority queue
monotonically decreasing
monotonically increasing
Monte Carlo algorithm
Moore machine
Morris–Pratt
move (finite-state machine transition)
move-to-front heuristic
move-to-root heuristic
multi-commodity flow
multigraph
multilayer grid file
multiplication method
multiprefix
multiprocessor model
multiset
multi suffix tree
multiway decision
multiway merge
multiway search tree
multiway tree
Munkres' assignment algorithm

N

naive string search
NAND
n-ary function
NC
NC many-one reducibility
nearest neighbor search
negation
network flow (see flow network)
network flow problem
next state
NIST
node
nonbalanced merge
nonbalanced merge sort
nondeterministic
nondeterministic algorithm
nondeterministic finite automaton
nondeterministic finite-state machine (NFA)
nondeterministic finite tree automaton (NFTA)
nondeterministic polynomial time
nondeterministic tree automaton
nondeterministic Turing machine
nonterminal node
nor
not
Not So Naive
NP
NP-complete
NP-complete language
NP-hard
n queens
nullary function
null tree
New York State Identification and Intelligence System (NYSIIS)

O

objective function
occurrence
octree
odd–even sort
offline algorithm
offset (computer science)
omega
omicron
one-based indexing
one-dimensional
online algorithm
open addressing
optimal
optimal cost
optimal hashing
optimal merge
optimal mismatch
optimal polygon triangulation problem
optimal polyphase merge
optimal polyphase merge sort
optimal solution
optimal triangulation problem
optimal value
optimization problem
or
oracle set
oracle tape
oracle Turing machine
orders of approximation
ordered array
ordered binary decision diagram (OBDD)
ordered linked list
ordered tree
order preserving hash
order preserving minimal perfect hashing
oriented acyclic graph
oriented graph
oriented tree
orthogonal drawing
orthogonal lists
orthogonally convex rectilinear polygon
oscillating merge sort
out-branching
out-degree
overlapping subproblems

P

packing (see set packing)
padding argument
pagoda
pairing heap
PAM (point access method)
parallel computation thesis
parallel prefix computation
parallel random-access machine (PRAM)
parametric searching
parent
partial function
partially decidable problem
partially dynamic graph problem
partially ordered set
partially persistent data structure
partial order
partial recursive function
partition (set theory)
passive data structure
patience sorting
path (graph theory)
path cover
path system problem
Patricia tree
pattern
pattern element
P-complete
PCP theorem
Peano curve
Pearson's hashing
perfect binary tree
perfect hashing
perfect k-ary tree
perfect matching
perfect shuffle
performance guarantee
performance ratio
permutation
persistent data structure
phonetic coding
pile (data structure)
pipelined divide and conquer
planar graph
planarization
planar straight-line graph
PLOP-hashing
point access method
pointer jumping
pointer machine
poissonization
polychotomy
polyhedron
polylogarithmic
polynomial
polynomial-time approximation scheme (PTAS)
polynomial hierarchy
polynomial time
polynomial-time Church–Turing thesis
polynomial-time reduction
polyphase merge
polyphase merge sort
polytope
poset
postfix traversal
Post machine (see Post–Turing machine)
postman's sort
postorder traversal
Post correspondence problem
potential function (see potential method)
predicate
prefix
prefix code
prefix computation
prefix sum
prefix traversal
preorder traversal
primary clustering
primitive recursive
Prim's algorithm
principle of optimality
priority queue
prisoner's dilemma
PRNG
probabilistic algorithm
probabilistically checkable proof
probabilistic Turing machine
probe sequence
Procedure (computer science)
process algebra
proper (see proper subset)
proper binary tree
proper coloring
proper subset
property list
prune and search
pseudorandom number generator
pth order Fibonacci numbers
P-tree
purely functional language
pushdown automaton (PDA)
pushdown transducer
p-way merge sort

Q

qm sort
qsort
quadratic probing
quadtree
quadtree complexity theorem
quad trie
quantum computation
queue
quicksort

R

Rabin–Karp string-search algorithm
radix quicksort
radix sort
ragged matrix
Raita algorithm
random-access machine
random number generation
randomization
randomized algorithm
randomized binary search tree
randomized complexity
randomized polynomial time
randomized rounding
randomized search tree
Randomized-Select
random number generator
random sampling
range (function)
range sort
Rank (graph theory)
Ratcliff/Obershelp pattern recognition
reachable
rebalance
recognizer
rectangular matrix
rectilinear
rectilinear Steiner tree
recurrence equations
recurrence relation
recursion
recursion termination
recursion tree
recursive (computer science)
recursive data structure
recursive doubling
recursive language
recursively enumerable language
recursively solvable
red–black tree
reduced basis
reduced digraph
reduced ordered binary decision diagram (ROBDD)
reduction
reflexive relation
regular decomposition
rehashing
relation (mathematics)
relational structure
relative performance guarantee
relaxation
relaxed balance
rescalable
restricted universe sort
result cache
Reverse Colussi
Reverse Factor
R-file
Rice's method
right rotation
right-threaded tree
root
root balance
rooted tree
rotate left
rotate right
rotation
rough graph
RP
R+-tree
R*-tree
R-tree
run time

S

saguaro stack
saturated edge
SBB tree
scan
scapegoat tree
search algorithm
search tree
search tree property
secant search
secondary clustering
memory segment
select algorithm
select and partition
selection problem
selection sort
select kth element
select mode
self-loop
self-organizing heuristic
self-organizing list
self-organizing sequential search
semidefinite programming
separate chaining hashing
separator theorem
sequential search
set
set cover
set packing
shadow heap
shadow merge
shadow merge insert
shaker sort
Shannon–Fano coding
shared memory
Shell sort
Shift-Or
Shor's algorithm
shortcutting
shortest common supersequence
shortest common superstring
shortest path
shortest spanning tree
shuffle
shuffle sort
sibling
Sierpiński curve
Sierpinski triangle
sieve of Eratosthenes
sift up
signature
Simon's algorithm
simple merge
simple path
simple uniform hashing
simplex communication
simulated annealing
simulation theorem
single-destination shortest-path problem
single-pair shortest-path problem
single program multiple data
single-source shortest-path problem
singly linked list
singularity analysis
sink
sinking sort
skd-tree
skew-symmetry
skip list
skip search
slope selection
Smith algorithm
Smith–Waterman algorithm
smoothsort
solvable problem
sort algorithm
sorted array
sorted list
sort in-place
sort merge
soundex
space-constructible function
spanning tree
sparse graph
sparse matrix
sparsification
sparsity
spatial access method
spectral test
splay tree
SPMD
square matrix
square root
SST (shortest spanning tree)
stable
stack (data structure)
stack tree
star-shaped polygon
start state
state
state machine
state transition
static data structure
static Huffman encoding
s-t cut
st-digraph
Steiner minimum tree
Steiner point
Steiner ratio
Steiner tree
Steiner vertex
Steinhaus–Johnson–Trotter algorithm
Stirling's approximation
Stirling's formula
stooge sort
straight-line drawing
strand sort
strictly decreasing
strictly increasing
strictly lower triangular matrix
strictly upper triangular matrix
string
string editing problem
string matching
string matching on ordered alphabets
string matching with errors
string matching with mismatches
string searching
strip packing
strongly connected component
strongly connected graph
strongly NP-hard
subadditive ergodic theorem
subgraph isomorphism
sublinear time algorithm
subsequence
subset
substring
subtree
succinct data structure
suffix
suffix array
suffix automaton
suffix tree
superimposed code
superset
supersink
supersource
symmetric relation
symmetrically linked list
symmetric binary B-tree
symmetric set difference
symmetry breaking
symmetric min max heap

T

tail
tail recursion
tango tree
target
temporal logic
terminal (see Steiner tree)
terminal node
ternary search
ternary search tree (TST)
text searching
theta
threaded binary tree
threaded tree
three-dimensional
three-way merge sort
three-way radix quicksort
time-constructible function
time/space complexity
top-down radix sort
top-down tree automaton
top-node
topological order
topological sort
topology tree
total function
totally decidable language
totally decidable problem
totally undecidable problem
total order
tour
tournament
towers of Hanoi
tractable problem
transducer
transition (see finite-state machine)
transition function (of a finite-state machine or Turing machine)
transitive relation
transitive closure
transitive reduction
transpose sequential search
travelling salesman problem (TSP)
treap
tree
tree automaton
tree contraction
tree editing problem
tree sort
tree transducer
tree traversal
triangle inequality
triconnected graph
trie
trinary function
tripartition
Turbo-BM
Turbo Reverse Factor
Turing machine
Turing reduction
Turing transducer
twin grid file
two-dimensional
two-level grid file
2–3 tree
2–3–4 tree
Two Way algorithm
two-way linked list
two-way merge sort

U

unary function
unbounded knapsack problem (UKP)
uncomputable function
uncomputable problem
undecidable language
undecidable problem
undirected graph
uniform circuit complexity
uniform circuit family
uniform hashing
uniform matrix
union
union of automata
universal hashing
universal state
universal Turing machine
universe
unsolvable problem
unsorted list
upper triangular matrix

V

van Emde Boas priority queue
vehicle routing problem
Veitch diagram
Venn diagram
vertex
vertex coloring
vertex connectivity
vertex cover
vertical visibility map
virtual hashing
visibility map
visible (geometry)
Viterbi algorithm
VP-tree
VRP (vehicle routing problem)

W

walk
weak cluster
weak-heap
weak-heap sort
weight-balanced tree
weighted, directed graph
weighted graph
window
witness
work-depth model
work-efficient
work-preserving
worst case
worst-case cost
worst-case minimum access
Wu's line algorithm

X

Y

Yule–Simon distribution

Z

Zeller's congruence
0-ary function
0-based indexing
0/1 knapsack problem
Zhu–Takaoka string matching algorithm
Zipfian distribution
Zipf's law
Zipper (data structure)
Zip tree
ZPP

Notes and References

Web site: Dictionary of Algorithms and Data Structures . Paul E . Black . . 2022-01-02 . nist.gov.
Web site: Gerleman. Nick. 2015-12-28. The Bkd Tree. 2020-10-07. Medium. en.