Red-Black Tree Visualized Teaching Website

Home Title

Welcome to the computer science visualized teaching platform. This website will teach you how to learn about Red-Black Trees

Author: Mingyang Fang (mfang34)

Introduction

Red-Black Tree is a self-balancing binary search tree. Red-Black Trees are widely used in Java's TreeMap and Linux's process scheduling. This website will help you master Red-Black Trees from scratch through easy-to-understand teaching texts and related example analyses.

Teaching Content Modules

Module 1: What is a red-black tree?

Definition: A red-black tree is a special kind of binary search tree that contains red nodes and black nodes and some additional rules to achieve automatic balancing.

Uses: The time complexity of insertion, deletion, and search is O(log n). Java TreeMap, C++ STL map/set, and heavily used in operating system scheduling.

Module 2: The five properties of a red-black tree

Each node is either red or black
The root node is black
Two consecutive red nodes cannot appear at the same time
The number of black nodes on the path from the root node to any leaf node is the same
Leaf nodes must be black

Module 3: Insertion operation demonstration

Inserting a node is the root node -> it becomes black directly
The uncle of the inserted node is red -> the uncle's father and grandfather change color, and the grandfather becomes the inserted node
The uncle of the inserted node is black -> (LL, RR, LR, RL) rotate and then change color

Module 4: Demonstration of deletion operations

Only left child / only right child: black after replacement
No child, red node: no need to make any adjustments after deletion
No child, black node, brother is black:

Brother has at least one red child: (LL, RR, LR, RL) change color + rotate
Brother's children are all black: brother turns red, double black moves up

No child, black node, brother is red: brother's father changes color, rotates toward double black

Module 5: Comparison of red-black trees with other trees

Tree Type	Self-Balancing	Search Efficiency	Rotation Frequency
Normal BST	No	O(n)	0
AVL Tree	Yes	O(log n)	Many
Red-Black Tree	Yes	O(log n)	Few