What is a Red-Black Tree?

A red-black tree is a binary search tree data structure , i.e. most of the common

operations (such as insert, delete, find etc.) are performed in O(h) time where h is

tree height.

In a red-black tree each node has a color which can be either Red or Black.

The also contains a NULL object which is black, and for each node if its parent or

children do not exist, it should point to the tree null object.

Properties satisfied by a red-black tree:

1. Every node is either red or black.

2. Every leaf is black(i.e. every leaf is the tree null object).

3. Every red node has two black children.

4. Every simple path from a node to a descendant leaf contains the same

number of black nodes.

Satisfing this properties leads to:

---

A Red-Black tree with n nodes has height at most 2lg(n+1).

---

i.e. most of the common operations are performed in O(lg n).

The Simulation

The simulator illustrates how the operations: Insert and Delete done in

a red-black tree.

With the simulator one can build a red-black tree by inserting and deleting

nodes.

All the steps of the operations are visual so one can really see how the operations

are done.

Press the button to start simulation

The Simulation Sources

Quick HELP:

• To start the simulation you should press the 'Start Simulation' button. This open the simulation window.
• Information on the current operation is given in the 'Info' line.
• The diagram on the upper right corner show the height of the this tree relative to a balanced search tree.
• Buttons:
• Demo: Show a series of insertion and deletion operations. The demo can be started only if the tree is empty (if the tree isn't empty, clear it first).
• Insert: Raise a window for user input (integer between 0 to 99) to be inserted to the tree.
• Delete: Raise a window for user input (integer between 0 to 99) to be deleted from the tree.
• Next: Use to move to the next step in the operation (either insert or delete.)
• Clear: Use to clear the current tree.
• Exit: Exit the simulation.