Trees

A hierarchical structure where every node has at most two children, the foundation of BSTs, heaps and expression trees.

A binary tree where every left descendant is smaller and every right descendant is larger, giving O(h) ordered search, insert and delete.

A self-balancing BST that keeps every node's subtree heights within 1 of each other using rotations, guaranteeing O(log n) operations.

A self-balancing BST that colors nodes red or black and enforces color rules so that no path is more than twice as long as any other.

A rooted tree in which each node can have any number of children, stored as a child list, and traversed with the same DFS/BFS ideas as binary trees.

A tree keyed by characters where each root-to-node path spells a prefix, giving O(L) insert, lookup and prefix search independent of how many words are stored.

A binary tree over array intervals that answers range queries (sum, min, max, gcd) and point or range updates in O(log n).

A compact array-based tree that supports prefix-sum queries and point updates in O(log n) using the binary representation of indices.

A balanced BST of intervals keyed by start, augmented with the maximum end in each subtree, to find all intervals overlapping a point or range in O(log n + k).

A balanced multiway search tree with wide nodes holding many keys, designed to minimize disk or cache-line reads for very large ordered data.

A B-tree variant that stores all records in linked leaf nodes and uses internal nodes only as a routing index, giving fast point lookups and sequential range scans.