Understanding Trees, Binary Trees, AVL Trees, and Red-Black Trees: Concepts, Properties, and Operations

Background

During a Java interview, a candidate was asked about the differences between HashMap implementations in JDK7 and JDK8, and then was challenged to draw a red‑black tree on a glass wall, revealing a common interview tactic of probing deeper knowledge of tree structures.

Tree

Tree in Real Life

A tree in nature represents a hierarchical "one‑to‑many" relationship, which mirrors the abstract tree data structure used in computing.

Tree in Data Structures

A tree is a non‑linear storage structure that holds elements with a parent‑child relationship, e.g., the set {A,B,C,D,E,F,G,H,I,J,K,L,M} where A is related to B, C, D, etc.

Tree Nodes

Node : each element stored in the tree.

Parent, Child, Sibling : relationships among nodes.

Root Node : the unique node without a parent.

Leaf Node : a node with no children.

Subtree

A subtree is a tree formed by a node and all its descendants; a single node also qualifies as a subtree.

Empty Tree

An empty tree contains no nodes.

Binary Tree

A binary tree is an ordered tree where each node has at most two children, designated as left and right subtrees.

public class Node<T> {
    T data;
    Node<T> left;
    Node<T> right;
}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

Binary Search Tree

A binary search tree (BST) maintains the ordering property: left subtree values are less than the node, right subtree values are greater.

If the left subtree is non‑empty, all its node values are less than the root.

If the right subtree is non‑empty, all its node values are greater than the root.

Both subtrees are themselves BSTs.

When inserted elements are already sorted, a BST degenerates into a linked list, degrading search complexity from O(log n) to O(n).

Balanced Binary Tree (AVL Tree)

An AVL tree is a self‑balancing BST where the height difference between left and right subtrees of any node does not exceed 1.

Red‑Black Tree

A red‑black tree is a self‑balancing binary tree that enforces five properties:

Each node is either red or black.

The root is always black.

All leaves (NIL nodes) are black.

Red nodes cannot have red children.

Every path from a node to its descendant leaves contains the same number of black nodes.

These rules guarantee that the longest path is at most twice the shortest, ensuring O(log n) height.

Balancing Operations

Balancing is achieved through three primitive operations:

Left Rotation : applied when a right child is red.

Right Rotation : applied when a left child and its left child are red.

Recoloring : flipping colors of a node and its relatives.

Insertion

New nodes are inserted as red. Depending on the colors of the parent (P), grandparent (G), and uncle (U), the algorithm performs recoloring and/or rotations to restore the red‑black properties. Four main cases are considered:

Inserted node is the root – recolor to black.

Parent is black – simple insertion, possibly followed by a left rotation if the new node is a right child.

Parent and uncle are red – recolor parent, uncle, and grandparent, then recurse.

Parent is red and uncle is black (or absent) – perform appropriate rotations and recoloring based on whether the new node is a left or right child.

Deletion

Deletion also follows case analysis based on the colors of the node to be removed (X), its sibling (B), and their children. The algorithm may replace X with its child, perform recoloring, and apply rotations (left or right) to maintain the red‑black invariants. Six detailed scenarios are described, ranging from simple removal of a red leaf to complex restructuring when both X and its sibling are black.

Summary

The article walks through tree concepts from basic trees to binary trees, AVL trees, and finally red‑black trees, emphasizing that the difficulty of red‑black trees lies in the insertion and deletion rebalancing steps; readers are encouraged to study the accompanying diagrams to grasp the transformations.