Red-Black trees are used in most standard library implementations (Java TreeMap, C++ std::map) because they require fewer rotations during insertion. While AVL trees guarantee stricter balance and slightly faster search, map implementations do many more insertions than pure lookups. Red-Black trees accept marginally worse balance in exchange for cheaper modifications. This trade-off makes RB trees the pragmatic choice for associative containers.

The black-height property ensures all paths from a node to NIL leaves have the same number of black nodes. Combined with the red constraint (no consecutive reds), this bounds the maximum path length. The longest possible path is alternating red-black (2 × black_height), and the shortest is all black (black_height). Since all paths share the same black_height, the longest can't exceed twice the shortest—guaranteeing O(log n) height.

Making the root black is a design choice that simplifies the properties. If we allowed red roots, we'd need to track an additional constraint in our black-height calculations. By fixing the root as black, the black-height property becomes easier to verify and maintain. It also ensures empty trees and single-node trees satisfy all properties without special cases.

Deletion is significantly more complex. While insertion has at most 2 rotations, deletion can require O(log n) rotations because fixing a double-black violation at one node may create the same violation at its parent. Deletion uses a "double-black" concept to track the underflow. The fixup cases are more numerous: there are 8 cases for deletion (4 symmetric pairs) versus 3 cases for insertion.

The five properties are:

• Node color (red or black): The fundamental mechanism for tracking balance without storing height
• Root is black: Simplifies the black-height invariant — without this, single-node trees need special handling
• Leaves (NIL) are black: Gives every path a guaranteed black baseline; prevents edge cases where a leaf is red and creates spurious red-red violations
• No consecutive reds: Limits the skew — a path can't have more reds than blacks, so no path can be more than twice as long as any other
• Equal black-height: Every path from root to NIL has the same number of black nodes. Combined with property 4, this bounds the height to O(log n)

Properties 4 and 5 together are the key: property 5 guarantees all paths have equal black nodes, property 4 ensures no path has extra reds. The worst-case path is red-black-red-black... (2x black-height), the best-case is all black (1x black-height), so the ratio is at most 2.

The three cases handle a red-red violation after inserting a red node z:

• Case 1 (Uncle is RED): Flip z.parent, uncle, and z.grandparent colors. Then move z up two levels to the grandparent and recheck. This is a pure color-only operation — no rotations needed.
• Case 2 (Uncle is BLACK, z is a right child): Rotate z.parent left, turning this into Case 3. This doesn't fix anything alone — it just restructures so Case 3 can work.
• Case 3 (Uncle is BLACK, z is a left child): Rotate z.grandparent right and recolor. This fully resolves the violation and terminates.

Key insight: Case 1 can propagate upward (O(log n) times). Cases 2 and 3 fix the violation in at most 2 rotations total. On the mirror side (parent is right child), the cases are symmetric (left ↔ right swapped).

The bound comes from how the fixup cases interact:

• Case 1 (red uncle) does color flips only — no rotations. It moves the violation up two levels but doesn't introduce rotations.
• Case 2 (black uncle, right child) does exactly one rotation to transform into Case 3, then Case 3 does exactly one more rotation.
• Case 3 (black uncle, left child) does exactly one rotation and terminates the fixup.

Therefore, the worst case is Case 1 propagating all the way up (only color flips), followed by one Case 2 + one Case 3 at the top = 2 rotations. Since Case 3 always terminates, you can never get more than 2 rotations per insertion regardless of tree size.

Under real workloads:

• Insert-heavy workloads (e.g., building a map from scratch): RB trees outperform AVL because most fixups are color flips (Case 1), not rotations. Color flips are O(1) pointerless operations.
• Read-heavy workloads (e.g., symbol table lookups): AVL trees have slightly better search performance due to stricter balance (~1.44 log n vs ~2 log n height bound).
• Mixed workloads: RB trees offer the best worst-case guarantee. The 2-rotation bound means insertion latency is more predictable than AVL (which also has ≤1 rotation but more fixup cases on the color side).
• Memory overhead: RB trees need 1 bit for color (usually stored in a low bit of a pointer), while AVL needs a small integer for balance factor. In practice, both fit in the same memory alignment padding.

Production systems (Linux kernel CFS scheduler, Java TreeMap, C++ std::map) choose RB trees because the amortized cost of modifications is lower and the implementation, while involved, is well-understood and battle-tested.

Every red-black tree is a binary encoding of a 2-3-4 tree (also called a B-tree of order 4):

• 2-node: A black node with no red children maps directly to a 2-node in the 2-3-4 tree
• 3-node: A black node with one red left child represents a 3-node — the red child is "absorbed" into the parent
• 4-node: A black node with two red children represents a 4-node — both children absorb into the parent

