Trees & Range Data Structures

A binary tree where each node's key is greater than all keys in its left subtree and less than all keys in its right subtree. An in-order traversal yields keys in sorted order.

Search, insert, and delete each run in O(h) time, where h is the tree height. For a balanced BST h = Θ(log n); for a degenerate (chain) BST h = Θ(n).

Replace the node's key with its in-order successor (smallest key in the right subtree) or in-order predecessor (largest in the left subtree), then delete that successor/predecessor, which has at most one child.

Plain BSTs can degenerate into a linked list (height Θ(n)) on adversarial or sorted insertions, making operations O(n). Balanced BSTs enforce height Θ(log n), guaranteeing O(log n) operations.

For every node, the heights of its two child subtrees differ by at most 1 (balance factor in {-1, 0, +1}). This keeps height ≤ ~1.44 log n, guaranteeing O(log n) search, insert, and delete. Rebalancing uses rotations.

Nodes are colored red or black; the root and null leaves are black; red nodes have black children; every root-to-leaf path has the same number of black nodes. These rules bound the height at ≤ 2 log(n+1), giving O(log n) operations with fewer rotations than AVL.