2. Advanced Data Structures and Operations
Augmented and self-balancing trees, range query structures, Fenwick and segment tree variants, union-find, tries, and order statistic structures.
Tag
Trees
10 notes
1.8 Basic Tree Traversals and Operations
General tree traversal patterns including DFS, BFS, level-order, zigzag, boundary traversal, LCA, serialization, and iterative approaches.
1.7 Binary Search Trees
BST operations, traversals, augmentation, interval trees, order statistics, persistence, and thread-safe BST designs.
2.1 Balanced Search Trees
AVL, red-black, splay, scapegoat, B-tree families, treaps, finger trees, persistent balanced trees, and cache-oblivious layouts.
4. Tree and Indexed Search
Tree-based and indexed search: BST, self-balancing trees, tries, suffix structures, segment and range trees, and spatial trees.
Finger Search
Search starting from a known nearby position, achieving time proportional to distance rather than full size.
Order Statistic Tree Rank
Compute the sorted-order rank of a key in a search tree augmented with subtree sizes.
Order Statistic Tree Select
Select the element with a given rank from a balanced search tree augmented with subtree sizes.
Binary Search Tree Search
Search for a key in a binary search tree by exploiting ordering between nodes.
Randomized BST Search
Search in a binary search tree maintained with randomization to achieve expected logarithmic height.