Clairvoyant

Red-Black Tree Documentation

This documentation refers to the Red-Black Tree problem. Your solution class will automatically extend RBTSolution, and must implement the following methods:

Your script should evaluate to the prototype of your defined class.

At present, your code is run as-is on your web client. Long-running or infinite loops will therefore crash your web client. Take appropriate actions to mitigate this issue when writing custom code.

c
class
RBTSolution

f
function
constructor(tree : RBTree)

The constructor receives the RBTree instance. Use it to store a reference to the tree for later use.

f
function
insert(key : number) : void

Called when the user requests an insertion. You should implement the full RB-INSERT algorithm including the fixup procedure.

Use this.tree.makeNode(key) to create a new node, then use the visualization methods below to animate each step.

f
function
delete(key : number) : void

Called when the user requests a deletion. You should implement the full RB-DELETE algorithm including the fixup procedure.

Use this.tree.search(key) to find the node to delete.

Visualization Methods

These methods are inherited from the base class. Call them from your algorithm to animate operations step by step. Each method auto-generates a descriptive message from its arguments. You can override or customize these messages using the annotation system.

Prefer the transaction helpers for rotations, transplant, and delete rewires. They keep the tree connected, move edges before nodes when appropriate, and produce more stable layouts for the visualizer.

f
function
insertNode(z : RBNode) : void

Inserts a node into the tree using standard BST insertion (walks the tree to find the correct position). The insertion is animated in the visualizer.

f
function
removeNode(z : RBNode) : void

Marks a node as removed from the visualization. In the current transaction model, this should be the point where the deleted node actually disappears from the rendered tree.

f
function
recolor(node : RBNode, color : RBColor) : void

Changes the color of a node. Use "RED" or "BLACK" as the color value.

f
function
rotateLeftTransaction(x : RBNode, y : RBNode) : void

Animates a full left rotation as one coordinated transaction. The visualizer first rewires the affected edges, then relayouts the connected tree as a whole.

f
function
rotateRightTransaction(y : RBNode, x : RBNode) : void

Animates a full right rotation as one coordinated transaction. This is the right-rotation counterpart to rotateLeftTransaction.

f
function
transplantTransaction(oldNode : RBNode, newNode : RBNode) : void

Animates transplant as a tree-connected replacement step.

f
function
moveEdgeTransaction(parent : RBNode, side : string, child : RBNode, carryNodes : RBNode[] = []) : void

Moves one child edge as a transaction-aware visual step. This is useful in delete/transplant flows where an edge should move coherently and some nodes must remain visible until a later removeNode call.

side must be "left" or "right". Pass affected nodes in carryNodes if they should remain visible through the transaction even after they stop being reachable from the root.

f
function
setRoot(node : RBNode) : void

Sets the tree's root to the given node.

f
function
trackPointer(name : string, node : RBNode) : RBNode

Highlights a node in the visualizer with a labeled pointer (e.g. "z", "x", "uncle"). The label appears above the node and is shown in the watch panel. Returns the node argument, so you can combine assignment and tracking in a single expression:

let w = this.trackPointer("w", x.parent.right);

f
function
clearPointer(name : string) : void

Removes a previously tracked pointer label.

f
function
logStep(ctx : object = undefined) : void

Records a narrative step without performing any tree mutation. The message is pulled from the line annotation and evaluated with the optional ctx object merged into the template context. Pass local variables that should be available in the annotation template, e.g. this.logStep({key}).

f
function
logCase(label : string) : void

Records a fixup case entry. The label (e.g. "Insert Case 1") is displayed in a color-coded badge in the top-right corner of the viewport. The badge tracks all cases encountered during the current operation and can be expanded to see the full history. Cases are cleared automatically when a new insert or delete begins.

f
function
done(ctx : object = undefined) : void

Marks the operation as complete. Call this at the end of insert and delete. Like logStep, accepts an optional context object for the annotation template.

c
class
Annotations

The annotation system lets you add descriptive messages and branch explanations to algorithm lines without cluttering the code. Messages are stored separately and can be edited interactively.

How it works

  • Each visualization method auto-generates a message from its arguments (e.g. moveEdgeTransaction(parent, "left", child) produces "Move parent.left edge to child").
  • An annotation can override the auto-generated message for any line.
  • Annotations on if/else if/else lines define branch Q&A that is displayed automatically when execution enters that branch.
  • Default annotations ship alongside the algorithm in a .annotations.json file.

Using the gutter UI

A small icon column appears to the right of line numbers in the code editor:

  • ● (blue dot) — this line has a message annotation.
  • ◆ (yellow diamond) — this is a branch line with a Q&A annotation.
  • Hover to reveal a + icon on unannotated lines.
  • Click any icon to open the popover editor.

Template syntax

Annotation messages use JavaScript template literal syntax (${...}). The following variables are available:

  • Method arguments — for viz methods, the parameter names are available (e.g. parent, child for moveEdgeTransaction, or oldNode, newNode for transplantTransaction).
  • Tracked pointers — all currently tracked pointers by name (e.g. z, x, uncle). These are RBNode objects, so you can access .key, .color, .isNil, etc.
  • tree — the RBTree instance.
  • NIL — the tree's NIL sentinel.
  • For logStep and done, any variables passed in the ctx argument.

If a template expression throws an error, the raw template string is displayed as a fallback.

Branch annotations

Branches are detected automatically from if/else if/else lines. When a visualization method fires inside a branch body and there is an annotation on the enclosing branch line with question and answer fields, a branch step is automatically inserted before the visualization step. This replaces the old this.branch() method.

Annotation storage

Annotations are stored as content-anchored entries (keyed by function name and trimmed line content, not line numbers), making them resilient to code edits. User edits persist for the current session. Defaults can be restored via the "Reset" button in the popover.

c
class
RBTree

The red-black tree instance. Accessed via this.tree in your solution.

p
property
root : RBNode

The root node of the tree. Equals tree.NIL when the tree is empty.

p
property
NIL : RBNode

The sentinel NIL node. All leaf pointers and the root's parent point to this node. Its color is always BLACK.

f
function
makeNode(key : number) : RBNode

Creates a new node with the given key. The node starts with both children and parent set to NIL.

f
function
search(key : number) : RBNode

Searches for a node with the given key. Returns the node if found, or tree.NIL if not found.

f
function
minimum(node : RBNode) : RBNode

Returns the node with the smallest key in the subtree rooted at the given node.

f
function
allNodes() : RBNode[]

Returns an array of all reachable nodes in the tree (excluding NIL).

c
class
RBNode

A node in the red-black tree.

p
property
key : number

The integer key stored in this node.

p
property
color : RBColor

The color of this node: "RED" or "BLACK".

p
property
left : RBNode

The left child. Equals tree.NIL if there is no left child.

p
property
parent : RBNode

The parent node. Equals tree.NIL for the root node.

p
property
isNil : boolean

Returns true if this node is the NIL sentinel.