Red-Black Tree Game

Game
Learn
Code

Test Your Red-Black Tree Knowledge

Add nodes to the tree and observe how the red-black tree properties are maintained through rotations and color changes.

Red-Black Tree Game initialized. Add nodes to begin!

Red-Black Tree Properties

A red-black tree is a self-balancing binary search tree with the following properties:

  1. Every node is either RED or BLACK
  2. The root is BLACK
  3. Every leaf (NIL node) is BLACK
  4. If a node is RED, then both its children are BLACK
  5. For each node, all simple paths from the node to descendant leaves contain the same number of BLACK nodes

Key Operations

Rotations

Rotations are used to maintain tree balance:

Insertion

When inserting a new node:

  1. Insert the node like in a normal BST and color it RED
  2. Recolor and rotate nodes to fix any violations of red-black properties

Deletion

When deleting a node:

  1. Remove the node like in a normal BST
  2. If the node was BLACK, recolor and rotate nodes to fix any violations

Red-Black Tree Implementation

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.parent = null;
        this.color = 'RED'; // New nodes are always red
    }
}

class RedBlackTree {
    constructor() {
        this.root = null;
        this.NIL = { color: 'BLACK' }; // NIL nodes are always black
    }
    
    // Insert a new node
    insert(value) {
        const newNode = new Node(value);
        newNode.left = this.NIL;
        newNode.right = this.NIL;
        
        // Regular BST insertion
        if (!this.root) {
            this.root = newNode;
            newNode.color = 'BLACK'; // Root must be black
            return newNode;
        }
        
        let current = this.root;
        let parent = null;
        
        while (current !== this.NIL) {
            parent = current;
            if (value < current.value) {
                current = current.left;
            } else if (value > current.value) {
                current = current.right;
            } else {
                // Value already exists
                return null;
            }
        }
        
        newNode.parent = parent;
        
        if (value < parent.value) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        
        // Fix Red-Black properties
        this.fixInsert(newNode);
        return newNode;
    }
    
    // Fix Red-Black tree properties after insertion
    fixInsert(node) {
        while (node !== this.root && node.parent && node.parent.color === 'RED') {
            let uncle;
            
            if (node.parent === node.parent.parent.left) {
                uncle = node.parent.parent.right;
                
                if (uncle && uncle.color === 'RED') {
                    // Case 1: Uncle is red
                    node.parent.color = 'BLACK';
                    uncle.color = 'BLACK';
                    node.parent.parent.color = 'RED';
                    node = node.parent.parent;
                } else {
                    if (node === node.parent.right) {
                        // Case 2: Node is right child
                        node = node.parent;
                        this.leftRotate(node);
                    }
                    
                    // Case 3: Node is left child
                    node.parent.color = 'BLACK';
                    node.parent.parent.color = 'RED';
                    this.rightRotate(node.parent.parent);
                }
            } else {
                uncle = node.parent.parent.left;
                
                if (uncle && uncle.color === 'RED') {
                    // Case 1: Uncle is red
                    node.parent.color = 'BLACK';
                    uncle.color = 'BLACK';
                    node.parent.parent.color = 'RED';
                    node = node.parent.parent;
                } else {
                    if (node === node.parent.left) {
                        // Case 2: Node is left child
                        node = node.parent;
                        this.rightRotate(node);
                    }
                    
                    // Case 3: Node is right child
                    node.parent.color = 'BLACK';
                    node.parent.parent.color = 'RED';
                    this.leftRotate(node.parent.parent);
                }
            }
        }
        
        this.root.color = 'BLACK';
    }
    
