Tree and list structures built to find, insert and remove keys quickly, such as the AVL tree, red-black tree, splay tree, B-tree, treap, skip list and van Emde Boas tree. An entry belongs here when its cited article describes a search tree, a self-balancing tree or a structure for storing keys for lookup. It excludes hash tables and filters, which sit in the hashing group. A member is placed here by what its own cited article states about it, not by the name of the algorithm or by the uses it is put to today, so each entry sits in the group its source describes it as belonging to.
Browse By
Search Trees and Dictionary Structures
Filter Results9 entries
Sources
Queap (Wikipedia)
Wikipedia: AVL tree
Wikimedia FoundationHas Member: AVL Tree Rotation Algorithm, Lead sectionQuote, Has Member: AVL Tree Rotation Algorithm, Lead section
is a self-balancing binary search tree
Wikipedia: Red-black tree
Wikimedia FoundationHas Member: Red-Black Tree Algorithm, Lead sectionQuote, Has Member: Red-Black Tree Algorithm, Lead section
is a self-balancing binary search tree data structure
NIST Dictionary of Algorithms and Data Structures: B+-tree
NIST Dictionary of Algorithms and Data StructuresHas Member: B+ Tree Algorithm, DefinitionQuote, Has Member: B+ Tree Algorithm, Definition
A B-tree in which keys are stored in the leaves
NIST Dictionary of Algorithms and Data Structures: splay tree
NIST Dictionary of Algorithms and Data StructuresHas Member: Splay Tree Algorithm, DefinitionQuote, Has Member: Splay Tree Algorithm, Definition
A binary search tree in which operations that access nodes restructure the tree.
NIST Dictionary of Algorithms and Data Structures: skip list
NIST Dictionary of Algorithms and Data StructuresHas Member: Skip List Algorithm, DefinitionQuote, Has Member: Skip List Algorithm, Definition
A randomized variant of an ordered linked list with additional, parallel lists.
NIST Dictionary of Algorithms and Data Structures: treap
NIST Dictionary of Algorithms and Data StructuresHas Member: Treap Algorithm, DefinitionQuote, Has Member: Treap Algorithm, Definition
A binary search tree in which nodes have another key
NIST Dictionary of Algorithms and Data Structures: ternary search tree
NIST Dictionary of Algorithms and Data StructuresHas Member: Ternary Search Tree Algorithm, DefinitionQuote, Has Member: Ternary Search Tree Algorithm, Definition
A 3-way tree where every node's left subtree has keys less than the node's key, every middle subtree has keys equal to the node's key, and every right subtree has keys greater than the node's key.
NIST Dictionary of Algorithms and Data Structures: B-tree
NIST Dictionary of Algorithms and Data StructuresHas Member: B-Tree Algorithm, DefinitionQuote, Has Member: B-Tree Algorithm, Definition
A balanced search tree in which every node has between ⌈ m/2⌉ and m children , where m>1 is a fixed integer.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.