This is a list of data structure

Data structure

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...

s. For a wider list of terms, see list of terms relating to algorithms and data structures. For a comparison of running time of subset of this list see comparison of data structures

Comparison of data structures

In computer science, a search data structure is any data structure that allows the efficient retrieval of specific items from a set of items, such as a specific record from a database....

.

Primitive type

Primitive type

In computer science, primitive data type is either of the following:* a basic type is a data type provided by a programming language as a basic building block...

s

• Boolean (for boolean values True/False)
• Char (for character values)
• Float (for storing real number values)
• Double (a larger size of type float)
  Double precision
  In computing, double precision is a computer number format that occupies two adjacent storage locations in computer memory. A double-precision number, sometimes simply called a double, may be defined to be an integer, fixed point, or floating point .Modern computers with 32-bit storage locations...
  
  
• int (for integral or fixed-precision values)
• String (for string of chars)
• Enumerated type
  Enumerated type
  In computer programming, an enumerated type is a data type consisting of a set of named values called elements, members or enumerators of the type. The enumerator names are usually identifiers that behave as constants in the language...
  
  

Composite type

Composite type

In computer science, a composite data type is any data type which can be constructed in a program using its programming language's primitive data types and other composite types...

s

• Array
  Array
  In computer science, an array data structure or simply array is a data structure consisting of a collection of elements , each identified by at least one index...
  
  
• Record
  Record (computer science)
  In computer science, a record is an instance of a product of primitive data types called a tuple. In C it is the compound data in a struct. Records are among the simplest data structures. A record is a value that contains other values, typically in fixed number and sequence and typically indexed...
  
   (also called tuple or struct)
• Union
• Tagged union
  Tagged union
  In computer science, a tagged union, also called a variant, variant record, discriminated union, or disjoint union, is a data structure used to hold a value that could take on several different, but fixed types. Only one of the types can be in use at any one time, and a tag field explicitly...
  
   (also called a variant
  Variant type
  Variant is a data type in certain programming languages, particularly Visual Basic and C++ when using the Component Object Model.In Visual Basic the Variant data type is a tagged union that can be used to represent any other data type except fixed-length string type and...
  
  , variant record, discriminated union, or disjoint union)
• Plain old data structure

Abstract data types 

• Container
  Container (data structure)
  In computer science, a container is a class, a data structure, or an abstract data type whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules...
  
  
• Deque
  Deque
  In computer science, a double-ended queue is an abstract data structure that implements a queue for which elements can only be added to or removed from the front or back...
  
  
• Map/Associative array/Dictionary
  Associative array
  In computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....
  
  
• Multimap
• Multiset
• Priority queue
  Priority queue
  A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
  
  
• Queue
• Set
  Set (computer science)
  In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set...
  
  
• Stack
  Stack (data structure)
  In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
  
  
• String
  String (computer science)
  In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
  
  
• Tree
• Graph
  Graph (data structure)
  In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
  
  
• Hash
  Hash table
  In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
  
  

Some properties of abstract data types:

Structure	Stable	Unique	Cells per Node
Bag (multiset Multiset In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once... )	no	no	1
Set Set (computer science) In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set...	no	yes	1
List	yes	no	1
Map Associative array In computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....	no	yes	2

"Stable" means that input order is retained. Other structures such as "linked list" and "stack" cannot easily be defined this way because there are specific operations associated with them.

Arrays

• Array
• Bidirectional map
  Bidirectional map
  In computer science, a bidirectional map is an associative data structure in which both types can be used as key.-External links:* http://www.boost.org/doc/libs/1_47_0/libs/bimap/doc/html/index.html...
  
  
• Bit array
• Bit field
  Bit field
  A bit field is a common idiom used in computer programming to compactly store multiple logical values as a short series of bits where each of the single bits can be addressed separately. A bit field is most commonly used to represent integral types of known, fixed bit-width. A well-known usage of...
  
  
• Bitboard
  Bitboard
  A bitboard is a data structure commonly used in computer systems that play board games.A bitboard, often used for boardgames such as chess, checkers and othello, is a specialization of the bitset data structure, where each bit represents a game position or state, designed for optimization of speed...
  
  
