wild-inter.net

Binary search trees  ·  and rank-based operations

Small screen: the arrays scroll sideways. The code and the analysis are below the drawing.
Show
Values
Detail
Click a node to use its key. New operations are added right after the one on screen; an empty key field puts a random key.
— / — Delay 650ms
The array zoom100%
compared found / new to be deleted successor not linked in (yet) range still searched (current subtree) count at the upper right, r rank on the left (only in the “why counts” example)
What happens
Call stack (innermost on top)
Results
Java code
Input
Keys are inserted in the order given, as in Sedgewick & Wayne’s tinyST.txt; in key:value mode write K:v. A line init: … builds a starting tree without animation. Operations, one per line or inline: put K, get K, delete K, deleteMin, and with subtree counts also rank K, select i, floor K, ceiling K, min, max, size. Keys: words of up to 3 characters or numbers (not mixed); # starts a comment. In rope mode, the init: line (key:object pairs) builds the tree from the keys, then the keys are forgotten and only the order of the values remains; the operations are insert i x, get i, delete i and size, and a plain word is appended at the end.