A Red-Black Tree is a type of binary search tree that automatically keeps itself balanced. It uses a color system (Red or Black) for its nodes and follows strict rules to make sure searching, inserting, and deleting data stays very fast.
- Node Color: Every node is either Red or Black.
- Root Rule: The root node is always Black.
- Leaf Rule: All NIL leaves (empty external nodes) are Black.
- Red Node Rule: If a node is Red, then both its children must be Black (no two Red nodes can be adjacent vertically).
- Black Path Rule: For each node, all simple paths from the node to descendant leaves must contain the same number of Black nodes.
leftRotate()&rightRotate(): These functions turn parts of the tree around a specific node to fix the tree structure and maintain balance when the red-black rules are broken.insert(): Adds a new piece of data into the tree in the correct position as a Red node, then calls a helper function to fix any color or balancing issues.insertFixUp(): Checks the colors of nearby nodes after an insertion. It recolors nodes or performs rotations to restore the red-black properties.rbDelete(): Removes a specific node from the tree and handles the restructuring process if a Black node is deleted.deleteFixUp(): Restores the tree's balance and fixes color violations after a node is removed.search(): Looks for a specific value in the tree by comparing values and moving left or right through the nodes.inorder(): Walks through the entire tree from left to right to print out all the stored data in sorted order.
Compile the file using a C++ compiler:
g++ RedBlackTree.cpp -o rbt_program