• Bitmap
  Bitmap
  In computer graphics, a bitmap or pixmap is a type of memory organization or image file format used to store digital images. The term bitmap comes from the computer programming terminology, meaning just a map of bits, a spatially mapped array of bits. Now, along with pixmap, it commonly refers to...
  
  
• Circular buffer
  Circular buffer
  A circular buffer, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end.This structure lends itself easily to buffering data streams.-Uses:...
  
  
• Control table
  Control table
  Control tables are tables that control the program flow or play a major part in program control. There are no rigid rules concerning the structure or content of a control table - its only qualifying attribute is its ability to direct program flow in some way through its 'execution' by an associated...
  
  
• Image
  Digital image
  A digital image is a numeric representation of a two-dimensional image. Depending on whether or not the image resolution is fixed, it may be of vector or raster type...
  
  
• Dynamic array
  Dynamic array
  In computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is a random access, variable-size list data structure that allows elements to be added or removed...
  
  
• Gap buffer
  Gap buffer
  A gap buffer In computer science is a dynamic array that allows efficient insertion and deletion operations clustered near the same location. Gap buffers are especially common in text editors, where most changes to the text occur at or near the current location of the cursor. The text is stored in...
  
  
• Hashed array tree
  Hashed array tree
  In computer science, a hashed array tree is a dynamic array algorithm published by Edward Sitarski in 1996. Whereas simple dynamic array data structures based on geometric expansion waste linear space, where n is the number of elements in the array, hashed array trees waste only order n1/2...
  
  
• Heightmap
  Heightmap
  In computer graphics, a heightmap or heightfield is a raster image used to store values, such as surface elevation data, for display in 3D computer graphics...
  
  
• Lookup table
  Lookup table
  In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
  
  
• Matrix
• Parallel array
  Parallel array
  In computing, a parallel array is a data structure for representing arrays of records. It keeps a separate, homogeneous array for each field of the record, each having the same number of elements. Then, objects located at the same index in each array are implicitly the fields of a single record....
  
  
• Sorted array
  Sorted array
  A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. It is typically used in computer science to implement static lookup tables to hold multiple values which has the same...
  
  
• Sparse array
  Sparse array
  In computer science, a sparse array is an array in which most of the elements have the same value . The occurrence of zero elements in a large array is inconvenient for both computation and storage...
  
  
• Sparse matrix
  Sparse matrix
  In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
  
  
• Iliffe vector
  Iliffe vector
  In computer programming, an Iliffe vector, also known as a display, is a data structure used to implement multi-dimensional arrays. An Iliffe vector for an n-dimensional array consists of a vector of pointers to an -dimensional array...
  
  
• Variable-length array
  Variable-length array
  In programming, a variable-length array is an array data structure of automatic storage duration whose length is determined at run time ....
  
  

Lists

• Doubly linked list
• Linked list
  Linked list
  In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
  
  
• Self-organizing list
  Self-organizing list
  A self-organizing list is a list that reorders its elements based on some self-organizing heuristic to improve average access time.The aim of Self organizing list is to improve efficiency of linear search by moving more frequently accessed items towards the head of the list.The "Self Organizing...
  
  
• Skip list
  Skip list
  A skip list is a data structure for storing a sorted list of items using a hierarchy of linked lists that connect increasingly sparse subsequences of the items...
  
  
• Unrolled linked list
  Unrolled linked list
  In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can drastically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as references...
  
  
• VList
  VList
  In computer science, the VList is a persistent data structure designed by Phil Bagwell in 2002 that combines the fast indexing of arrays with the easy extension of cons-based linked lists....
  
  
• Xor linked list
  XOR linked list
  An XOR linked list is a data structure used in computer programming. They take advantage of the bitwise exclusive disjunction operation, here denoted by ⊕, to decrease storage requirements for doubly linked lists. An ordinary doubly linked list stores addresses of the previous and next list items...
  
  
• Zipper
  Zipper (data structure)
  A zipper is a technique of representing an aggregate data structure so that it is convenient for writing programs that traverse the structure arbitrarily and update its contents, especially in purely functional programming languages. The zipper was described by Gérard Huet in 1997...
  
  
