{{ statusTitle }}
{{ statusValue }}

{{ summaryLine }}

Policy{{ policyName }} Nodes{{ nodeCount }} Invariant{{ invariantReport.ok ? 'Verified' : 'Failed' }}
Choose the invariant policy the reducer must preserve after each mutation.
Load a complete example, then inspect or edit every queued operation.
Use 1–24 operations. Keys are unique integers from −999 through 999.
{{ rows.length }} / 24
#OperationValue or orderMove / remove
{{ index + 1 }}
Add one operation
A duplicate insertion is traced but does not change the tree.
{{ playbackSpeed }} ms
Shorter intervals play faster; Step always advances one canonical frame.
Current canonical step

{{ session.current.message }}

Path{{ currentPathKeys.length ? currentPathKeys.join(' → ') : '—' }}
Traversal{{ currentTraversal.length ? currentTraversal.join(', ') : '—' }}
Rotations{{ session.rotation_count }}
Recolors{{ session.recolor_count }}

{{ workflowMessage }}

The diagram renderer is unavailable. The trace and operation ledger remain usable.

#OperationOutcomeNodesInvariantCopy
{{ row.index }}{{ row.operation }}{{ row.outcome }}{{ row.nodeCount }}{{ row.invariant }}
Linear Data Structure Operations Simulator Trace list, stack, queue, and deque operations across linked and bounded-array representations with endpoint and invariant evidence.
Heap Operations Simulator Build min or max heaps and trace insert, peek, and extract operations with synchronized array and tree views plus comparison and swap counts.
Hash Table Operations Simulator Trace hash-table insert, search, and delete operations across chaining and probing strategies with collision and tombstone evidence.
Search Algorithm Simulator Compare four search methods with repeatable probe traces and see how candidate ranges, data order and duplicates affect first-match or miss results.

A binary search tree stores each unique key so that smaller keys lie in the left subtree and larger keys lie in the right subtree. That ordering turns search, insertion, and deletion into a chain of comparisons rather than a scan of every node. The shape of the tree determines how long that chain becomes.

Insertion order can make an ordinary binary search tree broad or nearly linear. Adding already sorted keys, for example, can create a one-sided tree that loses much of the advantage of hierarchical search. AVL and red-black trees preserve the same key ordering while applying rotations, and sometimes color changes, to limit that shape problem after mutations.

PolicyInvariant beyond key orderTypical teaching focus
Ordinary BSTNo balance condition.Comparison paths, insertion position, successor-based deletion, and traversal.
AVL treeThe left and right subtree heights of every node differ by at most one.Height updates and single or double rotations.
Red-black treeRoot color, red-parent, and equal black-height rules constrain the shape.Rotation, recoloring, and insertion or deletion fix-up cases.

Deletion exposes the largest structural difference from search. Removing a leaf only cuts one link. Removing a node with one child reconnects that child to the parent. With two children, the in-order successor supplies the replacement position before the affected balance rules are repaired.

Traversal answers a different question from search. In-order visits a binary search tree's keys from smallest to largest. Pre-order visits a node before its subtrees, post-order visits it after both subtrees, and level-order visits breadth by breadth from the root.

A final tree diagram can hide the work that produced it. A stepwise trace makes comparisons, relinking, rotations, recoloring, and invariant checks visible, which is especially useful when two algorithms finish with the same sorted keys but different shapes.

How to Use This Tool:

Build one bounded operation queue and keep the tree policy fixed for the whole run.

  1. Choose Ordinary BST, AVL tree, or Red-black tree, or load a complete preset for the case you want to study.
  2. Add 1–24 insert, search, delete, or traverse operations. Keys must be unique integers from −999 through 999; duplicate insertion is traced but does not add another node.
  3. Start from the empty tree. Correct an invalid value, traversal order, or queue size before starting the session.
  4. Use Step for one canonical frame, or play continuously. A shorter Playback interval runs faster without changing the frames or final tree.
  5. Pause to inspect the current comparison path or mutation, then resume or finish the trace. Complete the run before using Replay same queue.
  6. Check the trace message, tree diagram, operation ledger, and final invariant status before explaining the result.

