2.1 Balanced Search Trees
AVL, red-black, splay, scapegoat, B-tree families, treaps, finger trees, persistent balanced trees, and cache-oblivious layouts.
Tag
Balanced-Tree
5 notes
Weight Balanced Tree Search
Search in a binary search tree that keeps subtree sizes balanced to guarantee logarithmic height.
Scapegoat Tree Search
Search in a weight balanced binary search tree that rebuilds subtrees to preserve logarithmic height.
Red Black Tree Search
Search in a balanced binary search tree with relaxed balancing using color properties.
AVL Tree Search
Search in a height balanced binary search tree with guaranteed logarithmic depth.