# Category: Trees (data structures)

Ordinal tree
An ordinal tree, by analogy with an ordinal number, is a rooted tree of arbitrary degree in which the children of each node are ordered, so that one refers to the ith child in the sequence of children
Finger search
In computer science, a finger search on a data structure is an extension of any search operation that structure supports, where a reference (finger) to an element in the data structure is given along
An adaptive k-d tree is a tree for multidimensional points where successive levels may be split along different dimensions.
Tree automaton
A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree autom
Min/max kd-tree
A min/max kd-tree is a k-d tree with two scalar values - a minimum and a maximum - assigned to its nodes. The minimum/maximum of an inner node is equal to the minimum/maximum of its children's minima/
Phylogenetic tree
A phylogenetic tree (also phylogeny or evolutionary tree ) is a branching diagram or a tree showing the evolutionary relationships among various biological species or other entities based upon similar
Tree-walking automaton
A tree-walking automaton (TWA) is a type of finite automaton that deals with tree structures rather than strings. The concept was originally proposed by Aho and Ullman. The following article deals wit
Sentinel node
In computer programming, a sentinel node is a specifically designated node used with linked lists and trees as a traversal path terminator. This type of node does not hold or reference any data manage
Tree accumulation
In computer science, tree accumulation is the process of accumulating data placed in treenodes according to their tree structure. Formally, this operation is a catamorphism. Upward accumulation refers
K-d tree
In computer science, a k-d tree (short for k-dimensional 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
Outline (list)
An outline, also called a hierarchical outline, is a list arranged to show hierarchical relationships and is a type of tree structure. An outline is used to present the main points (in sentences) or t
Wavelet Tree
The Wavelet Tree is a succinct data structure to store strings in compressed space. It generalizes the and operations defined on bitvectors to arbitrary alphabets. Originally introduced to represent c
Infinite-tree automaton
In computer science and mathematical logic, an infinite-tree automaton is a state machine that deals with infinite tree structures. It can be seen as an extension of top-down finite-tree automata to i
Bitwise trie with bitmap
A bitwise trie is a special form of trie where each node with its child-branches represents a bit sequence of one or more bits of a key. A bitwise trie with bitmap uses a bitmap to denote valid child
Ternary search tree
In computer science, a ternary search tree is a type of trie (sometimes called a prefix tree) where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather
Leftist tree
In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which is the distance to the nearest leaf in subtree ro
Relaxed k-d tree
A relaxed K-d tree or relaxed K-dimensional tree is a data structure which is a variant of K-d trees. Like K-dimensional trees, a relaxed K-dimensional tree stores a set of n-multidimensional records,
Fenwick tree
A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by Boris Ryabko in 1989with
Hash trie
In computer science, hash trie can refer to: * Hash tree (persistent data structure), a trie used to map hash values to keys * A space-efficient implementation of a sparse trie, in which the descend
Pebble automaton
In computer science, a pebble automaton is any variant of an automaton which augments the original model with a finite number of "pebbles" that may be used to mark tape positions.
Calkin–Wilf tree
In number theory, the Calkin–Wilf tree is a tree in which the vertices correspond one-to-one to the positive rational numbers. The tree is rooted at the number 1, and any rational number expressed in
PQ tree
A PQ tree is a tree-based data structure that represents a family of permutations on a set of elements, discovered and named by and in 1976. It is a rooted, labeled tree, in which each element is repr
Stern–Brocot tree
In number theory, the Stern–Brocot tree is an infinite complete binary tree in which the vertices correspond one-for-one to the positive rational numbers, whose values are ordered from the left to the
Binomial options pricing model
In finance, the binomial options pricing model (BOPM) provides a generalizable numerical method for the valuation of options. Essentially, the model uses a "discrete-time" (lattice based) model of the
H tree
In fractal geometry, the H tree is a fractal tree structure constructed from perpendicular line segments, each smaller by a factor of the square root of 2 from the next larger adjacent segment. It is
PH-tree
The PH-tree is a tree data structure used for spatial indexing of multi-dimensional data (keys) such as geographical coordinates, points, feature vectors, rectangles or bounding boxes. The PH-tree is
Embedded Zerotrees of Wavelet transforms
Embedded Zerotrees of Wavelet transforms (EZW) is a lossy image compression algorithm. At low bit rates, i.e. high compression ratios, most of the coefficients produced by a subband transform (such as
Conc-tree list
A conc-tree is a data structure that stores element sequences, and provides amortized O(1) time append and prepend operations, O(log n) time insert and remove operations and O(log n) time concatenatio
Tree of primitive Pythagorean triples
In mathematics, a tree of primitive Pythagorean triples is a data tree in which each node branches to three subsequent nodes with the infinite set of all nodes giving all (and only) primitive Pythagor
HAT-trie
The HAT-trie is a type of radix trie that uses array nodes to collect individual key–value pairs under radix nodes and hash buckets into an associative array. Unlike a simple hash table, HAT-tries sto
Branching factor
In computing, tree data structures, and game theory, the branching factor is the number of children at each node, the outdegree. If this value is not uniform, an average branching factor can be calcul
Parent pointer tree
In computer science, an in-tree or parent pointer tree is an N-ary tree data structure in which each node has a pointer to its parent node, but no pointers to child nodes. When used to implement a set
Finger search tree
In computer science, finger search trees are a type of binary search tree that keeps pointers to interior nodes, called fingers. The fingers speed up searches, insertions, and deletions for elements c
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(log log M), using O(n) space, where
Doubly logarithmic tree
In computer science a doubly logarithmic tree is a tree where each internal node of height 1, the tree layer above the leaves, has two children, and each internal node of height has children. Each chi
Program structure tree
A program structure tree (PST) is a hierarchical diagram that displays the nesting relationship of single-entry single-exit (SESE) fragments/regions, showing the organization of a computer program. No
In computer science, a linked data structure is a data structure which consists of a set of data records (nodes) linked together and organized by references (links or pointers). The link between data
Tree contraction
In computer science, parallel tree contraction is a broadly applicable technique for the parallel solution of a large number of tree problems, and is used as an algorithm design technique for the desi
GiST
In computing, GiST or Generalized Search Tree, is a data structure and API that can be used to build a variety of disk-based search trees. GiST is a generalization of the B+ tree, providing a concurre
A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations: * Add a tree consisting of a single node to the forest. * Given a node in o
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
Ternary tree
In computer science, a ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as "left", “mid” and "right". Nodes with children are parent nodes,
Abstract syntax tree
In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of text (often source code) written in a formal language. Each nod
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(log log M), using O(n log M) space,
Implicit k-d 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-functio
C-trie
A C-trie is a compressed trie data structure. It achieves lower memory and query time requirements at the expense of reduced flexibility.
Prefix order
In mathematics, especially order theory, a prefix ordered set generalizes the intuitive concept of a tree by introducing the possibility of continuous progress and continuous branching. Natural prefix
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 o
Rose tree
In computing, a rose tree is a term for the value of a tree data structure with a variable and unbounded number of branches per node. The term is mostly used in the functional programming community, e
Descendant tree (group theory)
In mathematics, specifically group theory, a descendant tree is a hierarchical structure that visualizes parent-descendant relations between isomorphism classes of finite groups of prime power order ,
In computer science, a radix tree (also radix trie or compact prefix tree or compressed trie) is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the on
Fusion tree
In computer science, a fusion tree is a type of tree data structure that implements an associative array on w-bit integers on a finite universe, where each of the input integer has size less than 2w a
T-theory
T-theory is a branch of discrete mathematics dealing with analysis of trees and discrete metric spaces.
Ranked alphabet
In theoretical computer science and formal language theory, a ranked alphabet is a pair of an ordinary alphabet F and a function Arity: F→. Each letter in F has its arity so it can be used to build te
Ball tree
In computer science, a ball tree, balltree or metric tree, is a space partitioning data structure for organizing points in a multi-dimensional space. The ball tree gets its name from the fact that it
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).
Treemapping
In information visualization and computing, treemapping is a method for displaying hierarchical data using nested figures, usually rectangles. Treemaps display hierarchical (tree-structured) data as a
Key-independent optimality
Key-independent optimality is a property of some binary search tree data structures in computer scienceproposed by John Iacono.Suppose that key-value pairs are stored in a datastructure, and that the
Polychotomous key
Polychotomous key refers to the number of alternatives which a decision point may have in a non-temporal hierarchy of independent variables. The number of alternatives are equivalent to the root or nt
Right rotation
Right rotation refers to the following * In an array, moving all items to the next higher location. The last item is moved to the first location, which has been vacated. * In a list, removing the ta
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 reported efficiently, and is typically used in two or high
Left rotation
Left rotation refers to the following * In an array, moving all items to the next lower location. The first item is moved to the last location, which is now vacant. * In a list, removing the head an
Tree transducer
In theoretical computer science and formal language theory, a tree transducer (TT) is an abstract machine taking as input a tree, and generating output – generally other trees, but models producing wo
Enfilades are a class of tree data structures invented by computer scientist Ted Nelson and used in Project Xanadu "Green" designs of the 1970s and 1980s. Enfilades allow quick editing, versioning, re
Palindrome tree
In computer science a palindrome tree, also called an EerTree, is a type of search tree, that allows for fast access to all palindromes contained in a string. They can be used to solve the longest pal
K-D-B-tree
In computer science, a K-D-B-tree (k-dimensional B-tree) is a tree data structure for subdividing a k-dimensional search space. The aim of the K-D-B-tree is to provide the search efficiency of a balan
Range query tree
In computer science, a Range Query Tree, or RQT, is a term for referring to a data structure that is used for performing range queries and updates on an underlying array, which is treated as the leave
Lattice model (finance)
In finance, a lattice model is a technique applied to the valuation of derivatives, where a discrete time model is required. For equity options, a typical example would be pricing an American option,
Figurative system of human knowledge
The "figurative system of human knowledge", sometimes known as the tree of Diderot and d'Alembert, was a tree developed to represent the structure of knowledge itself, produced for the Encyclopédie by
Vantage-point tree
A vantage-point tree (or VP tree) is a metric tree that segregates data in a metric space by choosing a position in the space (the "vantage point") and partitioning the data points into two parts: tho
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
Hyperbolic tree
A hyperbolic tree (often shortened as hypertree) is an information visualization and graph drawing method inspired by hyperbolic geometry. Displaying hierarchical data as a tree suffers from visual cl
Tree traversal
In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each no
Fractal tree index
In computer science, a fractal tree index is a tree data structure that keeps data sorted and allows searches and sequential access in the same time as a B-tree but with insertions and deletions that
Finger tree
In computer science, a finger tree is a purely functional data structure that can be used to efficiently implement other functional data structures. A finger tree gives amortized constant time access
Semantic resolution tree
A semantic resolution tree is a tree used for the definition of the semantics of a programming language. They have often been used as a theoretical tool for showing the unsatisfiability of clauses in
Self-balancing binary search tree
In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of a
M-tree
In computer science, 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-nearest
Newick format
In mathematics, Newick tree format (or Newick notation or New Hampshire tree format) is a way of representing graph-theoretical trees with edge lengths using parentheses and commas. It was adopted by
Tree network
A tree topology, or star-bus topology, is a hybrid network topology in which star networks are interconnected via bus networks. Tree networks are hierarchical, and each node can have an arbitrary numb
Anatree
An anatree is a data structure designed to solve anagrams. Solving an anagram is the problem of finding a word from a given list of letters. These problems are commonly encountered in word games like
Merkle tree
In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" (node) is labelled with the cryptographic hash of a data block, and every node that is not a leaf (call
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. It is a refinement of the Navigating Net data stru
Trinomial tree
The trinomial tree is a lattice-based computational model used in financial mathematics to price options. It was developed by Phelim Boyle in 1986. It is an extension of the binomial options pricing m
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 (that is, every internal node has e
Dialogue tree
A dialogue tree, or conversation tree, is a gameplay mechanic that is used throughout many adventure games (including action-adventure games) and role-playing video games. When interacting with a non-
Trace tree
A trace tree is a data structure that is used in the runtime compilation of programming code. Trace trees are used in tracing just-in-time compilation where tracing is used during code execution to lo
Split (phylogenetics)
A split in phylogenetics is a bipartition of a set of taxa, and the smallest unit of information in unrooted phylogenetic trees: each edge of an unrooted phylogenetic tree represents one split, and th
Suffix tree
In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the te
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional sp
Tree rearrangement
Tree rearrangements are deterministic algorithms devoted to searching for an optimal tree structure. They can be applied to any set of data that are naturally arranged into a tree, but have most appli
A maximum clade credibility tree is a tree that summarises the results of a Bayesian phylogenetic inference. Whereas a majority-rule tree combines the most common clades, and usually yields a tree tha
Cardinal tree
A cardinal tree (or trie) of degree k, by analogy with cardinal numbers and by opposition with ordinal trees, is a rooted tree in which each node has k positions for an edge to a child. Each node has
Korn–Kreer–Lenssen model
The Korn–Kreer–Lenssen model (KKL model) is a discrete trinomial model proposed in 1998 by Ralf Korn, Markus Kreer and Mark Lenssen to model illiquid securities and to value financial derivatives on t
Segment tree
In computer science, a segment tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments
Leaf node
No description available.
A radial tree, or radial map, is a method of displaying a tree structure (e.g., a tree data structure) in a way that expands outwards, radially. It is one of many ways to visually display a tree, with
Tree (automata theory)
In automata theory, a tree is a particular way of representing a tree structure as sequences of natural numbers. For example, each node of the tree is a word over set of natural numbers, which helps t
Expectiminimax
The expectiminimax algorithm is a variation of the minimax algorithm, for use in artificial intelligence systems that play two-player zero-sum games, such as backgammon, in which the outcome depends o
BK-tree
A BK-tree is a metric tree suggested by Walter Austin Burkhard and specifically adapted to discrete metric spaces.For simplicity, consider integer discrete metric . Then, BK-tree is defined in the fol
Parse tree
A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term
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-
M-ary tree
In graph theory, an m-ary tree (also known as n-ary, k-ary or k-way tree) is a rooted tree in which each node has no more than m children. A binary tree is the special case where m = 2, and a ternary
Suffix tree clustering
Suffix Tree Clustering, often abbreviated as STC is an approach for clustering that uses suffix trees. A suffix tree cluster keeps track of all n-grams of any given length to be inserted into a set wo
Log-structured merge-tree
In computer science, the log-structured merge-tree (also known as LSM tree, or LSMT) is a data structure with performance characteristics that make it attractive for providing indexed access to files
Priority search tree
In computer science, a priority search tree is a tree data structure for storing points in two dimensions. It was originally introduced by Edward M. McCreight. It is effectively an extension of the pr
Tree structure
A tree structure, tree diagram, or tree model is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic resembles a tree,
Hash calendar
A hash calendar is a data structure that is used to measure the passage of time by adding hash values to an append-only database with one hash value per elapsed second. It can be thought of special ki
Sentinel value
In computer programming, a sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data) is a special value in the context of an algorithm which uses its pres
Tree (data structure)
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (de
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 dimens
Generalized suffix tree
In computer science, a generalized suffix tree is a suffix tree for a set of strings. Given the set of strings of total length , it is a Patricia tree containing all suffixes of the strings. It is mos
Dendrogram
A dendrogram is a diagram representing a tree. This diagrammatic representation is frequently used in different contexts: * in hierarchical clustering, it illustrates the arrangement of the clusters
Iacono's working set structure
In computer science, Iacono's working set structure is a comparison based dictionary. It supports insertion, deletion and access operation to maintain a dynamic set of elements. The working set of an
Trie
In computer science, a trie, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often