Understanding Binary Trees, BSTs, AVL, 2‑3‑4, B‑Tree and Red‑Black Tree

A binary tree is an ordered tree where each node has at most two children, commonly called the left and right sub‑trees.

In a binary search tree (BST) every node’s left sub‑tree contains only smaller values and the right sub‑tree only larger or equal values, enabling efficient search, insertion and deletion.

When keys are inserted in sorted order, a BST can degenerate into a linked list (called a “left‑leaning” or “right‑leaning” tree), which harms performance.

Balanced trees solve this problem. An AVL tree is a self‑balancing BST where the height difference between the left and right sub‑trees of any node never exceeds one; rotations are performed after insertions to restore balance.

A 2‑3 tree is a multi‑way search tree whose internal nodes are either 2‑nodes (two children, one key) or 3‑nodes (three children, two keys); all leaves reside on the same depth, guaranteeing balance.

A 2‑3‑4 tree extends this idea with 4‑nodes (four children, three keys). Insertion follows two rules: new keys are added to the rightmost leaf, and a 4‑node is split into three 2‑nodes, promoting the middle key upward.

B‑trees generalize 2‑3‑4 trees: a B‑tree of degree *d* allows up to *d* children per node. When *d* = 3 the structure is a 2‑3 tree; when *d* = 4 it is a 2‑3‑4 tree.

Red‑Black trees are a special kind of BST that store an extra color bit (red or black) per node. Their five properties (root is black, red nodes have black children, every leaf (NIL) is black, every path from a node to its descendant leaves contains the same number of black nodes, and no path is more than twice as long as any other) make them a binary representation of 2‑3‑4 trees, ensuring logarithmic height.

Balancing operations include left and right rotations: a left rotation makes a node’s right child the new subtree root, while a right rotation makes the left child the new root. These rotations, together with recoloring, keep the red‑black tree balanced after insertions and deletions.

Red‑Black trees are widely used in practice, for example in Java’s TreeMap/TreeSet, C++ STL’s map and set, and Linux’s virtual memory management, because they provide O(log n) time for ordered operations.