import React, { useState, useEffect, useRef, useMemo } from 'react'; import { motion, AnimatePresence } from 'framer-motion'; // --- Constants & Config --- const VIEW_WIDTH = 1200; const VIEW_HEIGHT = 700; const NODE_RADIUS = 24; const LEVEL_HEIGHT = 90; const ANIM_SPEED = 1.2; // Speed multiplier (higher is slower) // Colors const COLORS = { bg: '#0f172a', grid: '#1e293b', text: '#f8fafc', textSub: '#94a3b8', redNode: '#ef4444', redNodeGlow: '#f87171', blackNode: '#0f172a', blackNodeStroke: '#06b6d4', link: '#475569', highlight: '#eab308', consoleBg: '#020617', consoleBorder: '#1e293b' }; // --- Data Structures --- type NodeType = 'RED' | 'BLACK'; interface TreeNode { id: number; value: number; type: NodeType; left: TreeNode | null; right: TreeNode | null; parent: TreeNode | null; // Visual props x: number; y: number; isNew?: boolean; highlight?: boolean; } interface VisualNode { id: number; value: number; type: NodeType; x: number; y: number; parentId: number | null; isNew: boolean; highlight: boolean; } interface LogMessage { id: number; text: string; type: 'info' | 'action' | 'success' | 'warning'; } // --- Helper Functions --- const sleep = (ms: number) => new Promise(resolve => setTimeout(resolve, ms * ANIM_SPEED)); // --- Main Component --- export default function RedBlackTreeAnimation() { // --- State --- const [visualNodes, setVisualNodes] = useState([]); const [logs, setLogs] = useState([]); const [currentAction, setCurrentAction] = useState("Initializing System..."); // Refs for logic (to avoid stale closures in async loop) const treeRootRef = useRef(null); const isMountedRef = useRef(true); const logCounterRef = useRef(0); // --- Layout Logic --- // Calculate X/Y coordinates for the entire tree const updateLayout = (root: TreeNode | null) => { if (!root) return []; const nodes: VisualNode[] = []; // Recursive layout calculator // We use a dynamic width approach based on depth const calculatePos = (node: TreeNode, x: number, y: number, offset: number) => { node.x = x; node.y = y; nodes.push({ id: node.id, value: node.value, type: node.type, x: node.x, y: node.y, parentId: node.parent ? node.parent.id : null, isNew: !!node.isNew, highlight: !!node.highlight }); if (node.left) { calculatePos(node.left, x - offset, y + LEVEL_HEIGHT, offset / 1.8); } if (node.right) { calculatePos(node.right, x + offset, y + LEVEL_HEIGHT, offset / 1.8); } }; calculatePos(root, VIEW_WIDTH / 2, 80, VIEW_WIDTH / 4.5); return nodes; }; const refreshView = () => { const nodes = updateLayout(treeRootRef.current); setVisualNodes(nodes); }; const addLog = (text: string, type: LogMessage['type'] = 'info') => { const id = logCounterRef.current++; setLogs(prev => [...prev.slice(-4), { id, text, type }]); // Keep last 5 logs }; // --- Red-Black Tree Logic Engine --- useEffect(() => { isMountedRef.current = true; // Simulation Sequence const runSimulation = async () => { await sleep(1000); // Input sequence designed to trigger various RB cases // 10, 20, 30 -> Left Rotate // 15 -> Recolor // 25 -> RL Rotation // 5, 1 -> Right Rotate const sequence = [10, 20, 30, 15, 25, 5, 1]; for (const val of sequence) { if (!isMountedRef.current) return; setCurrentAction(`Inserting Node: ${val}`); addLog(`Request: Insert value ${val}`, 'action'); await sleep(800); await insert(val); await sleep(1000); } setCurrentAction("Tree Balanced. Sequence Complete."); addLog("All operations finished successfully.", 'success'); }; // --- RB Tree Operations (Async for Animation) --- const insert = async (value: number) => { // 1. Standard BST Insert const newNode: TreeNode = { id: value, // Using value as ID for simplicity in this demo value, type: 'RED', // New nodes are always red left: null, right: null, parent: null, x: VIEW_WIDTH / 2, // Start at root pos visually y: 80, isNew: true }; if (!treeRootRef.current) { newNode.type = 'BLACK'; // Root is always black treeRootRef.current = newNode; addLog(`Root created: ${value} (Black)`, 'success'); refreshView(); return; } let current = treeRootRef.current; let parent: TreeNode | null = null; // Traverse to find spot while (current) { parent = current; // Visual traversal effect could go here if (value < current.value) { current = current.left!; } else { current = current.right!; } } // Link new node newNode.parent = parent; if (parent) { if (value < parent.value) parent.left = newNode; else parent.right = newNode; } addLog(`Inserted ${value} as RED child of ${parent?.value}`, 'info'); refreshView(); await sleep(800); // 2. Fix Violations newNode.isNew = false; // Stop pulsing await fixViolation(newNode); }; const fixViolation = async (node: TreeNode) => { let current = node; while (current.parent && current.parent.type === 'RED') { const parent = current.parent; const grandParent = parent.parent; // Should theoretically always exist if parent is Red (since Root is Black) if (!grandParent) break; parent.highlight = true; current.highlight = true; refreshView(); await sleep(600); if (parent === grandParent.left) { const uncle = grandParent.right; // Case 1: Uncle is RED -> Recolor if (uncle && uncle.type === 'RED') { addLog("Case 1: Parent & Uncle are RED -> Recolor", 'warning'); setCurrentAction("Fix: Recolor Parent, Uncle & GP"); parent.type = 'BLACK'; uncle.type = 'BLACK'; grandParent.type = 'RED'; parent.highlight = false; current.highlight = false; refreshView(); await sleep(1000); current = grandParent; // Check upwards } else { // Case 2: Uncle is BLACK (or null) // Case 2a: Triangle (Left-Right) -> Rotate Left if (current === parent.right) { addLog("Case 2: Triangle (LR) -> Rotate Left", 'warning'); setCurrentAction("Fix: Left Rotation on Parent"); current = parent; // Move pointer up for next step await rotateLeft(current); // Now we are in Case 3 (Line) } // Case 3: Line (Left-Left) -> Rotate Right addLog("Case 3: Line (LL) -> Rotate Right", 'warning'); setCurrentAction("Fix: Right Rotation on GP"); // Recolor first if (current.parent) current.parent.type = 'BLACK'; // Parent becomes Black grandParent.type = 'RED'; // GP becomes Red refreshView(); await sleep(800); await rotateRight(grandParent); } } else { // Mirror of above (Parent is Right Child) const uncle = grandParent.left; if (uncle && uncle.type === 'RED') { addLog("Case 1: Parent & Uncle are RED -> Recolor", 'warning'); setCurrentAction("Fix: Recolor Parent, Uncle & GP"); parent.type = 'BLACK'; uncle.type = 'BLACK'; grandParent.type = 'RED'; parent.highlight = false; current.highlight = false; refreshView(); await sleep(1000); current = grandParent; } else { if (current === parent.left) { addLog("Case 2: Triangle (RL) -> Rotate Right", 'warning'); setCurrentAction("Fix: Right Rotation on Parent"); current = parent; await rotateRight(current); } addLog("Case 3: Line (RR) -> Rotate Left", 'warning'); setCurrentAction("Fix: Left Rotation on GP"); if (current.parent) current.parent.type = 'BLACK'; grandParent.type = 'RED'; refreshView(); await sleep(800); await rotateLeft(grandParent); } } // Clear highlights if (parent) parent.highlight = false; if (current) current.highlight = false; } // Ensure root is always black if (treeRootRef.current && treeRootRef.current.type === 'RED') { treeRootRef.current.type = 'BLACK'; addLog("Final check: Painting Root BLACK", 'info'); refreshView(); } }; const rotateLeft = async (node: TreeNode) => { const rightChild = node.right!; node.right = rightChild.left; if (node.right) { node.right.parent = node; } rightChild.parent = node.parent; if (!node.parent) { treeRootRef.current = rightChild; } else if (node === node.parent.left) { node.parent.left = rightChild; } else { node.parent.right = rightChild; } rightChild.left = node; node.parent = rightChild; refreshView(); await sleep(1000); }; const rotateRight = async (node: TreeNode) => { const leftChild = node.left!; node.left = leftChild.right; if (node.left) { node.left.parent = node; } leftChild.parent = node.parent; if (!node.parent) { treeRootRef.current = leftChild; } else if (node === node.parent.right) { node.parent.right = leftChild; } else { node.parent.left = leftChild; } leftChild.right = node; node.parent = leftChild; refreshView(); await sleep(1000); }; runSimulation(); return () => { isMountedRef.current = false; }; }, []); // --- Render Helpers --- // Generate SVG paths for links const links = useMemo(() => { return visualNodes.map(node => { if (node.parentId === null) return null; const parent = visualNodes.find(n => n.id === node.parentId); if (!parent) return null; return { id: `link-${parent.id}-${node.id}`, x1: parent.x, y1: parent.y, x2: node.x, y2: node.y, isHighlight: node.highlight || parent.highlight }; }).filter(Boolean); }, [visualNodes]); return (

{/* Background Grid */} {/* Main SVG Visualization */} {/* UI Overlay: Title & Status */}

RED-BLACK TREE VISUALIZER

STATUS: {currentAction}

{/* UI Overlay: Console Log */}

SYSTEM LOGS v1.0.4

{logs.map((log) => { let color = COLORS.textSub; if (log.type === 'action') color = '#38bdf8'; if (log.type === 'warning') color = '#fbbf24'; if (log.type === 'success') color = '#4ade80'; return ( {`>`} {log.text} ); })}

{/* Legend */}

Red Node

Black Node

); }