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.

One 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. Reset clears the trace while keeping inputs. Editing the sequence or tree type clears the old result. The RB repair example selects the red–black variant; other sequence examples preserve the chosen type. Valid inputs and speed are saved; navigation starts idle. Large trees scroll locally without shrinking labels. Balanced-tree insertion is O(log n); generating independent snapshots and drawing them adds separate work in this bounded visualizer.

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