> See also: > - Reference # Red-Black Trees > [Introduction to Red-Black Trees (GG)](https://www.geeksforgeeks.org/introduction-to-red-black-tree/) > [RB-Tree Visualization/Sandbox](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html) While AVL trees are more balanced compared to Red-Black Trees, they have the potential to cause more rotations during the insertion or deletion process. RB-Trees are considered a loosely balanced data structure, as the conditions they must meet are not as strict, sacrificing a perfect balance for a reduced number of rotations/fixes that are required. ![[Pasted image 20240215181322.png|400]] > [!NOTE] **Properties of RB-Trees** > 1. Every node is either red or black. > 2. The root and leaves (NIL) are black. > 3. If a node is red, then both children are black. > 4. All paths from any given node to its NIL descendants will contain the same number of black nodes. When counting the number of black nodes in a path, it is known as the **black-height** of the red-black tree (the starting node of the path is never counted). The *longest path* (root → furthest NIL leaf) is *no more than twice* the length of the shortest path (root → nearest NIL leaf). - The shortest path possible will consist of only black nodes, while the longest will alternate between red and black. - Because the black-height of both paths must be identical, we can conclude that height of the alternative path will be twice as long The height of an RB-Tree is never greater than $2\log_2 n$, where $n$ is the number of nodes. ## RB-Tree Operations Additional Properties It’s important to note that uncle nodes within an RB-Tree can be NIL nodes (black) - While property #3 does imply - the root can still contain two black children - a black node can have up to two black children if they are NIL leaves ### Searching Finding Minimum - keep going left Finding Maximum - keep going right ### Insertion Let $Z$ be a new node to be inserted. The broad process of inserting a node is: 1. Insert $Z$ via BST insertion and color it RED. 2. Recolor and rotate nodes to fix violations #### Case 0 > **Case 0:** $Z$ is the root. 1. Simply recolor $Z$ black. Occurs when the tree is empty. #### Case 1 > **Case 1:** $Z$ has a *RED uncle*. 1. Recolor $Z$’s parent, grandparent, and uncle - Change $Z$’s parent color status to BLACK. - Change $Z$’s uncle color status to BLACK. - Change $Z$’s grandparent color status to RED 2. Have $Z$ point to its grandparent This will likely percolate upwards with the “check if $Z$’s parent is red” check that occurs after each iteration #### Case 2 > **Case 2:** $Z$ has a *BLACK uncle (triangle)*. 1. Rotate $Z$’s parent in the opposite direction of $Z$. - 2. Proceed immediately to Case 3 and perform rebalancing. #### Case 3 > **Case 3:** $Z$ has a *BLACK uncle (linear)*. 1. Rotate $Z$’s grandparent the opposite direction 2. Recolor the grandparent and parent accordingly This occurs when both $Z$ and its parent are the same type of child (LL or RR imbalance). --- Once we complete an iteration, we check to see if $Z$’s parent (for whatever new $Z$ we have assigned) is red. If it is still red, then the cases will be check again. Cases 2 & 3 share some similarities with how [[AVL Trees]] handle imbalances: - Whenever there is a Left-Right or Right-Left imbalance, two rotations must be performed to correct it. - **Node Coloring Has More Than Meets The Eye** - We can learn information about a node’s position based on it’s color, ### Deletion When performing a deletion, *the main goal is to balance out the black-height* of the RB-tree. > **Basic BST Deletions** > We cannot simply plop out an internal node within a binary search tree. > > Instead, we can use the *successor rule* (or predecessor rule) to swap the target node with the next largest (or smallest) one to *ensure the node being deleted is a leaf*. > > (This does not mean the immediate left or right child) Naturally, a gap would form when a node is removed, either the successor or predecessor rule must be used to decide which child node to promote to the empty spot - This is the typically process taken for any BST deletion - revisit BST deletion function & the new “loop until fixed” RB-Tree function Let $Z$ be a target node to be deleted. #### Case 1 > **Case 1:** $Z$’s sibling is RED. Case 3 & 4 are mutually exclusive