Self-balancing binary search tree
A self-balancing binary search tree automatically maintains bounded, typically logarithmic height as elements are inserted or removed.
Advanced Algorithms and Data Structures
A balanced tree is a tree data structure whose height is maintained within a logarithmic bound relative to the number of stored elements.
- How it is used
- Supports dynamically changing ordered collections requiring search, updates, extrema, predecessor, successor, or sorted traversal.
- How deep it goes
- Explains path-based BST operations, logarithmic height, balancing families, invariants, rotations, and trade-offs without full implementation algorithms.
- Examples
- Uses insertion-order layouts, city-and-warehouse coordinates, 2-3 splitting, red-black links, and treap rotations as concrete illustrations.
- What you can do after
- Evaluate/understand when ordered-tree operations justify logarithmic balancing instead of hash-table or array implementations.
Read how Advanced Algorithms and Data Structures explains self-balancing binary search tree →
Clojure: The Essential Reference
A self-balancing tree is a search tree that maintains bounded height through structural adjustments as elements are inserted or removed.
- How it is used
- Uses balanced trees to implement persistent vectors with efficient updates and structural sharing.
- How deep it goes
- Explains branching, path copying, shallow height, and asymptotic behavior, but does not describe binary-search ordering or rebalancing algorithms.
- Examples
- Illustrates persistent vectors with vector literals, assoc updates, a Pride and Prejudice tree figure, and billion-element depth estimates.
- What you can do after
- Evaluate how balanced-tree branching and path copying make persistent-vector updates efficient.
Read how Clojure: The Essential Reference explains self-balancing binary search tree →
Grokking Data Structures
A balanced binary search tree is a binary search tree whose height is constrained to remain logarithmic in the number of elements.
- How it is used
- Provides an ordered container with predictable performance for searching, insertion, deletion, and related operations.
- How deep it goes
- Defines height balance and logarithmic operation bounds, but defers the detailed mechanics of balancing implementations.
- Examples
- Names randomized heaps, red–black trees, and 2–3 trees as balancing approaches.
- What you can do after
- Evaluate ordered-data structures using logarithmic bounds and operation-wide performance tradeoffs.
Read how Grokking Data Structures explains self-balancing binary search tree →
Related concepts
- binary search treekind of · A binary search tree is a binary tree whose nodes follow an ordering relation placing keys in designated left and right subtrees relative to each node.
- AVL treeincludes · An AVL tree is a self-balancing binary search tree that maintains bounded differences between subtree heights through rotations.
- k-d treecontrasts with · A k-d tree is a binary space-partitioning tree that organizes points in multidimensional space by recursively comparing coordinate dimensions.
- OrderedDictused by · OrderedDict is a Python dictionary subclass that preserves insertion order and provides operations for explicitly rearranging entries.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.