Under this mapping, the five RB properties become natural invariants of the 2-3-4 tree. Case 1 (red uncle) corresponds to a node overflow in the 2-3-4 tree — we flip colors to push the overflow up. Case 2 and 3 (black uncle) correspond to restructuring operations. Understanding this makes the fixup cases feel like mechanical consequences of tree invariants rather than arbitrary branches in an algorithm.

The NIL sentinel is a dedicated node (usually black) used instead of null pointers. This eliminates special-case null checks throughout the code:

• Every child pointer is guaranteed to point to a valid node, so `node.left.color` is always a valid memory access
• Black-height calculations treat the sentinel as a black leaf — no null-to-zero conversion needed
• Leaf nodes can store data (unlike in naive BST implementations where external leaves are null)

Trade-offs: the sentinel consumes a small amount of memory (one node), and in garbage-collected languages it must be carefully managed to avoid being collected as unreachable garbage. The bigger implementation risk is mixing sentinel checks with null checks — using `if node:` instead of `if node == self.NIL:` causes subtle logic errors that are hard to debug.

Deletion has two phases:

• Phase 1: Standard BST deletion — Find the node, replace it with its in-order successor or predecessor if it has two children, or physically remove it if it has one or zero children
• Phase 2: Fixup — If the deleted node was black, the black-height property is violated. We track a "double-black" token representing the missing black height

The fixup cases handle the double-black node X:

• Case 1 (Sibling is red): Recolor sibling black, parent red, rotate parent toward X. This transforms the tree to make sibling black, which is the prerequisite for Cases 2, 3, 4
• Case 2 (Sibling is black, both nephews black): Recolor sibling red, move double-black up to parent
• Case 3 (Sibling is black, near nephew is red): Recolor sibling to parent's color, parent and far nephew to black, rotate parent away from X
• Case 4 (Sibling is black, far nephew is red): Recolor sibling to red, parent to black, rotate parent toward X — this terminates the fixup

The key insight is that Cases 2, 3, 4 each remove one layer of double-black, so fixup is O(log n). Cases 1-4 each have mirror variants for the left/right symmetry, giving 8 total deletion cases.

Range queries on a BST leverage the in-order traversal property:

• Time complexity: O(log n + m) where m is the number of keys in the range [k1, k2]
• Space complexity: O(h) = O(log n) for the recursion stack

Algorithm:

1. Navigate to k1 starting from root, following BST left/right decisions. When you find k1 (or the node where k1 would be), begin in-order traversal
2. During in-order traversal, collect nodes whose keys are ≤ k2. When you encounter a node with key > k2, terminate
3. The accumulated sequence is the sorted range in ascending order

For a balanced tree, the descent to k1 takes O(log n). The traversal visits exactly m nodes in range plus O(log n) nodes outside range but pruned during traversal. This is optimal — any comparison-based algorithm must examine every result.

Left-Leaning Red-Black Trees (Sedgewick, 2008) are a variant that maps 1:1 to 2-3 trees instead of 2-3-4 trees:

• Fewer cases to implement: 3 insertion cases (vs 6 in standard RB), 3 deletion cases (vs 8). This significantly reduces implementation complexity and bug surface area
• Simpler invariants: Red nodes must be left children only, eliminating half the symmetric cases
• Slightly different balance guarantees: LLRB maintains left-leaning property at the cost of a different height bound — still O(log n) but with a different constant

Choose LLRB when: you need a clean, well-documented implementation; you're building an educational tool; you want RB-like guarantees with fewer edge cases. Choose standard RB when: you're using a battle-tested library implementation (std::map, TreeMap); you need compatibility with existing code; you want the proven-in-production variant.

Standard Red-Black tree implementations typically treat duplicate keys as follows:

• Option 1 (Rejected): Most implementations reject duplicates as an error condition (like std::map). The BST invariant requires unique keys. An attempt to insert a duplicate calls the equivalent of an error handler
• Option 2 (Allow on right): Insert duplicates to the right of existing nodes. This preserves the BST property but means in-order traversal returns duplicates in insertion order. Fixup still applies — the new node is red and may cause red-red violations
• Option 3 (Counter field): Store a count field in each node for duplicates. Insertion increments count instead of creating a new node. This saves memory for duplicate-heavy workloads but requires changing the node structure

For interview purposes, the most correct answer is that duplicates are typically rejected in map/set implementations since they require unique keys. If the interviewer asks about handling, explain the trade-offs above. In any case, the fixup algorithm still works correctly with duplicates — the red-red violation rules apply regardless of key value relationships.

Proof of O(log n) height:

• Let bh(x) be the black-height of node x (number of black nodes from x to NIL, excluding x)
• By property 5, all paths from x to NIL have the same bh value
• By property 4 (no consecutive reds), any path from x to NIL has at most 2×bh(x) nodes (alternating red-black at maximum density)
• A subtree with black-height h has at least 2^h - 1 internal nodes (all-black path is the minimum case, equivalent to a perfectly balanced binary tree of height h)

For a tree with n internal nodes, the shortest path (all black) has length bh(root). The longest path has at most 2×bh(root) nodes. Since n ≥ 2^bh(root) - 1, we get bh(root) ≤ log₂(n+1). Therefore max height ≤ 2×log₂(n+1) = O(log n).

This proves the guarantee that search, insert, and delete all run in O(log n) worst-case time.

Add a subtree size field to each node (size[x] = number of nodes in subtree rooted at x, including x itself):

• Update on insert/delete: Increment size of all ancestors after structural changes. This is O(log n) overhead
• Update on rotation: Recalculate sizes of rotated nodes since child subtrees change. After rotation, sizes are: size[x] = size[x.left] + size[x.right] + 1
• Find k-th smallest: Starting at root, let leftSize = size(node.left). If k < leftSize, recurse left. If k == leftSize, return node. If k > leftSize, recurse right with k = k - leftSize - 1. This is O(log n)

The overhead is one integer field per node (~4 bytes in typical implementations) and O(log n) extra work per insertion/deletion to maintain the size fields. This is the same approach used by order-statistic trees (OST) and is compatible with Red-Black rebalancing since rotations properly recalculate sizes.

Red-Black trees and B-trees of order 4 are isomorphic representations — a 2-3-4 tree maps directly to a Red-Black tree. The difference is in storage model:

• Red-Black tree: Binary tree with color bits. Each node holds one key and two children. Pointer-heavy, good for in-memory structures
• B-tree of order 4: Multi-way tree with up to 3 keys and 4 children per node. Better cache locality (sequential key storage) and fewer pointer dereferences

Choose B-tree when: data is on disk or SSD (cache locality matters more than pointer overhead); you want to minimize I/O operations; you're building a database index. Choose Red-Black tree when: data is in memory; you need simple pointer-based traversal; you're implementing in-language collections (std::map, TreeMap).

The asymptotic complexity is identical — both guarantee O(log n) operations with different constants due to branching factor. The practical difference is memory layout and cache behavior.

Skip lists and Red-Black trees have the same average-case asymptotic complexity, but differ in practice:

• Implementation simplicity: Skip lists are significantly easier to implement correctly. No rotation cases, no color fixup, just random level assignment and merge operations
• Concurrent access: Skip lists have natural lock-free concurrent insert patterns (multiple threads can insert at different heights). Red-Black trees require careful locking or lock-free alternatives
• Cache locality: Red-Black trees have better cache locality — nodes are small and sequential in memory. Skip lists spread nodes across random memory locations
• Determinism: Red-Black trees are deterministic — same input always produces same tree. Skip lists depend on random level generation and may have different structure across runs

Redis uses skip lists for sorted sets (ZSET) because they combine ordered operations (like a BST) with easy concurrent access. Red-Black trees are used in Java TreeMap and C++ std::map because they provide deterministic worst-case guarantees and fit naturally into the pointer-based data structure paradigm of those languages.

When a black node is deleted, its black height contribution disappears from one path, creating a "double-black" deficit:

• Double-black token: This is not an actual node — it's a conceptual marker on a node's child pointer indicating "this subtree is missing one black node compared to its siblings"
• Transformed problem: The fixup tries to propagate this double-black upward until either it's absorbed (by a red node being recolored black) or the root is reached
• Root absorption: If double-black reaches the root, we simply drop the extra black — the root can be black twice over, effectively discarding the deficit

The four deletion fixup cases all aim to either (a) convert a double-black node into a single-black (Case 2 sibling-red to sibling-black transformation), (b) push the double-black upward (Case 2), or (c) resolve the double-black locally (Cases 3 and 4 through rotation and recoloring).

Persistent data structures return a new version after modification without modifying the old version. For Red-Black trees:

• Path copying: On insert/delete, only O(log n) nodes change. The path from root to the modified node must be recreated. Nodes not on this path are shared between old and new versions
• Node structure: No modification to node fields — just create new nodes for the modified path with the same color/size/children as originals
• Memory overhead: Each update creates O(log n) new nodes. For m updates, total memory is O(m log n). This is acceptable for occasional snapshots but expensive for high-frequency updates
• Rebalancing persistence: Rotations during fixup create new nodes for the rotation path. Color flips also create new nodes (since parent reference changes)

Alternatives: For write-heavy workloads, consider copy-on-write at the top level only (losing fine-grained persistence) or log-structured merge trees (LSM trees) which batch updates and provide snapshots through compaction. For read-heavy scenarios with occasional writes, persistent RB trees are elegant and practical.