Interpreting Results:

The highlighted path records the comparisons or visits used by the current frame. Rotations and recolorings are counted separately because they change balance without changing the sorted key set. Invariant verified means the current topology satisfies strict key order, valid parent links, acyclic structure, and the selected balance policy.

  • A search or delete miss reaches an empty link and leaves the tree unchanged.
  • A duplicate insertion is rejected by the unique-key policy and also leaves the tree unchanged.
  • An in-order traversal should list the keys in ascending order. If it does not, the ordering invariant has failed.
  • Replay starts again from an empty tree with the same queue and policy, so its canonical trace should match the completed run.

Technical Details:

Every operation first follows the strict comparison rule. A smaller key takes the left link, a larger key takes the right link, and equality ends a search or rejects a duplicate insertion. Mutations finish with a fresh invariant report before the operation enters the ledger.

Rule Core:

Rule setOrdered decision logicVerified condition
Search and insertionCompare at the root; follow left for a smaller key and right for a larger key until equality or an empty link.Every left key is smaller and every right key is larger than its ancestor bounds.
Ordinary deletionRemove a leaf, transplant the only child, or replace a two-child node through its minimum right-subtree successor.Ordering, parent links, and acyclic structure remain valid.
AVL repairRecompute heights upward. Balance factor > 1 repairs the left-heavy side; balance factor < −1 repairs the right-heavy side. An inward-heavy child triggers the first half of a double rotation.For every node, |left height − right height| ≤ 1.
Red-black insertionInsert red, then handle a red parent by recoloring a red uncle or rotating the inner and outer cases. Finish with a black root.No red node has a red child, all root-to-empty paths have equal black height, and the root is black.
Red-black deletionRelink the target or successor, then repair any lost black height with sibling-color, nephew-color, recoloring, and rotation cases.The red-parent, black-height, root-color, and ordering rules all hold.
TraversalUse node-left-right for pre-order, left-right-node for post-order, left-node-right for in-order, or a breadth-first queue for level-order.The visit list contains each reachable node once in the selected order.

AVL height uses an empty subtree height of −1, so a leaf has height 0. Its balance factor is left height minus right height. Values above 1 or below −1 require repair. Red-black balance uses node color instead of an exact height difference; its looser constraint permits different valid shapes for the same key set.

The simulator accepts at most 31 stored nodes. The limit keeps the diagram and frame sequence usable for learning. A queue may contain up to 24 operations, and a single operation may expand into several comparison, height, rotation, recoloring, relinking, or visit frames.

Formula Core is deliberately omitted because the governing mechanism is ordered comparison and invariant repair, not a numeric result. Step, rotation, recoloring, and node totals are event counts produced by the Rule Core.

Worked Examples:

AVL left-left insertion

Insert 30, 20, then 10. Node 30 reaches a balance factor of 2, with the extra height on its left child's left side. A right rotation promotes 20, leaving 10 and 30 as its children. The run records one rotation and ends with all AVL bounds verified.

Red-black outer repair

Insert 10, 5, then 1. The third insertion creates a red parent with no red uncle. A right rotation at 10 promotes 5, then recoloring leaves 5 black with red children 1 and 10. The verified trace records one rotation and three color changes across the run.

Limitations:

This is a bounded teaching model, not a benchmark or a code generator. Playback speed affects only presentation, and operation counts should not be treated as measured runtime.

  • Duplicate keys are not stored, so multiset or duplicate-key policies are outside scope.
  • The diagram shows canonical node links and colors, not memory addresses or a specific programming-language implementation.
  • Production trees may use different deletion details, sentinel nodes, metadata, or concurrency rules while preserving the same mathematical invariants.

References:

  • Binary search tree, NIST Dictionary of Algorithms and Data Structures, modified 30 August 2021.
  • AVL tree, NIST Dictionary of Algorithms and Data Structures, modified 12 November 2019.
  • Red-black tree, NIST Dictionary of Algorithms and Data Structures, modified 12 November 2019.