Deleting a Node in a Binary Search Tree (LeetCode 450: Delete Node in a BST)
- February 5, 2025
- Liu, An-Chi 劉安齊
Converting Pthreads to JavaScript with Emscripten and Performance Analysis (2) — Merge Sort
- August 10, 2020
- Liu, An-Chi 劉安齊
Red-Black Tree (RBT) Introduction
- November 27, 2019
- Liu, An-Chi 劉安齊
¶ Red-Black Tree Overview
A red-black tree is a special data structure that can automatically balance itself, similar to an AVL tree.
A red-black tree has the following properties:
- Each node is either red or black
- The root must be black
- Every leaf (
NIL) is black - If a node is red, its children must be black
- Every path from the root to a leaf has the same number of black nodes
Following these rules ensures the tree stays balanced during insertions and deletions. A red-black tree guarantees that when the number of nodes is n, the height is at most 2log(n+1).
In practice, it is often used to implement sets and dictionaries. In C++, std::set and std::map are backed by red-black trees.