🖥️
Sunil Notebook
Interview Preparation
  • 📒Notebook
    • What is this about ?
  • System Design
    • 💡Key Concepts
      • 🌐Scalability
      • 🌐Latency Vs Throughput
      • 🌐Databases
      • 🌐CAP Theorem
      • 🌐ACID Transactions
      • 🌐Rate limiting
      • 🌐API Design
      • 🌐Strong Vs eventual consistency
      • 🌐Distributed tracing
      • 🌐Synchronous Vs asynchronous Communication
      • 🌐Batch Processing Vs Stream Processing
      • 🌐Fault Tolerance
    • 💎Building Blocks
      • 🔹Message
      • 🔹Cache
      • 🔹Load Balancer Vs API Gateway
    • 🖥️Introduction to system design
    • ⏱️Step By Step Guide
    • ♨️Emerging Technologies in System Design
    • ☑️System design component checklist
      • 🔷Azure
      • 🔶AWS
      • ♦️Google Cloud
    • 🧊LinkedIn feed Design
    • 🏏Scalable Emoji Broadcasting System - Hotstar
    • 💲UPI Payment System Design
    • 📈Stock Broker System Design - Groww
    • 🧑‍🤝‍🧑Designing Instagram's Collaborative Content Creation - Close Friends Only
    • 🌳Vending Machines - Over the air Systems
    • Reference Links
  • DSA
    • Topics
      • Introduction
      • Algorithm analysis
        • Asymptotic Notation
        • Memory
      • Sorting
        • Selection Sort
        • Insertion Sort
        • Merge Sort
        • Quick Sort
        • Quick'3 Sort
        • Shell Sort
        • Shuffle sort
        • Heap Sort
        • Arrays.sort()
        • Key Points
        • Problems
          • Reorder Log files
      • Stacks and Queues
        • Stack Implementations
        • Queue Implementations
        • Priority Queues
        • Problems
          • Dijkstra's two-stack algorithm
      • Binary Search Tree
        • Left Leaning Red Black Tree
          • Java Implementations
        • 2-3 Tree
          • Search Operation - 2-3 Tree
          • Insert Operation - 2-3 Tree
        • Geometric Applications of BST
      • B-Tree
      • Graphs
        • Undirected Graphs
        • Directed Graphs
        • Topological Sort
      • Union Find
        • Dynamic Connectivity
        • Quick Find - Eager Approach
        • Quick Find - Lazy Approach
        • Defects
        • Weighted Quick Union
        • Quick Union + path comparison
        • Amortized Analysis
      • Convex Hull
      • Binary Heaps and Priority Queue
      • Hash Table vs Binary Search Trees
  • Concurrency and Multithreading
    • Introduction
    • Visibility Problem
    • Interview Questions
    • References
      • System design
  • Design Patterns
    • ℹ️Introduction
    • 💠Classification of patterns
    • 1️⃣Structural Design Patterns
      • Adapter Design Pattern
      • Bridge Design Pattern
      • Composite Design Pattern
      • Decorator Design Pattern
      • Facade Design Pattern
      • Flyweight Design Pattern
      • Private Class Data Design Pattern
      • Proxy Design Pattern
    • 2️⃣Behavioral Design Patterns
      • Chain Of Responsibility
      • Command Design Pattern
      • Interpreter Design Pattern
      • Iterator Design Pattern
      • Mediator Design Pattern
      • Memento Design Pattern
      • Null Object Design Pattern
      • Observer Design Pattern
      • State Design Pattern
      • Strategy Design Pattern
      • Template Design Pattern
    • 3️⃣Creational Design Patterns
      • Abstract Factory Design Pattern
      • Builder Design Pattern
      • Factory Method Design Pattern
      • Object Pool Design Pattern
      • Prototype Design Pattern
      • Singleton Design Pattern
    • Java Pass by Value or Pass by Reference
  • Designing Data-Intensive Applications - O'Reilly
    • Read Me
    • 1️⃣Reliable, Scalable, and Maintainable Applications
      • Reliability
      • Scalability
      • Maintainability
      • References
    • 2️⃣Data Models and Query Languages
      • Read me
      • References
    • Miscellaneous
  • Preparation Manual
    • Disclaimer
    • What is it all about?
    • About a bunch of links
    • Before you start preparing
    • Algorithms and Coding
    • Concurrency and Multithreading
    • Programming Language and Fundementals
    • Best Practices and Experience
  • Web Applications
    • Typescript Guidelines
  • Research Papers
    • Research Papers
      • Real-Time Data Infrastructure at Uber
      • Scaling Memcache at Facebook
  • Interview Questions
    • Important links for preparation
    • Google Interview Questions
      • L4
        • Phone Interview Questions
      • L3
        • Interview Questions
      • Phone Screen Questions
  • Miscellaneous
    • 90 Days Preparation Schedule
    • My Preparation for Tech Giants
    • Top Product Based Companies
  • Links
    • Github
    • LinkedIn