• Doubly connected edge list

Binary trees

• AA tree
  AA tree
  An AA tree in computer science is a form of balanced tree used for storing and retrieving ordered data efficiently. AA trees are named for Arne Andersson, their inventor....
  
  
• AVL tree
  AVL tree
  In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O time in both the average and worst...
  
  
• Binary search tree
  Binary search tree
  In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...
  
  
• Binary tree
  Binary tree
  In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...
  
  
• Cartesian tree
  Cartesian tree
  In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric traversal of the tree returns the original sequence...
  
  
• Randomized binary search tree
• Red-black tree
  Red-black tree
  A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by...
  
  
• Rope
  Rope (computer science)
  In computer programming a rope, or cord, is a data structure for efficiently storing and manipulating a very long string. For example, a text editing program may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done...
  
  
• Scapegoat tree
  Scapegoat tree
  In computer science, a scapegoat tree is a self-balancing binary search tree, discovered by Arne Anderson and again by Igal Galperin and Ronald L. Rivest...
  
  
• Self-balancing binary search tree
  Self-balancing binary search tree
  In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....
  
  
• Splay tree
  Splay tree
  A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O amortized time. For many sequences of nonrandom operations, splay trees perform...
  
  
• T-tree
  T-tree
  In computer science a T-tree is a type of binary treedata structure that is used by main-memory databases, such asDatablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen and MobileLite....
  
  
• Tango tree
• Threaded binary tree
  Threaded binary tree
  A threaded binary tree defined as follows:"A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the node."A threaded binary...
  
  
• Top tree
  Top tree
  A Top tree is a data structure based on a binary tree for unrooted dynamic trees that is used mainly for various path-related operations. It allows simple divide-and-conquer algorithms...
  
  
• Treap
  Treap
  In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys...
  
  
• Weight-balanced tree
  Weight-balanced tree
  A weight-balanced binary tree is a binary tree which is balanced based on knowledge of the probabilities of searching for each individual node. Within each subtree, the node with the highest weight appears at the root...
  
  

B-trees

• B-tree
  B-tree
  In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children...
  
  
• B+ tree
  B+ tree
  In computer science, a B+ tree or B plus tree is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of...
  
  
• B*-tree
• B sharp tree
• Dancing tree
  Dancing tree
  For the film Dancing tree, see Dancing tree In computer science, a dancing tree is a tree data structure, which is similar to B+ tree. Invented by Hans Reiser, for use by the Reiser4 file system...
  
  
• 2-3 tree
  2-3 tree
  In computer science, a 2-3 tree is a type of data structure, a tree where every node with children has either two children and one data element or three children and two data elements...
  
  
• 2-3-4 tree
  2-3-4 tree
  In computer science, a 2-3-4 tree is a self-balancing data structure that is commonly used to implement dictionaries...
  
  
• Queap
  Queap
  In computer science, a queap is a priority queue data structure that points to the smallest stored item. Queap is composed of a doubly linked list and a 2-4 tree data structure...
  
  
• Fusion tree
  Fusion tree
  A fusion tree is a type of tree data structure in computer science. It implements an associative array with integer keys up to a fixed size; by exploiting the constant-time machine word multiplication operation available on many real processors, it is able to achieve all operations inO\lefttime ,...
  
  
• Bx-tree
  Bx-tree Moving Object Index
  In computer science, the Bx tree is a query and update efficient B+ tree-based index structure for moving objects.-Index structure:The base structure of the Bx-tree is a B+ tree in which the internal nodes serve as a directory, each containing a pointer to its right sibling...
  
  

Heaps

• Heap
  Heap (data structure)
  In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key ≥ key. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap...
  
  
• Binary heap
  Binary heap
  A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:*The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one are fully filled, and, if the last level of...
  
  
• Binomial heap
  Binomial heap
  In computer science, a binomial heap is a heap similar to a binary heap but also supports quickly merging two heaps. This is achieved by using a special tree structure...
  
  
• Fibonacci heap
  Fibonacci heap
  In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987...
  
  
  • AF-heap
    AF-heap
    In computer science, the AF-heap is a type of priority queue for integer data, an extension of the fusion tree using an atomic heap proposed by M. L. Fredman and D. E. Willard....
    
    
