- Graph theory
- >
- Graphs
- >
- Application-specific graphs
- >
- Trees (data structures)

- Graphs
- >
- Graph families
- >
- Trees (graph theory)
- >
- Trees (data structures)

- Set theory
- >
- Trees (set theory)
- >
- Trees (graph theory)
- >
- Trees (data structures)

- Topology
- >
- Trees (topology)
- >
- Trees (graph theory)
- >
- 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

Adaptive k-d tree

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

Linked data structure

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

Link/cut tree

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 ,

Radix tree

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

Enfilade (Xanadu)

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

Quadtree

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

Maximum clade credibility tree

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.

Radial tree

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

© 2023 Useful Links.