Left-Leaning Red-Black (2,3) Tree Operations
A left-leaning red-black tree has the property that all red nodes without
siblings (corresponding to 3-child nodes in (2,4) and (2,3) trees) are left
children. In a (2,3) tree, therefore, these are the only red nodes. The
algorithms for insertion and deletion are particularly simple in this case,
without any significant loss of speed over the general, more permissive
red-black tree representation. Our implementation is based on
Left-leaning
Red-Black Trees by Robert Sedgewick of Princeton University.
The space below allows you to interactively try out
several basic operations on a red-black search tree:
- Typing a number into the
“Value to insert” box (followed by “Enter”) adds it to the tree.
- Double-clicking a tree node removes it from the tree.
You can back up or redo an operation using the “<<” and
“>>” buttons.
Tree nodes that become unreachable (“garbage”) fall out of the
demonstration space.