• 2-3 heap
  2-3 heap
  In computer science, a 2-3 heap is a data structure, a variation on the heap, designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap, and borrows from the 2-3 tree.Time costs for some common heap operations:...
  
  
• Soft heap
  Soft heap
  In computer science, a soft heap is a variant on the simple heap data structure that has constant amortized time for 5 types of operations. This is achieved by carefully "corrupting" the keys of at most a certain fixed percentage of values in the heap...
  
  
• Pairing heap
  Pairing heap
  A pairing heaps is a type of heap data structure with relatively simple implementation and excellent practical amortized performance. However, it has proven very difficult to determine the precise asymptotic running time of pairing heaps....
  
  
• Leftist heap
  Leftist tree
  A leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced...
  
  
• Treap
  Treap
  In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys...
  
  
• Beap
  Beap
  Beap, or bi-parental heap, is a data structure where a node usually has two parents and two children . Unlike a heap, a beap allows sublinear search. The beap was introduced by Ian Munro and Hendra Suwanda...
  
  
• Skew heap
  Skew heap
  A skew heap is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast with binary heaps, there are no structural constraints, so there is no guarantee that the height of the tree is logarithmic...
  
  
• Ternary heap
• D-ary heap
  D-ary heap
  The -ary heap or -heap is a priority queue data structure, a generalization of the binary heap in which the nodes have children instead of 2. Thus, a binary heap is a 2-heap. According to Tarjan and Jensen et al., -ary heaps were invented by Donald B...
  
  

Tries

In these data structures each tree node compares a bit slice of key values.

• Trie
  Trie
  In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the...
  
  
• Radix tree
  Radix tree
  In computer science, a radix tree is a space-optimized trie data structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. Unlike in regular tries, edges can be labeled with sequences of characters as well as single...
  
  
• Suffix tree
  Suffix tree
  In computer science, a suffix tree is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many important string operations.The suffix tree for a string S is a tree whose edges are labeled with strings, such that each suffix...
  
  
• Suffix array
  Suffix array
  In computer science, a suffix array is an array of integers giving the starting positions of suffixes of a string in lexicographical order.-Details:Consider the string...
  
  
• Compressed suffix array
  Compressed suffix array
  The Compressed Suffix Array is a compressed data structure for pattern matching. Given a text T of n characters from an alphabet Σ, the compressed suffix array support searching for arbitrary patterns in T...
  
  
• FM-index
  FM-index
  The FM-index is type of Substring index based on the Burrows-Wheeler transform,with some similarities to the Suffix Array.It is named after the creators of the algorithm, Paolo Ferragina and Giovanni Manzini, who describe it as an opportunistic data structure as it allows compression of the input...
  
  
• Generalised suffix tree
  Generalised suffix tree
  A generalised suffix tree is a suffix tree for a set of strings. Given the set of strings D=S_1,S_2,\dots,S_d of total length n, it is a Patricia tree containing all n suffixes of the strings...
  
  
• B-trie
  B-trie
  The B-trie is a trie-based data structure that can store and retrieve variable-length strings efficiently on disk.The B-trie was compared against several high-performance variants of B-tree that were...
  
  
• Judy array
  Judy array
  In computer science and software engineering, a Judy array is a data structure that has high performance, low memory usage and implements an associative array. Unlike normal arrays, Judy arrays may be sparse, that is, they may have large ranges of unassigned indices. They can be used for storing...
  
  
• X-fast trie
  X-fast trie
  In computer science, an x-fast trie is a data structure for storing integers from a bounded domain. It supports exact and predecessor or successor queries in time O, using O space, where n is the number of stored values and M is the maximum value in the domain...
  
  
• Y-fast trie
  Y-fast trie
  In computer science, a y-fast trie is a data structure for storing integers from a bounded domain. It supports exact and predecessor or successor queries in time O, using O space, where n is the number of stored values and M is the maximum value in the domain...
  
  
• Ctrie
  Ctrie
  A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and is memory-efficient...
  
  

Multiway trees