Powered by GitBook
On this page
  • Node Implementation
  • Search Operation
  • Elementary operations
  • Left Rotation
  • Right Rotation
  • Color Flip
  • Insertion
  • Case 1: Into Exactly 2-node
  • Case 2: Insert into 3-node
  • Passing red links up the tree
  • Java Implementation
  • Delete

Was this helpful?

Edit on GitHub
  1. DSA
  2. Topics
  3. Binary Search Tree
  4. Left Leaning Red Black Tree

Java Implementations

PreviousLeft Leaning Red Black TreeNext2-3 Tree

Last updated 3 years ago

Was this helpful?

Node Implementation

private static final boolean RED = true;
private static final boolean BLACK = false;

class TreeNode{
    private Key key;
    private Value val;
    private TreeNode left;
    private TreeNode right;
    private boolean color;
    
    // ....... constructor ........
}

private boolean isRed(Node x){
    if(x == null) return false;
    return x.color == RED;
}

Search Operation

Observation. Search is the same as for elementary BST ( ignore color ).

public class redBlackTree {
    public key search(TreeNode x, key key){
        if(x == null) return null;
        while(x!=null){
            int cmp = (key).compareTo(x.key);
            if( cmp < 0 ) x = x.left;
            else if( cmp > 0 ) x = x.right;
            else return  x.key;
        }
        return null;
    }
}

Elementary operations

Left Rotation

private TreeNode rotateLeft(TreeNode h)
 {
     assert isRed(h.right);
     TreeNode x = h.right;
     h.right = x.left;
     x.left = h;
     x.color = h.color;
     h.color = RED;
     return x;
 }

Right Rotation

Invariants: Maintains symmetric order and perfect black balance.

private TreeNode rotateRight(TreeNode h)
 {
     assert isRed(h.left);
     TreeNode x = h.left;
     h.left = x.right;
     x.right = h;
     x.color = h.color;
     h.color = RED;
     return x;
 }

Color Flip

public void colorFlip(TreeNode h){
    assert !isRed(h);
    assert isRed(h.left);
    assert isRed(h.right);
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}

Insertion

Basic Strategy: Maintain 1-1 correspondence with 2-3 trees by applying elementary red-black BST operations.

Case 1: Into Exactly 2-node

  • Do standard BST insert; color new link red

  • If new red link is a right link, rotate left.

Example: Insert ' C '

Case 2: Insert into 3-node

  • Do standard BST insert; color new link red.

  • Rotate to balance the 4-node ( if needed ).

  • Flip colors to pass red link up one level.

  • Rotate to make lean left (if needed).

Example: Inserting ' H '

Passing red links up the tree

  • Do standard BST insert; color new link red.

  • Rotate to balance the 4-node ( if needed ).

  • Flip colors to pass red link up one level.

  • Rotate to make lean left (if needed).

  • Repeat case 1, case 2 ( if needed ).

Example:

Java Implementation

private Node put(Node h, Key key, Value val)
 {
     // insert at bottom with color RED
     if (h == null) return new Node(key, val, RED);
     int cmp = key.compareTo(h.key);
     
     if (cmp < 0) h.left = put(h.left, key, val);
     else if (cmp > 0) h.right = put(h.right, key, val);
     else if (cmp == 0) h.val = val;
     
     //lean left
     // Right child red, left child black: rotate left.
     if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
     
     // balance 4-node
     // Left child, left-left grandchild red: rotate right.
     if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
     
     // split 4-node
     // Both children red: flip colors.
     if (isRed(h.left) && isRed(h.right)) flipColors(h);
    
     return h;
 }

Delete

Delete operations are bit complicated.

Explanation for inserting a node in 2-node
Example for inserting a node in 2-node
Explanation for inserting a node in 3-node
Example for inserting a node in 3-node Red Black Tree