Share This
table started by
Freebase Web Team for the Computer Science Base
There is no user-contributed description yet.
Add More Topics
Save this view to a base, or just for yourself.
121 Data Structure topics matching:
Filter this Collection| x name | x image | x Operations | x Space complexity | x article | |
|---|---|---|---|---|---|
| x Operation | x Time complexity | ||||
| x Octree |
|
An octree is a tree data structure in which each internal node has up to 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...
|
|||
| x 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 (the "vantage point") and dividing the data points into two partitions: those that are nearer to the vantage point than a...
|
||||
| x Quadtree |
A quadtree is a tree data structure in which each internal node has up to 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...
|
||||
| x 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.
AA trees are a variation of the red-black tree, which in turn is an...
|
||||
| x Deque |
|
In computer science, a double-ended queue (often abbreviated to deque, pronounced deck) is an abstract data structure that implements a queue for which elements can only be added to or removed from the front (head) or back (tail). It is also often...
|
|||
| x 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...
|
||||
| x Van Emde-Boas priority queue |
In computer science, a van Emde-Boas priority queue is an an efficient implementation a priority queue where insert, delete, get minimum, get maximum, etc. take O(log log N) time, where N is the total possible number of keys. Depending on the...
|
||||
| x Van Emde Boas tree |
A van Emde Boas tree (or van Emde Boas priority queue), 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(log m) time. Notice that m is the size of the...
|
||||
| x Fusion tree |
A fusion tree is a tree data structure that 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...
|
||||
| x 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. The most probable item is the root item. The left subtree consists of items less than the root item's...
|
|||
| x Scapegoat tree |
In computer science, a scapegoat tree is a self-balancing binary search tree, invented by Igal Galperin and Ronald L. Rivest. It provides worst-case O(log n) lookup time, and O(log n) amortized insertion and deletion time.
Unlike other self...
|
||||
| x Doubly Linked Face List |
A Doubly Linked Face List or DLFL is an efficient data structure for storing 2-manifold mesh data. The structure stores linked lists for a 3D mesh's faces, edges, vertices, and corners. The structure guarantees the preservation of the manifold...
|
||||
| x 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.
Min/max kd-trees may be constructed...
|
||||
| x 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...
|
||||
| x Sparse array |
In computer science, a sparse array is an array in which most of the elements have the same value (known as the default value -- usually 0 or null).
A naive implementation of an array may allocate space for the entire array, but in the case where...
|
||||
| x 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...
|
||||
| x 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...
|
||||
| x XOR linked list |
XOR linked lists are a data structure used in computer programming. They take advantage of the bitwise exclusive disjunction (XOR) operation, here denoted by ⊕, to decrease storage requirements for doubly-linked lists. An ordinary doubly-linked list...
|
||||
| x Doubly linked list |
A doubly linked list is a type of linked list allowing bi-directional traversal of the elements of the collection. It is achieved through the use of forward and backward links for each node in the list.
|
||||
| x 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 (or singly-linked) linked lists.
Like arrays, VLists have constant-time...
|
|||
| x Queue |
|
A queue (pronounced /kjuː/) is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal...
|
|||
| x Circular buffer |
A circular 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.
An example that could possibly use an overwriting circular...
|
||||
| x 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...
|
||||
| x 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....
|
|||
| x 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 AutoCAD, Adobe Illustrator, Acrobat 3D, OpenSceneGraph and CorelDRAW.
The scene graph...
|
||||
| x 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 (information only in the leaves) with records stored according to Z-order, also...
|
||||
| x 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.
The...
|
|||
| x R+ tree |
In computer science, an R+ tree is a tree data structure, a variant of the R tree, used for indexing spatial information.
R+ trees are a compromise between R trees and kd-trees; they avoid overlapping of internal nodes by inserting an object into...
|
||||
| x R* tree |
R* trees are a variant of R trees used for indexing spatial information. R* trees support point and spatial data at the same time with a slightly higher cost than other R-trees. It was proposed by Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider...
|
||||
| x Enfilade |
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. The Xanadu "Gold"...
|
||||
| x K-ary tree |
In graph theory, a k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree.
A binary tree is the special case where k=2.
A full k-ary tree is a k-ary...
|
||||
| x Dancing tree |
In computer science, a dancing tree is a tree data structure, which is similar to B+ tree. Invented by Hans Reiser, it is used by the Reiser4 file system. As opposed to self-balancing binary search trees that attempt to keep their nodes balanced at...
|
||||
| x Top Trees |
|
The Top Tree is a binary tree based data structure for unrooted dynamic trees which is used mainly for carrying out various path related operations, it allows simple Divide and conquer algorithms. It has since been augmented to maintain dynamically...
|
|||
| x 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 (d) of 1, and has 2 children. In an...
|
|||
| x Kd-trie |
A kd-trie is a spatial data structure for indexing points in k-dimensional space. It is a variation on the kd-tree that only stores points in the leaf nodes, sometimes in small collections called bins or buckets. Internal nodes only store the...
|
||||
| x Hash trie |
In computer science, hash trie refers to two kinds of data structure:
|
||||
| x Generalised suffix tree |
|
A generalised suffix tree is a suffix tree for a set of strings. Given the set of strings of total length n, it is a Patricia trie containing all n suffixes of the strings. It is mostly used in bioinformatics.
It can be built in Θ(n) time and space...
|
|||
| x (a,b)-tree |
In computer science, an (a,b) tree is a specific kind of search tree.
An (a,b) 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 . The root may have as few as...
|
||||
| x Abstract syntax tree |
|
In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract (simplified) syntactic structure of source code written in a certain programming language. Each node of the tree denotes a construct...
|
|||
| x Parse tree |
|
A concrete syntax tree or parse tree is 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...
|
|||
| x Bounding interval hierarchy |
A Bounding Interval Hierarchy (BIH) is a partitioning data structure similar to that of bounding volume hierarchies or kd-trees. Bounding interval hierarchies can be used in high performance (or real-time) ray tracing and may be especially useful...
|
||||
| x Adaptive k-d tree |
An adaptive k-d tree is a tree for multidimensional points where successive levels may be split along different dimensions.
Paul E. Black, Adaptive k-d tree at the NIST Dictionary of Algorithms and Data Structures.
|
||||
| x Implicit kd-tree |
|
An implicit kd-tree is a kd-tree defined implicitly above a rectilinear grid. Its splitting planes' positions and orientations are not given explicitly but implicitly by some recursive splitting-function defined on the hyperrectangles belonging to...
|
|||
| x And–or tree |
|
An and–or tree is a graphical representation of the reduction of problems (or goals) to conjunctions and disjunctions of subproblems (or subgoals).
The and-or tree: represents the search space for solving the problem P, using the goal-reduction...
|
|||
| x 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. Examples include vp-trees, cover trees...
|
||||
| x Bk tree |
A BK-tree is a metric tree suggested by Burkhard and Keller specifically adapted to discrete metric spaces. For simplicity, let us consider integer discrete metric . Then, BK-tree is defined in the following way. An arbitrary element a is selected...
|
||||
| x Cover tree |
The cover tree is a special type of data structure in computer science that is specifically designed to facilitate the speed-up of a nearest neighbor search. It was introduced by Alina Beygelzimer, John Langford, and Sham Kakade.
The tree can be...
|
||||
| x 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" (leaves) of the tree, where data is stored, and the internal...
|
||||
| x Decision tree |
|
A decision tree (or tree diagram) 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. Decision trees are commonly used in...
|
|||
| x Alternating decision tree |
|
An Alternating Decision Tree (ADTree) is a machine learning method for classification. The ADTree data structure and algorithm are a generalization of decision trees and have connections to boosting. ADTrees were introduced by Yoav Freund and Llew...
|
|||
| x 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...
|
||||
| x Suffix trie |
|
In computer science, a suffix trie of a string is a trie representing all the suffix of that string. When a suffix trie for string A has been constructed, it can be used to determine whether another string B is a substring of string A.
Formally, a...
|
|||
| x 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 designed for string keys. It was shown to offer...
|
||||
| x Hash array mapped trie |
A hash array mapped trie (HAMT) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie.
Implementation of a HAMT involves the use of the "CTPOP" function, which counts the number of...
|
||||
| x Fat tree |
|
The fat tree network, invented by Charles E. Leiserson of MIT, is a universal network for provably efficient communication. Unlike an ordinary computer scientist's notion of a tree, which has "skinny" links all over, the links in a fat-tree become ...
|
|||
| x PQ tree |
![The PQ tree representing [1 (2 3 4) 5]](http://img.freebase.com/api/trans/image_thumb/wikipedia/images/commons_id/654656?pad=1&errorid=%2Ffreebase%2Fno_image_png&maxheight=64&mode=fillcropmid&maxwidth=64)
|
A PQ tree is a tree-based data structure that represents a family of permutations on a set of elements, discovered and named by Kellogg S. Booth and George S. Lueker in 1976. It is a rooted, labeled tree, in which each element is represented by one...
|
|||
| x SPQR-tree |
The SPQR-tree is a tree data structure that represents the decomposition of a biconnected graph with respect to its triconnected components. It was introduced by Di Battista and Tamassia . Its main application is planarity testing and graph drawing....
|
||||
| x Directed acyclic word graph |
In computer science, a directed acyclic word graph (sometimes abbreviated as a DAWG) is a data structure that represents a set of strings, and allows for a query operation that tests whether a given string belongs to the set in time proportional to...
|
||||
| x Directed acyclic graph |
|
In mathematics, a directed acyclic graph (commonly abbreviated to DAG), is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is...
|
|||
| x T-pyramid |
A T-pyramid is a tree in which every internal node has (exactly) 4 child-nodes.
The arcs of the tree need not be recorded because the nodes can be stored in depth-first traversal order as with a heap.
|
||||
