Skip to content

4. Tree and Indexed Search

Tree-based and indexed search: BST, self-balancing trees, tries, suffix structures, segment and range trees, and spatial trees.

algorithms searching trees data-structures
indexslugname
81binary-search-tree-searchBinary Search Tree Search
82avl-tree-searchAVL Tree Search
83red-black-tree-searchRed Black Tree Search
84treap-searchTreap Search
85randomized-bst-searchRandomized BST Search
86splay-tree-searchSplay Tree Search
87scapegoat-tree-searchScapegoat Tree Search
88weight-balanced-tree-searchWeight Balanced Tree Search
89b-tree-searchB Tree Search
90b-plus-tree-searchB Plus Tree Search
91b-star-tree-searchB Star Tree Search
92van-emde-boas-searchVan Emde Boas Search
93x-fast-trie-searchX Fast Trie Search
94y-fast-trie-searchY Fast Trie Search
95trie-searchTrie Search
96compressed-trie-searchCompressed Trie Search
97radix-tree-searchRadix Tree Search
98patricia-trie-searchPatricia Trie Search
99ternary-search-tree-searchTernary Search Tree Search
100suffix-tree-searchSuffix Tree Search
101suffix-array-binary-searchSuffix Array Binary Search
102lcp-accelerated-suffix-searchLCP Accelerated Suffix Search
103segment-tree-searchSegment Tree Search
104fenwick-tree-lower-boundFenwick Tree Lower Bound
105wavelet-tree-rank-searchWavelet Tree Rank Search
106wavelet-tree-select-searchWavelet Tree Select Search
107interval-tree-searchInterval Tree Search
108range-tree-searchRange Tree Search
109kd-tree-searchKD Tree Search
110ball-tree-searchBall Tree Search
111vp-tree-searchVantage Point Tree Search
112cover-tree-searchCover Tree Search
113r-tree-searchR Tree Search
114quadtree-searchQuadtree Search
115octree-searchOctree Search
AVL Tree SearchSearch in a height balanced binary search tree with guaranteed logarithmic depth.
2 min
Red Black Tree SearchSearch in a balanced binary search tree with relaxed balancing using color properties.
2 min
Treap SearchSearch in a randomized binary search tree that also maintains heap order over priorities.
3 min
Randomized BST SearchSearch in a binary search tree maintained with randomization to achieve expected logarithmic height.
2 min
Splay Tree SearchSearch in a self-adjusting binary search tree that moves accessed nodes toward the root.
5 min
Scapegoat Tree SearchSearch in a weight balanced binary search tree that rebuilds subtrees to preserve logarithmic height.
2 min
Weight Balanced Tree SearchSearch in a binary search tree that keeps subtree sizes balanced to guarantee logarithmic height.
3 min
B Tree SearchSearch for a key in a multiway balanced search tree optimized for block based storage.
3 min
B+ Tree SearchSearch in a B+ tree where all records are stored in leaves and internal nodes guide traversal.
3 min
B* Tree SearchSearch in a B* tree, a B tree variant that keeps nodes denser by redistributing entries before splitting.
3 min
Van Emde Boas SearchSearch for an integer key in a van Emde Boas tree using recursive universe decomposition.
4 min
X Fast Trie SearchSearch for an integer key in an X fast trie using hashed prefixes over a binary trie.
4 min
Y Fast Trie SearchSearch for an integer key using a Y fast trie, combining hashing with balanced trees for linear space.
3 min
Trie SearchSearch for a string key in a prefix tree by following character transitions.
3 min
Compressed Trie SearchSearch for a string key in a trie whose unary paths are compressed into edge labels.
3 min
Radix Tree SearchSearch for a string or byte key in a radix tree using variable length edge labels.
3 min
Patricia Trie SearchSearch for a key in a Patricia trie using bitwise branching with path compression.
3 min
Ternary Search Tree SearchSearch for a string key in a ternary search tree using character comparisons and three-way branching.
3 min
Suffix Tree SearchSearch for a pattern in a text using a suffix tree in time proportional to the pattern length.
3 min
Suffix Array Binary SearchSearch for a pattern in a text by binary searching the lexicographically sorted suffix array.
4 min
LCP Accelerated Suffix SearchSearch for a pattern in a suffix array using LCP information to reduce redundant character comparisons.
3 min
Suffix Array Doubling SortBuild a suffix array using the prefix doubling technique with iterative ranking.
4 min
SA-IS Suffix ArrayLinear time suffix array construction using induced sorting of LMS substrings.
3 min
DC3 Suffix ArrayLinear time suffix array construction using the DC3 divide and conquer strategy.
3 min
DC7 Suffix ArrayGeneralized divide and conquer suffix array construction using modulo 7 partitioning.
3 min
Interval Tree SearchSearch for all intervals that overlap a query interval using a balanced interval tree.
3 min
Range Tree SearchSearch for all points within a multidimensional range using layered balanced search trees.
3 min
k-d Tree SearchSearch for nearest or range points in k-dimensional space using recursive axis splitting.
3 min
Ball Tree SearchSearch for nearest neighbors in metric space using hierarchical clustering with hyperspheres.
3 min
VP Tree SearchNearest neighbor search in metric space using vantage point partitioning.
4 min
Cover Tree SearchNearest neighbor search in metric space using hierarchical covers with exponential scale separation.
3 min
R Tree SearchSearch for spatial objects using hierarchical minimum bounding rectangles.
3 min
Quadtree SearchSearch for points or regions in 2D space using recursive quadrant decomposition.
3 min
Octree SearchSearch for points or regions in 3D space using recursive octant decomposition.
4 min
BST SearchSearch for a key in a binary search tree by exploiting ordering between nodes.
2 min