Trees

Hierarchies and the search trees built on them: traversals and expression trees, threaded trees, binary search trees, the balanced families (AVL, red-black, splay, B-trees), heaps, augmented trees and the range-query trees used in competitive and production code.

This part builds on Searching and sorting.

4 of 11 topics ready, listed in reading order

Trees and traversalsTerminology, representations, preorder, inorder, postorder and level order, expression trees, and rebuilding a tree from its traversals.Planned

Threaded binary treesThreads that replace null links, inorder traversal without a stack, and Morris traversal.Planned

Binary search treesSearch, insertion, the three cases of deletion, successors and predecessors, and how insertion order decides the height.Planned

AVL treesBalance factors, the four rotations, and insertion and deletion traced rotation by rotation.ReadyRed-black treesThe five properties, insertion and deletion fix-ups case by case, and the link to 2-3-4 trees.Ready

Splay treesZig, zig-zig and zig-zag steps, splaying on access, and the amortized logarithmic bound.Planned

B-trees and B+ treesMultiway search trees, B-tree insertion with splits and deletion with merges, B+ trees and range scans, and why disks want wide nodes.ReadyHeaps and priority queuesBinary heaps, sifting up and down, building a heap in linear time, heapsort, d-ary heaps and decrease-key.Ready

Augmented treesOrder-statistic trees and interval trees, and the rule for augmenting a balanced tree safely.Planned

Segment trees and Fenwick treesPrefix sums, range queries with point and range updates, and lazy propagation.Planned

Treaps and skip listsBalance by randomness: treap rotations, skip list levels and their expected costs.Planned