🍁
Data Structures and Algorithms
  • Introduction
  • Introduction to Algorithms Analysis
    • Growth Rates
    • Big-O, Little-o, Theta, Omega
    • Analysis of Linear Search
    • Analysis of Binary Search
  • Recursion
    • The runtime stack
    • How to Write a Recursive Function
      • Example: the Factorial Function
    • Drawbacks of Recursion and Caution
  • Lists
    • Implementation
    • Linked List
      • Nodes
      • Iterator
      • Template Singly Linked List
      • Doubly Linked List
      • Circular Linked List
  • Stacks
    • Stack Operations
    • Stack Implementations
    • Stack Applications
  • Queue
    • Queue Operations
    • Queue Implementations
    • Queue Applications
  • Tables
    • Simple Table
    • Hash Table
      • Bucketing
      • Chaining
      • Linear Probing
      • Quadratic Probing and Double Hashing
  • Sorting
    • Simple Sorts
      • Bubble Sort
      • Insertion Sort
      • Selection Sort
    • Merge Sort
      • Merge Sort Implementation
    • Quick Sort
    • Heap Sort
      • Binary heap
      • Binary heap basics
      • Insertion into a binary heap
      • Delete from a binary heap
      • Implementation
      • Sorting
  • Introduction to Trees, Binary Search Trees
    • Definitions
    • Tree Implementations
    • Binary Trees
    • Binary Search Trees
      • Insertion
      • Removal
      • Traversals
  • AVL Trees
    • Height Balance
    • Insertion
    • Why it works
  • Red Black Trees
    • Insertion Example
  • 2-3 Trees
  • Graphs
    • Representation
  • Complexity Theory
  • Appendix: Mathematics Review
Powered by GitBook
On this page
  • Insert 30
  • Insert 50
  • Insert 40
  • Insert 20
  • Insert 10

Was this helpful?

  1. Red Black Trees

Insertion Example

PreviousRed Black TreesNext2-3 Trees

Last updated 5 years ago

Was this helpful?

Starting with an empty tree let us take a look at how red-black tree insertions work.

In the pictures below, null nodes (empty subtrees) are denoted as black circles

Insert 30

All nodes are inserted as red nodes:

If the root is red, make it black:

Insert 50

Insert 50 as a red node, parent is black so we don't have to change anything

Insert 40

Inserting 40 as a red node.

If parent is red, we must apply fix. Parent's sibling (50's sibling) is black, so we must perform a rotation.

The type of rotation depends on the insertion pathway. If the insertion path from grand parent to parent to node is straight (both left or both right) do a single rotation. If it is angled (left then right or right then left) we need to do a double.

In this case, we need to do a double (aka zig zag) rotation.

Rotate first 40 and 50

then rotate again with 30 and 40, this time doing a colour swap. A zigzag rotation is just an extra step that is needed to make the insertion path go in the same direction.

Finally we end up with:

Insert 20

inserting 20 as a red node.

If parent is red we must apply a fix. Parent's sibling is red so we need to do a colour swap between parent+sibling and grandparent.

Now as 40 is the root of the whole tree we must change 40's colour to black. As it is the root, we can just change it to black without causing other problems.

Insert 10

If parent is red, we must apply a fix. Parent's sibling is black, so a rotation is needed. This time, the insertion path from grandparent to parent to node is "left" then "left". Thus, we only need to perform a single rotation and colour swap.

Finally we get:

inserting 10 as a red node.