• Ternary search tree
  Ternary search tree
  In computer science, a ternary search tree is a special trie data structure where the child nodes of a standard trie are ordered as a binary search tree. Searching for a string in a ternary search tree consists of a series of binary searches, one for each character in the string...
  
  
• And–or tree
• (a,b)-tree
  (a,b)-tree
  In computer science, an tree is a specific kind of search tree.An tree has all of its leaves at the same depth, and all internal nodes have between a and b children, where a and b are integers such that 2 \le a \le /2. The root may have as few as zero children.- Definition :Let a, b \in N such...
  
  
• Link/cut tree
  Link/cut tree
  A link/cut tree is a type of data structure that can merge and split data sets in O amortized time, and can find which tree an element belongs to in O amortized time. In the original publication, Sleator and Tarjan referred to link/cut trees as "dynamic trees"....
  
  
• SPQR-tree
  SPQR-tree
  In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the...
  
  
• Spaghetti stack
  Spaghetti stack
  A spaghetti stack in computer science is an N-ary tree data structure in which child nodes have pointers to the parent nodes . When a list of nodes is traversed from a leaf node to the root node by chasing these parent pointers, the structure looks like a linked list stack...
  
  
• Disjoint-set data structure
  Disjoint-set data structure
  In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:* Find: Determine which set a particular element...
  
  
• Fusion tree
  Fusion tree
  A fusion tree is a type of tree data structure in computer science. It implements an associative array with integer keys up to a fixed size; by exploiting the constant-time machine word multiplication operation available on many real processors, it is able to achieve all operations inO\lefttime ,...
  
  
• Enfilade
  Enfilade (Xanadu)
  Enfilades are a class of tree data structures used in Project Xanadu designs of the 1970s and 1980s. Enfilades allow quick editing, versioning, retrieval and inter-comparison operations in a large, cross-linked hypertext database...
  
  
• Exponential tree
  Exponential tree
  An exponential tree is almost identical to a binary search tree, with the exception that the dimension of the tree is not the same at all levels. In a normal binary search tree, each node has a dimension of 1, and has 2d children. In an exponential tree, the dimension equals the depth of the node,...
  
  
• Fenwick tree
  Fenwick tree
  A Fenwick tree is a data structure that can be used to implement cumulative frequency tables. It was invented by Peter Fenwick in 1994. -Structure:...
  
  
• Van Emde Boas tree
  Van Emde Boas tree
  A van Emde Boas tree , also known as a vEB tree, is a tree data structure which implements an associative array with m-bit integer keys. It performs all operations in O time...
  
  

Space-partitioning trees

These are data structures used for space partitioning

Space partitioning

In mathematics, space partitioning is the process of dividing a space into two or more disjoint subsets . In other words, space partitioning divides a space into non-overlapping regions...

 or binary space partitioning

Binary space partitioning

In computer science, binary space partitioning is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.Originally, this approach was proposed in 3D computer...

.

• Segment tree
  Segment tree
  In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built...
  
  
• Interval tree
  Interval tree
  In computer science, an interval tree is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for example, to find all roads on a computerized map inside...
  
  
• Range tree
  Range tree
  In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be efficiently retrieved, and is typically used in two or higher dimensions....
  
  
• Bin
  Bin (computational geometry)
  In computational geometry, the bin data structure allows efficient region queries, i.e., if there are some axis-aligned rectangles on a 2D plane, answer the question Given a query rectangle, return all rectangles intersecting it. kd-tree is another data structure that can answer this question...
  
  
• Kd-tree
  Kd-tree
  In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...
  
  
• Implicit kd-tree
  Implicit kd-tree
  An implicit k-d tree is a k-d tree defined implicitly above a rectilinear grid. Its split planes' positions and orientations are not given explicitly but implicitly by some recursive splitting-function defined on the hyperrectangles belonging to the tree's nodes...
  
  
• Min/max kd-tree
  Min/max kd-tree
  A min/max kd-tree is a kd-tree with two scalar values - a minimum and a maximum - assigned to its nodes. The minimum/maximum of an inner node is equal the minimum/maximum of its children's minima/maxima.-Construction:...
  
  
