Red-Black Trees
The URL /rbtree generates a random Red-Black Tree and allows you to add nodes to it.
You can also generate a specific Red-Black Tree by specifying the nodes you want to insert. You can do this
by using query parameters to specify a comma separated list of nodes, for e.g.,
/rbtree?nodes=2,7,11. Here's a summary of rules to insert a node into a Red-Black Tree.
- The new node is red.
- If the parent of the node is red then we need to fix the violation.
- Find the uncle of the node (the sibling of the parent).
- If the uncle is black (or NIL), we perform rotations to fix the violation.
- Zig-zag configuration of node, parent, and grandparent—two rotations.
- Zig-zig configuration—one rotation.
- If the uncle is red, we recolor the parent and uncle to black and promote the grandparent to red.
This may cause further violations up the tree, so we repeat this process from the grandparent.
Add a Node