    // Left rotation
    leftRotate(x) {
        const y = x.right;
        x.right = y.left;
        
        if (y.left !== this.NIL) {
            y.left.parent = x;
        }
        
        y.parent = x.parent;
        
        if (!x.parent) {
            this.root = y;
        } else if (x === x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        
        y.left = x;
        x.parent = y;
    }
    
    // Right rotation
    rightRotate(y) {
        const x = y.left;
        y.left = x.right;
        
        if (x.right !== this.NIL) {
            x.right.parent = y;
        }
        
        x.parent = y.parent;
        
        if (!y.parent) {
            this.root = x;
        } else if (y === y.parent.right) {
            y.parent.right = x;
        } else {
            y.parent.left = x;
        }
        
        x.right = y;
        y.parent = x;
    }
    
    // Delete a node (simplified)
    delete(value) {
        // TODO: Implement delete operation
        return false;
    }
}

// Game logic
let tree = new RedBlackTree();
let manualMode = false;
let challengeMode = false;
let challengeTarget = null;
let errorCount = 0;

function addNode() {
    const value = parseInt(document.getElementById('nodeValue').value);
    if (isNaN(value)) return;
    
    try {
        const node = tree.insert(value);
        if (node) {
            logMessage(`Inserted node ${value}`, 'success');
            updateVisualization();
        } else {
            logMessage(`Value ${value} already exists in the tree`, 'error');
        }
    } catch (err) {
        logMessage(`Error inserting node: ${err.message}`, 'error');
    }
}

function deleteNode() {
    const value = parseInt(document.getElementById('nodeValue').value);
    if (isNaN(value)) return;
    
    if (tree.delete(value)) {
        logMessage(`Deleted node ${value}`, 'success');
        updateVisualization();
    } else {
        logMessage(`Value ${value} not found in the tree`, 'error');
    }
}

function resetTree() {
    tree = new RedBlackTree();
    logMessage('Tree reset', 'info');
    updateVisualization();
}

function startChallenge() {
    challengeMode = true;
    errorCount = 0;
    
    // Generate a target challenge (e.g., insert nodes to create a specific structure)
    challengeTarget = generateChallenge();
    logMessage('Challenge mode activated! Try to match the target structure.', 'info');
}

function toggleManualMode() {
    manualMode = !manualMode;
    logMessage(`Manual mode ${manualMode ? 'enabled' : 'disabled'}`, 'info');
}

function openTab(evt, tabName) {
    const tabcontent = document.getElementsByClassName('tab-content');
    for (let i = 0; i < tabcontent.length; i++) {
        tabcontent[i].classList.remove('active');
    }
    
    const tablinks = document.getElementsByClassName('tab');
    for (let i = 0; i < tablinks.length; i++) {
        tablinks[i].classList.remove('active');
    }
    
    document.getElementById(tabName).classList.add('active');
    evt.currentTarget.classList.add('active');
}

// Visualization using D3.js
const svgWidth = 1000;
const svgHeight = 500;
const nodeRadius = 20;

const svg = d3
    .select('#tree-display')
    .append('svg')
    .attr('width', svgWidth)
    .attr('height', svgHeight);

let tooltip = d3.select('body').append('div')
    .attr('class', 'tooltip');

function updateVisualization() {
    svg.selectAll('*').remove();
    
    if (!tree.root) {
        svg
            .append('text')
            .attr('x', svgWidth / 2)
            .attr('y', svgHeight / 2)
            .attr('text-anchor', 'middle')
            .text('Tree is empty');
        return;
    }
    
    const treeLayout = d3.tree().size([svgWidth - 100, svgHeight - 100]);
    const root = d3.hierarchy(tree.root, (d) => [d.left !== tree.NIL ? d.left : null, d.right !== tree.NIL ? d.right : null].filter(Boolean));
    const treeData = treeLayout(root);
    
    // Draw links
    svg
        .selectAll('.link')
        .data(treeData.links())
        .enter()
        .append('path')
        .attr('class', 'link')
        .attr('d', d3.linkHorizontal()
            .x((d) => d.x + 50)
            .y((d) => d.y + 50)
        );
    
    // Draw nodes
    const nodes = svg
        .selectAll('.node')
        .data(treeData.descendants())
        .enter()
        .append('g')
        .attr('class', 'node')
        .attr('transform', (d) => `translate(${d.x + 50}, ${d.y + 50})`);
    
    nodes
        .append('circle')
        .attr('r', nodeRadius)
        .style('stroke', (d) => (d.data.color === 'RED' ? 'red' : 'black'))
        .style('fill', (d) => (d.data.color === 'RED' ? '#ffcccc' : '#dddddd'))
        .on('mouseover', function (event, d) {
            tooltip.transition()
                .duration(200)
                .style('opacity', .9);
            tooltip.html(`Value: ${d.data.value}
Color: ${d.data.color}`)
                .style('left', (event.pageX + 10) + 'px')
                .style('top', (event.pageY - 28) + 'px');
        })
        .on('mouseout', function () {
            tooltip.transition()
                .duration(500)
                .style('opacity', 0);
        });
    
    nodes
        .append('text')
        .attr('dy', 4)
        .text((d) => d.data.value);
}

// Log messages
function logMessage(message, type = 'info') {
    const log = document.getElementById('message-log');
    const msg = document.createElement('div');
    msg.className = `message ${type}`;
    msg.textContent = message;
    log.appendChild(msg);
    log.scrollTop = log.scrollHeight;
}

function generateChallenge() {
    // Simple challenge: create a balanced tree with specific values
    const values = [50, 25, 75, 12, 37, 62, 87];
    resetTree();
    values.forEach(v => tree.insert(v));
    updateVisualization();
    return values;
}

// Initial setup
updateVisualization();

// Tabs setup
function openTab(evt, tabName) {
    const tabcontent = document.getElementsByClassName('tab-content');
    for (let i = 0; i < tabcontent.length; i++) {
        tabcontent[i].classList.remove('active');
    }
    
    const tablinks = document.getElementsByClassName('tab');
    for (let i = 0; i < tablinks.length; i++) {
        tablinks[i].classList.remove('active');
    }
    
    document.getElementById(tabName).classList.add('active');
    evt.currentTarget.classList.add('active');
}