• Adaptive k-d tree
  Adaptive k-d tree
  An adaptive k-d tree is a tree for multidimensional points where successive levels may be split along different dimensions....
  
  
• Kdb tree
• Quadtree
  Quadtree
  A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...
  
  
• Octree
  Octree
  An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree,...
  
  
• Linear octree
  Linear octree
  A linear octree is an octree that is represented by a linear array instead of a tree data structure.To simplify implementation, a linear octree is usually complete and where the maximum permissible depth is fixed a priori...
  
  
• Z-order
  Z-order (curve)
  In mathematical analysis and computer science, Z-order, Morton order, or Morton code is a space-filling curve which maps multidimensional data to one dimension while preserving locality of the data points. It was introduced in 1966 by G. M. Morton...
  
  
• UB-tree
  UB-tree
  The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree with records stored according to Z-order, also called Morton order...
  
  
• R-tree
  R-tree
  R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both research and real-world applications...
  
  
• R+ tree
  R+ tree
  An R+ tree is a method for looking up data using a location, often coordinates, and often for locations on the surface of the earth. Searching on one number is a solved problem; searching on two or more, and asking for locations that are nearby in both x and y directions, requires craftier...
  
  
• R* tree
• Hilbert R-tree
  Hilbert R-tree
  Hilbert R-tree, an R-tree variant, is an index for multidimensional objects like lines, regions, 3-D objects, or high dimensional feature-based parametric objects. It can be thought of as an extension to B+-tree for multidimensional objects....
  
  
• X-tree
  X-tree
  In computer science, an X-tree is an index tree structure based on the R-tree used for storing data in many dimensions. It differs from R-trees, R+-trees and R*-trees because it emphasizes prevention of overlap in the bounding boxes, which increasingly becomes a problem in high dimensions...
  
  
• Metric tree
  Metric tree
  A metric tree is any tree data structure specialized to index data in metric spaces. Metric trees exploit properties of metric spaces such as the triangle inequality to make accesses to the data more efficient...
  
  
• Cover tree
  Cover tree
  The cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed-up of a nearest neighbor search...
  
  
• M-tree
  M-tree
  M-trees are tree data structures that are similar to R-trees and B-trees. It is constructed using a metric and relies on the triangle inequality for efficient range and k-NN queries....
  
  
• VP-tree
  Vp-tree
  A vantage-point tree, or vp-tree is a BSP tree that segregates data in a metric space by choosing a position in the space and dividing the data points into two partitions: those that are nearer to the vantage point than a threshold, and those that are not...
  
  
• BK-tree
• Bounding interval hierarchy
  Bounding interval hierarchy
  A bounding interval hierarchy is a partitioning data structure similar to that of bounding volume hierarchies or kd-trees. Bounding interval hierarchies can be used in high performance ray tracing and may be especially useful for dynamic scenes.The BIH itself is, however, not new...
  
  
• BSP tree
• Rapidly-exploring random tree
  Rapidly-exploring random tree
  A Rapidly-exploring random tree is a data structure and algorithm designed for efficiently searching nonconvex, high-dimensional search spaces. The tree is constructed in such a way that any sample in the space is added by connecting it to the closest sample already in the tree.RRTs, developed by...
  
  

Application-specific trees

• Syntax tree
• Abstract syntax tree
  Abstract syntax tree
  In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...
  
  
• Parse tree
  Parse tree
  A concrete syntax tree or parse tree or parsing treeis an ordered, rooted tree that represents the syntactic structure of a string according to some formal grammar. In a parse tree, the interior nodes are labeled by non-terminals of the grammar, while the leaf nodes are labeled by terminals of the...
  
  
• Decision tree
  Decision tree
  A decision tree is a decision support tool that uses a tree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm. Decision trees are commonly used in operations research, specifically...
  
  
• Alternating decision tree
  Alternating decision tree
  An alternating decision tree is a machine learning method for classification. It generalizes decision trees and has connections to boosting.-History:...
  
  
• Minimax tree
• Expectiminimax tree
  Expectiminimax tree
  An expectiminimax tree is a specialized variation of a minimax game tree for use in artificial intelligence systems that play two-player zero-sum games such as backgammon, in which the outcome depends a combination of the player's skill and chance elements such as dice rolls...
  
  
