AVL / Red–Black Trees

Insert 1–31 signed base-10 integer keys from −9999 to 9999, using at most 512 characters. Commas or whitespace separate keys; empty comma entries and trailing commas are invalid. Leading zeros and an optional plus sign are accepted. Decimal points, exponents, hexadecimal notation and partial numbers are rejected. Duplicate keys are read but skipped: the tree represents a set.

Step shows one actual operation: attaching a new node, a single left or right rotation, a group of color changes, a completed insertion or a skipped duplicate. A double rotation has two separate rotation frames. Rotation counts count individual rotations; recoloring counts count groups that actually change colors, including restoring a black root. Keys read includes the current key from its insertion frame onward. The unique-key count excludes duplicates.

Rotations preserve binary-search order: all keys in the left subtree are smaller, all keys in the right subtree larger. Inorder lists keys from left to right. AVL balance is left height minus right height, between −1 and 1 after each completed insertion. Here an empty subtree has height 0 and a leaf height 1.

The red–black variant uses classic insertion repair, not the left-leaning variant. The root and omitted NIL leaves are black; red nodes have no red children; every path from a node to a NIL leaf has the same black-node count. The node table counts the current node if black and counts the final NIL leaf; NIL alone therefore has black height 1. A dash indicates unequal black heights during repair. Color letters supplement the node colors.

Intermediate snapshots may temporarily violate balance or red–black properties. The summary confirms these only at completed insertion or duplicate boundaries. Outlines mark affected nodes; a dashed outline marks the old subtree root of a rotation. Its promoted child and any moved subtree root are named below the action.

Run resumes a paused trace and restarts a completed trace. Back and Step let you inspect individual operations in both directions. Clear clears the trace while keeping inputs. Editing keys or tree type clears the old result. The RB repair example selects red–black; other examples preserve the type. Enter inserts a newline; Ctrl/Command+Enter runs. Raw inputs, selection, speed, detail sections and current frame are saved locally, including unfinished drafts. Reload or returning within the app restores a valid frame paused; playback never restarts automatically. Large trees scroll locally without shrinking labels. Balanced-tree insertion is O(log n); independent snapshots and drawing add separate work in this bounded visualizer.

Sources: MIT 6.006 (2011), lecture 6, AVL trees; MIT 6.046 (2005), lecture 10, red–black trees.

The current operation and tree are shown first. Trace details contains counters and the sorted key list; node details opens the locally scrollable table. Pause appears only during playback. The step count is shown while operations remain, and disappears when finished.

Local storage holds at most 100000 serialized characters. Above this limit, the previous saved copy is retained; download the complete keys before reloading or leaving the page. In-app navigation retains the live draft. Traces use at most 31 keys and 512 characters; longer drafts remain editable but are rejected when running. Legacy saved inputs are supported; old versions did not store frames.