Red-black tree invariants work by encoding enough structural information in red and black node colours to guarantee that no search path becomes arbitrarily longer than another. The tree does not store an explicit balance factor like AVL. Instead, it maintains rules about red adjacency and black counts along root-to-leaf paths.
These rules are powerful because they separate ordinary depth into two kinds of structure. Black nodes form a shared backbone whose count is equal across every root-to-NIL path. Red nodes provide limited slack between black levels, but red nodes cannot chain together. The combination bounds total height by a constant factor of the black backbone.
This pillar owns the invariant layer: node colours, black NIL leaves, root colour, the no-red-red rule, black height, proof of logarithmic height, valid and invalid examples, validation algorithms, sentinel design, metadata representation, duplicate policies and the difference between local colour validity and global black-height validity.
Master guide: How Red-Black Trees Work · Foundation: How Binary Search Trees Work · Compare: How AVL Trees Work · Generic rotation primitive
The Invariant Layer Sits Above BST Ordering
Ordering Still Defines Search
A red-black tree is first a valid binary search tree. Keys on the left compare before the node and keys on the right compare after it. Colour does not tell search where to go. It tells update algorithms whether the shape remains within the red-black balance regime.
Balance Cannot Repair Misordered Keys
If a node is attached on the wrong side, recolouring can leave every colour rule satisfied while search remains semantically broken. Rotations preserve inorder order and therefore cannot sort an already misordered tree. Production validation must check both ordered-key invariants and colour invariants.
Invariant One: Every Real Node Has a Colour
Two Logical States
Each stored node is red or black. A concrete implementation might encode this in a boolean, enum, spare pointer bit or compact tag. The representation may vary; the logical state space does not.
Why Two States Are Enough
The colour is not a direct height number. It marks whether a node contributes to the black backbone. Black contributes one unit of black height; red contributes ordinary depth without increasing black count. Those two roles are sufficient for the balancing proof.
Invariant Two: NIL Leaves Are Black
Conceptual Leaves Complete the Tree
Every missing child can be viewed as a black NIL leaf. This lets every internal node have two conceptual children and gives every downward path a common terminal object.
Sentinel Blackness Simplifies Black Height
If null children had no colour, every proof and deletion case would need a special boundary definition. Treating NIL as black means black-height rules apply uniformly to real and absent children. Many implementations use a shared sentinel to turn that mathematical convenience into code.
Invariant Three: The Root Is Black
Stable Public State
After an update finishes, the root is black under the standard definition. Insertion can temporarily propagate a red conflict to the root, but the last step recolours it black.
Why Root Recolouring Is Safe
Every root-to-NIL path passes through the root. Changing the root from red to black increases the black count on every path equally. Therefore black-height equality is preserved even though the absolute black height increases.
Invariant Four: Red Nodes Have Black Children
No Red-Red Parent-Child Edge
If a node is red, both conceptual children are black. Equivalently, a red node cannot have a red parent except during transient insertion repair.
What the Rule Prevents
Without this rule, a path could contain a long chain of red nodes that added ordinary height without adding black height. The black backbone could remain balanced while total path length exploded. No-red-red adjacency limits red slack to at most one node between black levels.
Invariant Five: Equal Black Height
All Paths From a Node to Descendant NIL Leaves Carry Equal Black Count
Choose a node and follow any route down to a conceptual NIL leaf. Count black nodes according to the chosen convention. Every such route must have the same black count.
This Rule Is Global, Not Merely Parent-Child
A node can have black children and still violate red-black balance if one deeper branch contains an extra black level. Local colour checks alone cannot certify the tree. Validation needs recursive black-height comparison.
Define Black Height Consistently
Conventions Differ Slightly
Some definitions count the current node if black; others define black height below the node and count descendant black nodes but not the node itself. NIL may or may not be included in the numerical label depending on convention.
The Equality Relationship Is What Matters
All standard conventions lead to the same validity decisions if applied consistently. Problems arise when insertion, deletion or validation mixes definitions. Document the convention beside the black-height helper and test tiny trees explicitly.
A One-Node Tree Is Valid
Black Root, Black NIL Children
A single black root with two conceptual black NIL children satisfies every invariant. There are no red-red edges, and both root-to-NIL paths have equal black count.
A Red Root Is Usually Normalised Away
A single red root could satisfy no-red-red and equal-path rules under some relaxed formulations, but the standard root-black invariant recolours it. Normalising the root reduces proof and implementation variation.
Red Children Can Appear Under a Black Parent
One Red Child Is Legal
A black node may have a red child provided the red child has black children and black-height equality remains valid.
Two Red Children Can Also Be Legal
A black node may have both children red. This often appears transiently before insertion recolouring or as a stable local pattern. What matters is that the red children themselves do not continue into red descendants and all black counts still agree.
A Red Parent and Red Child Is Immediately Invalid
The Violation Is Local and Easy to Detect
Check every red node’s children. If either child is red, the no-red-red invariant fails.
Why Insertion Focuses on This Violation
New nodes are typically inserted red to preserve black height. Therefore the most likely new problem is exactly a red parent with a red child. Insertion fix-up is built around repairing that local condition without disturbing black counts.
Equal Black Height Can Fail With No Red-Red Edge
A Subtle Invalid Tree
Imagine every real node is black, but the left branch has three internal black nodes before NIL while the right branch has two. No red-red edge exists because there are no red nodes at all, yet the tree is invalid.
Why This Matters in Testing
A validator that checks only root colour and red adjacency can miss the central balance property. Black-height equality must be calculated recursively and compared between siblings.
The Height Proof Starts From Black Height
Every Long Path Contains a Black Backbone
Because all paths have equal black height, every root-to-NIL route contains the same number of black structural levels.
Red Nodes Can Only Appear Between Black Nodes
No-red-red adjacency means a path can insert at most one red node between successive black nodes. Therefore total internal path length is at most a small constant multiple of black height.
Minimum Nodes Grow Exponentially With Black Height
A Black-Height-b Subtree Cannot Be Arbitrarily Sparse
Both child paths must retain enough black structure to reach the required black height. Red nodes may change local branching shape, but they cannot remove the need for the black backbone on both sides.
Exponential Growth Gives Logarithmic Black Height
Standard red-black proofs show a subtree with black height b contains at least 2^b−1 internal nodes under an appropriate convention. Therefore b is O(log n). Combined with the no-red-red bound, ordinary height is also O(log n).
Why Longest and Shortest Paths Differ by Only a Constant Factor
Shortest Path Uses Mostly Black Nodes
A short root-to-NIL path can descend through black nodes without inserting red levels between them.
Longest Path Alternates Black and Red
A longest legal path may add a red node between many pairs of black nodes, but cannot add two reds consecutively. Its length is therefore at most roughly twice that of the black backbone. Red-black balance is loose, but not uncontrolled.
The Invariants Do Not Force Perfect Symmetry
Subtrees Can Have Different Ordinary Heights
One child subtree may use more red slack than the other while maintaining the same black height.
This Flexibility Is the Point
Red-black trees avoid the strict per-node ordinary-height difference required by AVL. The looser condition still guarantees logarithmic search while giving update algorithms more ways to restore validity through recolouring.
Black Height Is Not Stored Necessarily
Many Implementations Store Only Colour
Insertion and deletion algorithms reason locally about colour and structural cases without caching black height on every node.
Validation Can Recompute Black Height
A recursive invariant checker can calculate it from children, making sure left and right agree before returning the parent’s black height. This is useful precisely because it does not trust update code.
Colour Is Metadata, but It Is Structural Metadata
Changing Colour Changes the Balance Interpretation
Recolouring a node can change the black contribution of every path through its subtree without moving a pointer.
That Is Why Recolouring Is an Algorithmic Operation
A red-uncle insertion case repairs local black-height relationships by coordinated recolouring. Colour writes are not cosmetic rendering decisions; they are part of the data-structure transformation.
Recolouring Must Preserve Black-Height Relationships
Single-Node Recolouring Is Usually Not Arbitrary
Turning one internal black node red removes one black count from every path through it and can make those paths inconsistent with siblings.
Fix-Up Recolours Families Deliberately
Insertion and deletion algorithms recolour parent, uncle, grandparent, sibling or children in combinations chosen so black contribution is redistributed coherently. Case logic is a proof embodied in code.
Sentinel NIL Leaves Make Deletion Cases Uniform
A Missing Replacement Still Has a Colour
When deleting a black leaf, the replacement position is logically NIL and black. Fix-up can talk about its sibling and parent even though no user entry exists there.
One Shared Sentinel Can Carry Parent Context
Some imperative implementations temporarily update the sentinel’s parent pointer during deletion so the fix-up loop can navigate upward. This is useful but requires disciplined sentinel handling because one global object represents many conceptual leaves over time.
The Root-Black Rule Is Not the Main Height Guarantee
Equal Black Height and No-Red-Red Do Most of the Work
If the root colour changed, relative path black counts and red spacing could still remain bounded.
Root Black Normalises the Representation
Making the root black gives a consistent canonical stable state and simplifies recursive definitions. It also prevents a top-level red-red issue after propagation. Useful conventions can be important even when they are not the deepest source of the theorem.
Duplicate-Key Policy Is Separate From Colour
Map and Set Semantics Usually Collapse Comparator Equality
An equal key updates an existing value or is ignored. No new node means no new colour case.
Multisets Can Store Counts
Multiplicity inside one node leaves the colour structure unchanged until the final occurrence is removed. If duplicates are stored as separate nodes, the comparator’s non-strict placement policy must survive rotations, making invariant reasoning more complicated.
Colour and Parent Pointers Are Independent Metadata
Parent Links Support Fix-Up Navigation
Insertion uses parent and grandparent; deletion uses parent and sibling. Parent pointers make those relations easy to reach.
Parent Validity Must Be Checked Separately
A tree can satisfy every colour invariant under downward traversal while parent pointers are stale. Later fix-up can then navigate incorrectly. Validate reciprocal links if the implementation stores them.
Augmented Red-Black Trees Add More Invariants
Subtree Size Enables Rank Queries
Each node can store the number of descendants for order-statistics operations.
Rotations and Transplants Must Repair Every Summary
Colour validity does not imply size or interval metadata correctness. Recompute augmented fields from children after structural changes. A data structure can be a valid red-black tree and still answer rank queries incorrectly if augmentation drifts.
A Validator Should Return More Than True or False
Return Black Height
Validate left and right recursively, compare their black heights and return the common value plus one if the current node is black.
Carry Comparator Bounds
At the same time, pass allowable lower and upper key bounds down the recursion. This lets one validation traversal certify both BST order and red-black colour structure.
A Validator Should Treat NIL Explicitly
NIL Base Case
At a conceptual black NIL leaf, return the chosen base black height consistently.
Sentinel Safety
If using a real sentinel object, ensure it is black and not counted as a user entry. Validation should avoid following sentinel child pointers indefinitely if the sentinel references itself.
Worked Valid Example
Black Root With Red Children
Take black 20 with red children 10 and 30, each having black NIL children. Every root-to-NIL path includes the same black root and terminal black NIL contribution under the common conceptual count. Red nodes have black children.
Why It Can Be Shallower Than an All-Black Equivalent
The red children add one ordinary level without adding black height. Red slack lets the tree represent more keys between black backbone levels while keeping path ratios controlled.
Worked Invalid Example: Red Chain
Black 30, Red 20, Red 10
The BST ordering can be perfectly valid. But 20 and 10 form a red-red edge.
Why Height Control Would Fail if Repeated
If arbitrary red chains were allowed, many ordinary levels could be inserted without increasing black height. The proof bounding total height by black height would collapse.
Worked Invalid Example: Unequal Black Paths
Black 20 With a Black Left Child and NIL Right
Assume the left child itself terminates in NIL leaves. The path through the left side contains one more real black node than the direct right-NIL path.
No Recolouring of an Unrelated Node Can Hide the Mismatch
Repair must address the local structural/colour relationship so both sides carry equal black contribution. This is why deletion fix-up focuses on sibling families around the deficit.
Invariant Transitions During Insertion
New Red Node Preserves Black Height Initially
The only possible immediate red-black violation is a red-red edge with its parent.
Fix-Up Restores Stable State
Red uncle triggers coordinated recolouring and possible upward propagation; black uncle triggers rotation plus recolouring. The tree returns with root black, no red-red edge and equal black heights.
Invariant Transitions During Deletion
Removing Red Preserves Black Count
No black contribution disappears.
Removing Black Can Create a Deficit
A red replacement can be recoloured black; otherwise fix-up reasons about the missing black contribution using sibling and sibling-child colours. The invariant perspective explains why deletion’s case family differs fundamentally from insertion.
Red-Black Invariants Versus AVL Invariants
AVL Stores Ordinary Height Information Directly
Its local rule constrains left/right height difference to at most one.
Red-Black Stores a Coarser Structural Encoding
Colour controls black-height equality and red spacing instead of exact ordinary height. This makes red-black balance looser and update policy different while retaining logarithmic height.
Why Libraries Often Choose Red-Black-Like Trees
General-Purpose Ordered Operations Need Deterministic Height
Search, lower bound, ranges and iteration benefit from a balanced tree guarantee.
Update Flexibility Is Valuable
Recolouring can repair some insertion conflicts without rotation, and the looser invariant tolerates more shapes. Implementation maturity, iterator guarantees and node-based APIs also influence library choices.
Common Invariant Failure: NIL Treated as Red or Colourless Inconsistently
Symptom
Deletion case logic dereferences null specially in some branches and assumes black in others.
Repair
Choose one conceptual model. Even if physical pointers are null, helper functions can define colour(null)=black. Uniform boundary semantics make case analysis and validation reliable.
Common Invariant Failure: Root Colour Forgotten After Propagation
Symptom
Insertion recolours a grandparent red and moves current upward until it becomes root, then returns.
Repair
Normalise the final root to black before exposing the stable tree. Add a root-black assertion to every mutation test.
Common Invariant Failure: Validator Trusts Stored State
Symptom
The same buggy colour or height helper is used by both update code and validator, so corruption self-certifies.
Repair
Write validation as an independent recursive specification. Recompute ordering bounds and black height directly from links and colour fields, not from cached derived values.
Rainbolt and CivDJ Views of the Invariants
Rainbolt View: Read the Black Backbone
Black nodes mark the shared structural skeleton. Red nodes are permitted extra steps, but they cannot stack. The visual colour pattern tells you where the tree is using slack and where every path must still pay the same black structural cost.
CivDJ View: Invariants as Constitutional Rules
A programmer sees booleans, a mathematician sees a height proof, a verifier sees recursive predicates, and a library designer sees a predictable ordered container. The rules work because no single update is allowed to leave the public structure outside the shared constitution.
How to Teach the Invariants Before the Fix-Up Cases
Prove the Purpose of Each Rule
Ask what would go wrong if red-red chains were allowed, then what would go wrong if black heights differed. Learners see that each invariant blocks a specific way the tree could become too tall.
Then Make Case Tables Restore Named Rules
Insertion repairs red-red conflict while preserving black counts. Deletion repairs black-count deficit while protecting red adjacency. The case diagrams become meaningful because each pointer or colour change has an invariant it serves.
Frequently Asked Questions
Can a Black Node Have a Black Child?
Yes. Black-black edges are normal. The equal-black-height rule controls total counts across sibling paths rather than forbidding consecutive black nodes.
Can a Black Node Have Two Red Children?
Yes, if those red children have black children and all descendant paths preserve equal black height. This configuration often appears before or after recolouring.
More Frequently Asked Questions
Is Black Height the Same as Ordinary Height?
No. Ordinary height counts all structural levels. Black height counts only black contributions under a chosen convention. Red nodes can increase ordinary height without increasing black height.
Does Every Valid Red-Black Tree Have the Same Colouring?
No. The same key set and even the same underlying BST shape can sometimes admit different valid colourings. The invariants define a valid family, not one canonical colouring.
The Pillar Boundary and Sources
What This Article Owns
This pillar owns the red-black invariant system: colours, root black, black NIL leaves, no-red-red adjacency, black height, logarithmic-height proof and invariant validation. Insertion and deletion fix-up have separate canonical pages.
Sources and Further Reading
For balanced search-tree foundations, see Princeton Algorithms: Balanced Search Trees. For the underlying BST structure, see MIT OpenCourseWare: Binary Search Trees.
Final Synthesis: Red-Black Balance Is a Contract Between Path Colour and Path Length
The Contract
Keep the root and NIL leaves black, never allow red to touch red, and require equal black height on every descendant path.
The Result
Black nodes form a common backbone; red nodes add only bounded slack. Those simple rules are strong enough to prevent linear-height degeneration and flexible enough to support local recolouring and rotations after updates.
Worked Black-Height Ledger: Count the Backbone Explicitly
Write the Black Count on Every Root-to-NIL Path
Take a small tree and annotate each downward path with the number of black nodes encountered under one chosen convention. Do not infer validity from visual symmetry. A left path can contain more ordinary nodes than a right path and still be valid if the extra nodes are red and the black counts match. Conversely, two paths can have similar ordinary lengths and still be invalid if one contains an extra black node. The ledger forces the distinction between total depth and black structural depth.
Black Height Is a Conservation Quantity
Insertion and deletion fix-up become easier to understand when black height is treated like a conserved accounting quantity. Recolouring parent and uncle black while grandparent becomes red moves where blackness sits without changing the total along local descendant paths. Deletion fix-up performs the inverse kind of accounting: one side has lost a black contribution and sibling cases determine whether that deficit can be cancelled locally or must be passed upward.
Invariant Independence: One Rule Can Hold While Another Fails
No Red-Red Edge Does Not Guarantee Equal Black Height
An all-black unbalanced tree is the clearest counterexample. Every red adjacency rule is vacuously satisfied, yet one deep branch can contain more black nodes than another. The structure is a valid BST but not a valid red-black tree. This example is valuable because it shows why validators must check every invariant rather than assuming one implies the others.
Equal Black Height Does Not Guarantee No Red-Red Edge
A path can contain two consecutive red nodes without altering black count. If sibling paths are arranged with matching black totals, black-height equality can still hold while the no-red-red rule fails. Allowing such red chains would destroy the bound on total ordinary height. The two major invariants cooperate: one equalises black structure; the other limits how much non-black depth can accumulate between black levels.
From 2–3–4 Trees to Red-Black Intuition
A Red Link Can Be Read as a Logical Grouping
One common way to build intuition is to view certain red-black trees as binary encodings of higher-arity search-tree nodes. A red child can be interpreted as being grouped with a black parent, while black links separate logical multiway nodes. This perspective explains why black height behaves like the true structural level count and why red nodes add local flexibility without increasing the number of black levels.
The Analogy Explains Recolouring as Splitting or Merging Logical Nodes
When a black parent has two red children, recolouring the children black and the parent red resembles splitting an overfull logical multiway node and pushing a key upward. The correspondence depends on the particular red-black formulation, especially left-leaning variants, but it provides a strong mental model: colours encode how several binary nodes combine into a shallower logical search structure.
Why the Longest Path Cannot Be More Than About Twice the Shortest
The Short Path Pays the Black Backbone Cost
Every path from the same starting node to a NIL leaf contains the same number of black nodes. A shortest path cannot skip those black contributions. Its ordinary length is therefore at least the black-height scale of the subtree.
The Long Path Can Insert Only Isolated Red Nodes
Because red cannot follow red, the longest legal path can place at most one red node between consecutive black nodes. That allows extra depth but only at a bounded rate. The resulting constant-factor path ratio is weaker than AVL’s tight height balance but strong enough to prevent the long linked-list degeneration of a plain BST.
Stable-State Invariants Versus Transient Fix-Up States
Updates May Temporarily Violate One Rule
Insertion commonly creates a red-red edge before fix-up. Deletion can create a conceptual black deficit before sibling cases resolve it. These are algorithmic intermediate states, not valid public red-black trees. A useful implementation discipline is to define exactly which helper functions are allowed to receive transiently invalid structures and which public operations promise to return only fully valid stable state.
Assertions Belong at Stable Boundaries
Running the full invariant validator after every primitive colour change inside a fix-up routine would reject intentional intermediate states. Instead, validate at operation boundaries or after complete case transformations whose postconditions should restore specific local rules. This keeps assertions aligned with the algorithm’s proof structure rather than treating every intermediate pointer assignment as a public tree.
Colour Representation and Memory Layout
Explicit Colour Fields Favour Clarity
A dedicated byte, boolean or enum is easy to inspect in a debugger and easy to validate. The memory cost can be small relative to key, value and pointer fields, especially when padding would exist anyway. For educational and general-purpose implementations, explicit representation often pays for itself in reliability.
Pointer Tagging Is an Optimisation With Extra Proof Obligations
Some low-level containers store colour in an otherwise-unused pointer bit based on alignment guarantees. This can reduce node size, which may improve cache density. But every pointer access must mask and restore the tag correctly, tooling becomes less transparent and portability constraints tighten. The invariant remains conceptually identical; the encoding simply moves colour into a more compact representation.
Invariant Validation for Large Trees
A Single Recursive Pass Can Check the Core Rules
At each node, validate ordering bounds, recurse into both children, require equal returned black heights, check that red nodes have black children and return the local black height. At the root, assert black. This traversal is O(n), which is acceptable for tests, debug builds, offline integrity checks and occasional production diagnostics even though ordinary map operations are logarithmic.
Return Rich Failure Information
Instead of a boolean “invalid,” report the key where the first violation occurred, the expected key bounds, left and right black heights, node colour and parent colour. When a random mutation test discovers corruption, this local evidence often points directly to the fix-up branch that failed. A validator is more useful as an explanatory instrument than as a final red light.
Invariant-Preserving Serialization and Persistence
Logical Entries Are Safer to Persist Than Raw Shape
For many applications, serialising sorted key-value entries and rebuilding the balanced tree is safer than persisting implementation-specific pointer topology and colour bits. Internal representation can change between library versions. If exact shape is not part of the public contract, logical contents should be the durable format.
If Shape Is Persisted, Validate on Load
A stored tree can be corrupted by partial writes, incompatible versions or external modification. Recompute ordering and black height before trusting it. Persisted metadata should never bypass the invariant layer merely because it came from disk rather than a live update path.
Invariant Review: What Colour Does Not Tell You
Colour Does Not Tell You Exact Height
Two valid red-black trees with identical colour counts can have different ordinary shapes and different exact search depths for particular keys. The invariants bound worst-case height; they do not determine one unique balanced form.
Colour Does Not Tell You Workload Fitness
A perfectly valid red-black tree may still be slower than a hash table for exact lookups or slower than a B-tree on storage pages. The invariant certifies structural balance for ordered-tree operations. Container choice still depends on workload, memory hierarchy, update frequency and API guarantees.
Invariant Audit: Distinguish Shape Guarantees From API Guarantees
The Red-Black Rules Guarantee Height, Not Iteration Policy
A valid red-black tree guarantees a bounded ordered-search height under its comparator, but it does not by itself specify iterator invalidation, node-address stability, memory layout, concurrency semantics or whether duplicate keys are permitted. Those are container-level guarantees layered on top. Conflating them makes it difficult to tell whether a bug violates the mathematical data structure or only a particular library contract.
The Comparator Is Part of the Invariant Boundary
Every colour proof assumes that the underlying tree is already a coherent BST. If the comparator changes over time or gives inconsistent results, the tree may still satisfy root-black, no-red-red and equal-black-height rules while exact search fails. A complete red-black specification therefore begins with a stable ordering relation, then adds colour invariants as the height-control layer.
Black Height as a Debugging Signature
Print Black Heights at Subtree Roots
When a validator finds unequal child black heights, report both values and the local node colour. If the mismatch appears immediately after deletion, the last fix-up probably failed to restore a missing black contribution. If it appears after insertion, a recolouring or rotation likely changed one side without compensating the other. The first mismatching subtree root is usually much more informative than the final root-level failure.
Use the Signature to Minimise Failing Histories
In property tests, once a random operation sequence breaks black-height equality, shrink the sequence while preserving the first mismatching signature. A short sequence that reproduces one local black-height difference often exposes the exact case-table error. This turns a complicated global corruption into a small proof obligation around one family of nodes.
Invariant Review: Why the Rules Are Minimal but Cooperative
No single red-black rule provides the full height guarantee. Root black normalises the top. Black NIL leaves close every path consistently. Equal black height gives all paths the same black backbone. No-red-red adjacency limits how much ordinary depth can be inserted between those black levels. The design works because the rules constrain different failure modes and compose into one logarithmic-height proof.
This is also how the tree should be debugged: identify which invariant first became false rather than treating “red-black balance” as one opaque condition. A red-red failure points toward insertion recolouring or rotation. A black-height mismatch points toward deletion deficit or incorrect colour transfer. A valid colour structure with wrong search points toward BST ordering or comparator semantics.
A useful final test is to imagine deleting every colour field while keeping the pointers. The structure would still be a BST, but its height guarantee would no longer be certified. Now imagine keeping colours while scrambling key order: height control might remain, but search semantics would fail. Red-black trees work because ordered structure and colour structure are independent contracts maintained together.
Next pillar: How Red-Black Tree Insertion Fix-Up Works · Next pillar: How Red-Black Tree Deletion Fix-Up Works
Continue the Red-Black Tree Series
How Red-Black Trees Work · How Tree Rotations Work · How X Works Hub