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: You can back up or redo an operation using the “<<” and “>>” buttons. Tree nodes that become unreachable (“garbage”) fall out of the demonstration space.

Fast Slow

Value to insert: