List of terms relating to algorithms and data structures

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)
(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
alternating Turing machine
alternation
American flag sort
amortized cost
ancestor
and
American National Standards Institute (ANSI)
antichain
antisymmetric relation
AP
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 quicksort
balanced tree
BANG file
Batcher sort
Baum Welch algorithm
BDD
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 GCD algorithm
binary heap
binary insertion sort
binary knapsack problem
binary relation
binary search
binary search tree
binary tree
bingo sort
binomial heap
binomial tree
bin packing problem
bin sort
bintree
bipartite graph
bipartite matching
bisector
bitonic sort
bit vector
Bk tree
(not to be confused with k-d-B-tree)^[2]
block
blocking flow
block search
Bloom filter
blossom (graph theory)
bogosort
boolean
boolean expression
boolean function
bottleneck traveling salesman
bottom-up tree automaton
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
BSP-tree
B*-tree
B-tree
bubble sort
bucket
bucket array
bucketing method
bucket sort
bucket trie
buddy system
Burrows–Wheeler transform (BWT)
busy beaver
Byzantine generals

C[]

cactus stack
Calculus of Communicating Systems (CCS)
calendar queue
canonical complexity class
capacitated facility location
capacity
Cartesian tree
cascade merge sort
caverphone
Cayley–Purser algorithm
C curve
cellular automaton
centroid
certificate
chain (order theory)
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)
coalesced hashing
cocktail shaker sort
codeword
coding tree
collision
collision resolution scheme
combination
comb sort
Communicating Sequential Processes
commutative
compact DAWG
comparison sort
competitive analysis
competitive ratio
complement
complete binary tree
complete graph
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
CSP (communicating sequential processes)
CSP (constraint satisfaction problem)
CTL
cuckoo hashing
cut (graph theory)
cut (logic programming)
cutting plane
cutting stock problem
cut vertex
cycle sort
cyclic redundancy check (CRC)

D[]

DAG shortest paths
Damerau–Levenshtein distance
data structure
decidable
decidable language
decimation
decision problem
decision tree
degree
dense graph
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
DFTA
diagonalization argument
diameter
dichotomic search
dictionary (data structure)
diet (see discrete interval encoding tree below)
difference (set theory)
digital tree
digraph
Dijkstra's algorithm
dining philosophers
directed acyclic graph (DAG)
directed acyclic word graph (DAWG)
directed graph
disjoint set
disjunction
distributed algorithm
distribution sort
divide-and-conquer algorithm
divide and marriage before conquest
data domain
don't-care term
Doomsday rule
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 programming
dynamization transformation

E[]

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

F[]

facility location
factor (see substring)
factorial
fast fourier transform (FFT)
feasible region
feasible solution
feedback edge set
feedback vertex set
Ferguson–Forcade algorithm
Fibonacci number
Fibonacci search
Fibonacci tree
Fibonacci heap
Find
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)
flow
flow conservation
flow function
flow network
Floyd–Warshall algorithm
Ford–Bellman algorithm
Ford–Fulkerson algorithm
forest
formal language
formal methods
formal verification
forward index
fractal
fractional knapsack problem
free list
free tree
full binary tree
full inverted index
fully persistent data structure
fully polynomial approximation scheme
function (programming)
function (mathematics)
functional data structure

G[]

gamma function
global optimum
gnome sort
goobi
graph
graph coloring
graph drawing
graph isomorphism
graph partition
Gray code
greatest common divisor (GCD)
greedy algorithm
greedy heuristic
grid file
Grover's algorithm

H[]

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

I[]

Identity function
implication
implies
inclusion–exclusion principle
inclusive or
incompressible string
in-degree
independent set (graph theory)
index file
in-place algorithm
in-order traversal
in-place sort
insertion sort
integer linear program
interactive proof system
interface
internal node
internal sort
interpolation 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 Huffman encoding
k-ary tree
k-coloring
k-connected graph
k-d-B-tree (not to be confused with )^[2]
k-dimensional
k-d tree
key
KMP
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
KV diagram
k-way merge
k-way tree

L[]

labeled graph
language
last-in, first-out (LIFO)
Las Vegas algorithm
lattice (group)
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)
Levenshtein distance
lexicographical order
linear
linear congruential generator
linear hash
linear insertion sort
linear order
linear probing
linear program
linear search
link
linked list
list
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[]

