17 articles
AVL tree
The AVL tree, or Adelson-Velskii Landis tree, is a self-balancing binary search tree, invented in 1962, in which search, insertion, and deletion take O(log n) time.
B-tree
A B-tree is a balanced, multiway search tree in which nodes hold many keys and children, invented by Bayer and McCreight at Boeing in 1970 and standard in database indexes.
B+ tree
A B+ tree, also written B plus tree, is a balanced tree data structure that keeps all records in linked leaf pages, serving as the standard database index.
Binary search tree
A binary search tree (BST) is a node-based data structure whose ordering lets a search discard half the tree at each step, like binary search in a sorted array.
Binary tree
A binary tree is a hierarchical data structure in which each node has at most two children, the left and right child. It underlies binary search trees, heaps, and balanced variants like red-black trees.
K-d tree
A k-d tree is a binary search tree that organizes points in a k-dimensional space, developed by Jon Louis Bentley in 1975 for associative searches.
Merkle tree
A Merkle tree, also called a Merkle hash tree, is a hash-based binary tree, introduced by Ralph Merkle in 1979, whose root hash tamper-evidently commits to a dataset.
Octree
An octree is a tree data structure in which each internal node has exactly eight children, recursively subdividing 3-D space into eight subcubes, or octants.
Quadtree
A quadtree, or quadtree decomposition, is a tree data structure in which each node has four children, one per quadrant, used for spatial indexing and image encoding.
R-tree
An R-tree is a balanced tree index for multi-dimensional spatial data, proposed by Antonin Guttman in 1984 and built into database systems including PostgreSQL and SQLite.
Red–black tree
A red–black tree, or symmetric binary B-tree, is a self-balancing binary search tree invented by Rudolf Bayer in 1972 and used in Java's TreeMap, C++ std::map, and the Linux kernel.
Search tree (computer science)
A search tree is a tree data structure in which each node holds a key, and key ordering directs efficient search, insertion, deletion, and range queries.
Self-balancing binary search tree
A self-balancing binary search tree, also called a balanced or height-balanced tree, uses rotations and balance rules such as those of AVL and red-black trees to keep operations logarithmic.
Splay tree
A splay tree, also called a self-adjusting binary search tree, is a search tree that splays each accessed node to the root, giving amortized O(log n) operations.
Tree (abstract data type)
A tree, or tree data structure, is an abstract data type of parent-child linked nodes with one root and no cycles, used for hierarchies like document models and syntax trees.
Tree structure
A tree structure is a hierarchical data organization in which every element except the root has exactly one parent, used in file systems and search indexes.
Trie
A trie, also called a prefix tree or digital tree, is a tree data structure for storing strings where each node represents a distinct prefix of the stored keys.