Wikipedia

List of terms relating to algorithms and data structures

The NIST Dictionary of Algorithms and Data Structures 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

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 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)[1]
  • 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 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
  • 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
  • Doomsday rule
  • double-direction bubble sort
  • double-ended priority queue
  • double hashing
  • double left rotation
  • Double Metaphone
  • double right rotation
  • doubly 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
  • enfilade
  • 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

H

I

J

K

L

M

N

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

Q

R

S

T

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

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

X

Y

  • Yule–Simon distribution

Z

References

  1. ^ a b Gerleman, Nick (2015-12-28). "The Bkd Tree". Medium. Retrieved 2020-10-07.
This article is copied from an article on Wikipedia® - the free encyclopedia created and edited by its online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of Wikipedia® encyclopedia articles provide accurate and timely information, please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.

Copyright © 2003-2025 Farlex, Inc Disclaimer
All content on this website, including dictionary, thesaurus, literature, geography, and other reference data is for informational purposes only. This information should not be considered complete, up to date, and is not intended to be used in place of a visit, consultation, or advice of a legal, medical, or any other professional.