• Finger tree
  Finger tree
  A finger tree is a purely functional data structure used in efficiently implementing other functional data structures. A finger tree gives amortized constant time access to the "fingers" of the tree, where data is stored, and the internal nodes are labeled in some way as to provide the...
  
  

Hashes

• Bloom filter
  Bloom filter
  A Bloom filter, conceived by Burton Howard Bloom in 1970, is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not; i.e. a query returns either "inside set " or "definitely not in set"...
  
  
• Distributed hash table
  Distributed hash table
  A distributed hash table is a class of a decentralized distributed system that provides a lookup service similar to a hash table; pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key...
  
  
• Hash array mapped trie
  Hash array mapped trie
  A hash array mapped trie is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie.- Operation :...
  
  
• Hash list
  Hash list
  In computer science, a hash list is typically a list of hashes of the data blocks in a file or set of files. Lists of hashes are used for many different purposes, such as fast table lookup and distributed databases...
  
  
• Hash table
  Hash table
  In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
  
  
• Hash tree
  Hash tree
  In cryptography and computer science Hash trees or Merkle trees are a type of data structure which contains a tree of summary information about a larger piece of data – for instance a file – used to verify its contents. Hash trees are a combination of hash lists and hash chaining, which in turn are...
  
  
• Hash trie
  Hash trie
  In computer science, hash trie can refer to:* A space-efficient implementation of a sparse trie, in which the descendants of each node may be interleaved in memory...
  
  
• Koorde
  Koorde
  In peer-to-peer networks, Koorde is a Distributed hash table system based on the Chord DHT and the De Bruijn graph . Inheriting the simplicity of Chord, Koorde meets O hops per node , and O hops per lookup request with O neighbors per node.The Chord concept is based on a wide range of...
  
  
• Prefix hash tree
  Prefix hash tree
  A prefix hash tree is a distributed data structure that enables more sophisticated queries over a distributed hash table . The prefix hash tree uses the lookup interface of a DHT to construct a trie-based data structure that is both efficient , and resilient A prefix hash tree (PHT) is a...
  
  

Graphs

• Graph
  Graph (data structure)
  In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
  
  
• Adjacency list
  Adjacency list
  In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list.If the graph is undirected, every entry is a set of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node...
  
  
• Adjacency matrix
  Adjacency matrix
  In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
  
  
• Graph-structured stack
  Graph-structured stack
  In computer science, a graph-structured stack is a directed acyclic graph where each directed path represents a stack.The graph-structured stack is an essential part of Tomita's algorithm, where it replaces the usual stack of a pushdown automaton...
  
  
• Scene graph
  Scene graph
  A scene graph is a general data structure commonly used by vector-based graphics editing applications and modern computer games. Examples of such programs include Acrobat 3D, Adobe Illustrator, AutoCAD, CorelDRAW, OpenSceneGraph, OpenSG, VRML97, and X3D....
  
  
• Binary decision diagram
  Binary decision diagram
  In the field of computer science, a binary decision diagram or branching program, like a negation normal form or a propositional directed acyclic graph , is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed...
  
  
• Zero suppressed decision diagram
  Zero suppressed decision diagram
  A zero-suppressed decision diagram is a version of binary decision diagram where instead of nodes being introduced when the positive and the negative part are different, they are introduced when negative part is different from constant 0...
  
  
• And-inverter graph
  And-inverter graph
  An and-inverter graph is a directed, acyclic graph that represents a structural implementation of the logical functionality of a circuit or network. An AIG consists of two-input nodes representing logical conjunction, terminal nodes labeled with variable names, and edges optionally containing...
  
  
• Propositional directed acyclic graph
  Propositional directed acyclic graph
  A propositional directed acyclic graph is a data structure that is used to represent a Boolean function. A Boolean function can be represented as a rooted, directed acyclic graph of the following form:...
  
  
• Directed graph
  Directed graph
  A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
  
  
• Multigraph
  Multigraph
  In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge....
  
  
• Hypergraph
  Hypergraph
  In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...