Red Black Tree


Click here to view quick instructions.


Instructions:

Quick Start:

Press Quick Start and the algorithm will run with 10 randomly generated integers.

To create your own input:

Choose how many integers to insert.  1 to 64 integers may be inserted.  Type the number in the space provided and go to the next step.

** Unless you choose Quick Start, you must specify how many inputs you wish to sort before proceeding.

Choose the input to insert from the following.  Input must be integers from 1 to 99.

** Duplicate numbers are not allowed.  If the program detects a duplicate, the number will be automatically replaced by an unused number.

  1. Press the Random button to generate random input.

  2. Press the Reverse button to generate reversely sorted input.

  3. Press the Sorted button to generate sorted input..

  4. Enter your own input.

** Make sure you have the correct number of integers and that your numbers are separated by spaces.  Only integers and spaces are legal input.

Press the Start Animation button to begin.

When the insertions are done, you may use the insert, find, and delete features.  Enter a number to insert, find, or delete in the text field at the top and press the corresponding button.  Remember that a number cannot be inserted that is already in the tree.  The operation must complete before you may begin another one.

Red-Black Tree Properties

  1. Every node is red or black.

  2. The root is black.

  3. If a node is red, its children must be black.

  4. Every path from the root to a leaf or null child must contain the same number of black nodes.

** Special Note:

Some rotations will cause nodes to appear a level below the allowed insertion level.  They will appear and the program can find and delete them, but the user is not allowed to insert other nodes at this level.