4. Tree and Indexed Search

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

35 items

4. Tree and indexed search, 35

index slug name
81 binary-search-tree-search Binary Search Tree Search
82 avl-tree-search AVL Tree Search
83 red-black-tree-search Red Black Tree Search
84 treap-search Treap Search
85 randomized-bst-search Randomized BST Search
86 splay-tree-search Splay Tree Search
87 scapegoat-tree-search Scapegoat Tree Search
88 weight-balanced-tree-search Weight Balanced Tree Search
89 b-tree-search B Tree Search
90 b-plus-tree-search B Plus Tree Search
91 b-star-tree-search B Star Tree Search
92 van-emde-boas-search Van Emde Boas Search
93 x-fast-trie-search X Fast Trie Search
94 y-fast-trie-search Y Fast Trie Search
95 trie-search Trie Search
96 compressed-trie-search Compressed Trie Search
97 radix-tree-search Radix Tree Search
98 patricia-trie-search Patricia Trie Search
99 ternary-search-tree-search Ternary Search Tree Search
100 suffix-tree-search Suffix Tree Search
101 suffix-array-binary-search Suffix Array Binary Search
102 lcp-accelerated-suffix-search LCP Accelerated Suffix Search
103 segment-tree-search Segment Tree Search
104 fenwick-tree-lower-bound Fenwick Tree Lower Bound
105 wavelet-tree-rank-search Wavelet Tree Rank Search
106 wavelet-tree-select-search Wavelet Tree Select Search
107 interval-tree-search Interval Tree Search
108 range-tree-search Range Tree Search
109 kd-tree-search KD Tree Search
110 ball-tree-search Ball Tree Search
111 vp-tree-search Vantage Point Tree Search
112 cover-tree-search Cover Tree Search
113 r-tree-search R Tree Search
114 quadtree-search Quadtree Search
115 octree-search Octree Search
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

BST Search

Search for a key in a binary search tree by exploiting ordering between nodes.
algorithms searching bst trees
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

AVL Tree Search

Search in a height balanced binary search tree with guaranteed logarithmic depth.
algorithms searching avl-tree balanced-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Red Black Tree Search

Search in a balanced binary search tree with relaxed balancing using color properties.
algorithms searching red-black-tree balanced-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Treap Search

Search in a randomized binary search tree that also maintains heap order over priorities.
algorithms searching treap randomized-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Randomized BST Search

Search in a binary search tree maintained with randomization to achieve expected logarithmic height.
algorithms searching randomized-bst trees
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Splay Tree Search

Search in a self-adjusting binary search tree that moves accessed nodes toward the root.
algorithms searching splay-tree self-adjusting-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Scapegoat Tree Search

Search in a weight balanced binary search tree that rebuilds subtrees to preserve logarithmic height.
algorithms searching scapegoat-tree balanced-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Weight Balanced Tree Search

Search in a binary search tree that keeps subtree sizes balanced to guarantee logarithmic height.
algorithms searching weight-balanced-tree balanced-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

B Tree Search

Search for a key in a multiway balanced search tree optimized for block based storage.
algorithms searching b-tree multiway-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

B+ Tree Search

Search in a B+ tree where all records are stored in leaves and internal nodes guide traversal.
algorithms searching b-plus-tree database-index
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

B* Tree Search

Search in a B* tree, a B tree variant that keeps nodes denser by redistributing entries before splitting.
algorithms searching b-star-tree multiway-tree
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Van Emde Boas Search

Search for an integer key in a van Emde Boas tree using recursive universe decomposition.
algorithms searching van-emde-boas-tree integer-set
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

X Fast Trie Search

Search for an integer key in an X fast trie using hashed prefixes over a binary trie.
algorithms searching x-fast-trie integer-set
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Y Fast Trie Search

Search for an integer key using a Y fast trie, combining hashing with balanced trees for linear space.
algorithms searching y-fast-trie integer-set
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Trie Search

Search for a string key in a prefix tree by following character transitions.
algorithms searching trie string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Compressed Trie Search

Search for a string key in a trie whose unary paths are compressed into edge labels.
algorithms searching compressed-trie string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Radix Tree Search

Search for a string or byte key in a radix tree using variable length edge labels.
algorithms searching radix-tree string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Patricia Trie Search

Search for a key in a Patricia trie using bitwise branching with path compression.
algorithms searching patricia-trie bitwise-trie
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Ternary Search Tree Search

Search for a string key in a ternary search tree using character comparisons and three-way branching.
algorithms searching ternary-search-tree string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Suffix Tree Search

Search for a pattern in a text using a suffix tree in time proportional to the pattern length.
algorithms searching suffix-tree string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Suffix Array Binary Search

Search for a pattern in a text by binary searching the lexicographically sorted suffix array.
algorithms searching suffix-array string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

LCP Accelerated Suffix Search

Search for a pattern in a suffix array using LCP information to reduce redundant character comparisons.
algorithms searching suffix-array lcp-array string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Suffix Array Doubling Sort

Build a suffix array using the prefix doubling technique with iterative ranking.
algorithms sorting suffix-array string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

SA-IS Suffix Array

Linear time suffix array construction using induced sorting of LMS substrings.
algorithms sorting suffix-array sa-is string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

DC3 Suffix Array

Linear time suffix array construction using the DC3 divide and conquer strategy.
algorithms sorting suffix-array dc3 string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

DC7 Suffix Array

Generalized divide and conquer suffix array construction using modulo 7 partitioning.
algorithms sorting suffix-array dc7 string
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Interval Tree Search

Search for all intervals that overlap a query interval using a balanced interval tree.
algorithms searching interval-tree range-query
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Range Tree Search

Search for all points within a multidimensional range using layered balanced search trees.
algorithms searching range-tree geometry
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

k-d Tree Search

Search for nearest or range points in k-dimensional space using recursive axis splitting.
algorithms searching kd-tree geometry
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Ball Tree Search

Search for nearest neighbors in metric space using hierarchical clustering with hyperspheres.
algorithms searching ball-tree nearest-neighbor
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

VP Tree Search

Nearest neighbor search in metric space using vantage point partitioning.
algorithms searching vp-tree nearest-neighbor
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Cover Tree Search

Nearest neighbor search in metric space using hierarchical covers with exponential scale separation.
algorithms searching cover-tree nearest-neighbor
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

R Tree Search

Search for spatial objects using hierarchical minimum bounding rectangles.
algorithms searching r-tree spatial-index
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Quadtree Search

Search for points or regions in 2D space using recursive quadrant decomposition.
algorithms searching quadtree spatial-index
Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Octree Search

Search for points or regions in 3D space using recursive octant decomposition.
algorithms searching octree spatial-index 3d