Part V · Trees, Priority Structures and Range Queries
26. Self-Balancing Search Trees and B-Trees
6 lessons•34 topics•Intermediate / Advanced
6 of 6 lessons published
26.014 animated
AVL trees
- Balance factor
- LL/RR/LR/RL rotations
- Insertion rebalancing
- Deletion rebalancing
- Height bound
26.025 animated
Red-black trees
- Node colors
- Black-height
- Rotations
- Insert fix-up
- Delete fix-up
- Properties
- TreeMap internals
26.032 animated
Other balanced BSTs
- 2-3 trees
- 2-3-4 trees
- AA trees
- Scapegoat trees
- Weight-balanced trees
26.046 animated
B-trees and storage indexes
- B-tree nodes
- Degree
- Split/merge
- Search
- Insert
- Delete
- External memory motivation
26.053 animated
B+ trees
- Internal vs leaf nodes
- Leaf chaining
- Range scans
- Index pages
- B+ tree vs B-tree
26.061 animated
Tree implementations
- Sentinel nodes
- Parent pointers
- Rotations
- Height/size augmentation
- Comparator correctness