(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
max-heap property
maximal independent set
maximum bipartite matching
maximum-flow problem
MAX-SNP
Mealy machine
mean
median
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
mode
model checking
model of computation
MODIFIND
monotone priority queue
monotonically decreasing
monotonically increasing
Monte Carlo algorithm
Moore machine
move (finite-state machine transition)
move-to-front heuristic
move-to-root heuristic
multi-commodity flow
multigraph
multiset
multiway tree
Munkres' assignment algorithm

N[]

naive string search
nand
n-ary function
NC
nearest neighbor search
negation
network flow (see flow network)
network flow problem
NIST
node
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
nor
not
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 solution
optimal value
optimization problem
or
oracle set
oracle tape
oracle Turing machine
orders of approximation
ordered binary decision diagram (OBDD)
ordered tree
oriented acyclic graph
oriented graph
oriented tree
orthogonally convex rectilinear polygon
oscillating merge sort
out-degree
overlapping subproblems

P[]

packing (see set packing)
padding argument
pagoda
pairing heap
PAM (point access method)
parallel computation thesis
parallel random-access machine (PRAM)
parent
partial function
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
Patricia tree
pattern
P-complete
PCP
Peano curve
perfect binary tree
perfect hashing
perfect matching
perfect shuffle
permutation
persistent data structure
phonetic coding
pile (data structure)
planar graph
planarization
planar straight-line graph
point access method
pointer jumping
pointer machine
polychotomy
polyhedron
polylogarithmic
polynomial
polynomial-time approximation scheme (PTAS)
polynomial hierarchy
polynomial time
polynomial-time Church–Turing thesis
polynomial-time reduction
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 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
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

Q[]

qsort
quadratic probing
quadtree
quantum computation
queue
quicksort

R[]

Rabin–Karp string-search algorithm
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
random number generator
random sampling
range (function)
range sort
Rank (graph theory)
reachable
rebalance
recognizer
rectangular matrix
rectilinear
rectilinear Steiner tree
recurrence equations
recurrence relation
recursion
recursion termination
recursive (computer science)
recursive data structure
recursive doubling
recursive language
recursively enumerable language
red–black tree
reduced ordered binary decision diagram (ROBDD)
reduction
reflexive relation
rehashing
relation (mathematics)
relational structure
relative performance guarantee
relaxation
relaxed balance
result cache
Rice's method
right rotation
right-threaded tree
root
root balance
rooted tree
rotation
RP
R+-tree
R*-tree
R-tree
run time

S[]

saguaro stack
SBB tree
scan
scapegoat tree
search algorithm
search tree
search tree property
secant search
memory segment
select algorithm
select and partition
selection problem
selection sort
select kth element
self-loop
self-organizing heuristic
self-organizing list
semidefinite programming
separator theorem
sequential search
set
set cover
set packing
shadow heap
shaker sort
Shannon–Fano coding
shared memory
Shell sort
Shift-Or
Shor's algorithm
shortest common supersequence
shortest common superstring
shortest path
shortest spanning tree
shuffle
shuffle sort
sibling
Sierpiński curve
Sierpinski triangle
sieve of Eratosthenes
signature
Simon's algorithm
simple path
simplex communication
simulated annealing
single-destination shortest-path problem
single-pair shortest-path problem
single program multiple data
single-source shortest-path problem
singly linked list
sink
sinking sort
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
soundex
space-constructible function
spanning tree
sparse graph
sparse matrix
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
s-t cut
Steiner minimum tree
Steiner point
Steiner ratio
Steiner tree
Steiner vertex
Steinhaus–Johnson–Trotter algorithm
Stirling's approximation
Stirling's formula
stooge sort
strand sort
strictly decreasing
strictly increasing
strictly lower triangular matrix
strictly upper triangular matrix
string
string matching
string searching
strongly connected component
strongly connected graph
strongly NP-hard
subgraph isomorphism
sublinear time algorithm
subsequence
subset
substring
subtree
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

T[]

tail
tail recursion
tango tree
temporal logic
terminal (see Steiner tree)
terminal node
ternary search
ternary search tree (TST)
text searching
theta
threaded binary tree
three-dimensional
three-way radix quicksort
time-constructible function
time/space complexity
top-down tree automaton
top-node
topological order
topological sort
total function
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
travelling salesman problem (TSP)
treap
tree
tree automaton
tree contraction
tree sort
tree transducer
tree traversal
triangle inequality
trie
trinary function
Turing machine
Turing reduction
two-dimensional
2–3 tree
2–3–4 tree
two-way linked list

U[]

unary function
unbounded knapsack problem (UKP)
uncomputable function
uncomputable problem
undecidable language
undecidable problem
undirected graph
uniform circuit complexity
uniform circuit family
uniform matrix
union
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
visible (geometry)
Viterbi algorithm
VP-tree
VRP (vehicle routing problem)

W[]

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

X[]

Xiaolin Wu's line algorithm
xor

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)
ZPP

References[]

^ Black, Paul E. "Dictionary of Algorithms and Data Structures". nist.gov. National Institute of Standards and Technology. Retrieved 2022-01-02.
^ ^a ^b Gerleman, Nick (2015-12-28). "The Bkd Tree". Medium. Retrieved 2020-10-07.

[dads-1] Black, Paul E. "Dictionary of Algorithms and Data Structures". nist.gov. National Institute of Standards and Technology. Retrieved 2022-01-02.

[bdk_tree-2] Gerleman, Nick (2015-12-28). "The Bkd Tree". Medium. Retrieved 2020-10-07.

[1]

[2]