Red black trees are binary trees with additional information, each node not only holds a value, and pointers to left and right children, it also stores a color, red or black. The purpose of the color is to ensure that the tree remains balanced (mostly) while performing insertions and deletions. Whenever an insertion or deletion operation is performed the tree is re-balanced to satisfy the rules that make it a Red-Black tree. **Properties** Red Black Trees inherit all of the properties of Binary Search Trees, and add a few more: 1. Each node is either Red or Black 2. The root node is black 3. All leafs are black 4. If a node is red, then both its children are black 5. All paths from a single node go through the same number of black nodes to reach any of its `NIL` nodes. The benefit of implementing RB Trees over just Binary Search Tree is that unlike BST, RB Trees are almost always balanced and therefore operations like insertions or deletions always perform at `0(log(n))` time. ## Implementation ### Insert First lets start with the basic structure for the RB Tree. We start by defining the nodes that make up the tree, and then the actual structure for the tree. Here the `nil` nodes are used by RB Trees to help in the re-balancing process but otherwise contain so useful values. ```python class RBNode: def __init__(self, val): self.red = False self.parent = None self.val = val self.left = None self.right = None class RBTree: def __init__(self): self.nil = RBNode(None) self.nil.red = False self.nil.left = None self.nil.right = None self.root = self.nil ``` The insert method adds the following the to `RBTree` class: ```python def insert(self, val): # set up new node for inserting, we use the val we want to insert # and initialize left and right to be nil new_node = RBNode(val) new_node.left = self.nil new_node.right = self.nil new_node.red = True # parent will eventually hold the actual parent of new_node or will # remain None parent = None # start the iteration at the top of the tree current = self.root while current is not self.nil: parent = current if new_node.val < current.val: current = current.left elif new_node.val > current.val: current = current.right else: return new_node.parent = parent # when the parent remained None then the new_node will be the root if parent is None: self.root = new_node elif new_node.val < parent.val: parent.left = new_node else: parent.right = new_node ``` In the first part of this method we create a `new_node` with with its value set to the value we want to insert. In addition to this we set its children left and right to be nil, as well ask make it red. Next we seek to find the its parent (i.e where in the tree we can slot in this node based on its value alone). We do this by starting at the root node and iterating through all nodes following the left or right children based on the value comparisons. Once the loop is done we either found the parent and stored it in the `parent` variable or never found the parent in which case the node we are trying to insert is the root node. ### Rotate Finding a place for the `new_node` is not the final step in the process when it comes to RB Trees, we need always make sure the tree is balanced after we insert or delete a node. So the next few things we need to do are implement methods for balancing the tree. These new methods will allow us to rotate the tree left and right. ![[Pasted image 20240427224818.png]] ```python def rotate_left(self, x): if x is self.nil: return if x.right is self.nil: return # let y be x's right child y = x.right # set x's right child to be the y's left child x.right = y.left # If y's left child isn't a nil leaf node, set y's left-child's parent to x if y.left is not self.nil: y.left.parent = x # Set y's parent to x's parent y.parent = x.parent # If x is the root, set the root to y if x is self.root: self.root = y elif x is x.parent.left: x.parent.left = y elif x is x.parent.right: x.parent.right = y y.left = x x.parent = y def rotate_right(self, x): if x is self.nil: return if x.left is self.nil: return y = x.left x.left = y.right if y.right is not self.nil: y.right.parent = x y.parent = x.parent if x is self.root: self.root = y elif x is x.parent.left: x.parent.left = y elif x is x.parent.right: x.parent.right = y y.right = x x.parent = y ``` Lets break this down. Lets go over the left rotation. The first thing we do is check for some special cases, when either `x` is a `nil` leaf node or the right child `y` in this case is a `nil` leaf node. In each of these cases we just return. We need `y` (x's right child) to be non nil since this is the node that will pivot about the x node. Next we just set `y = x.right` and proceed to move x's right child to be y's left child `x.left = y.right`. This leaves the y node with only a right child, and breaks the connection between x and y. If this shift results in moving a non-nil node then we need make sure to set the parent of the node that got moved to x, we do this with: ```python if y.left is not self.nil: y.left.parent = x ``` Next we set y's parents to be x's parents, this will remove the connection that x has with its parent node and replace it with y. Now step through a few special cases. 1. If x was the root, set y to be the root within our `RBTree` data structure `self.root = y` 2. Else if x is the left child of the parent then make this point to y now 3. Else if x is the right child of the parent then make this point to y now And lastly we make sure to update the pointer references that make y's right child point to x and x parents pointer point to y. The right rotation is a mirrored version of this implementation, shown above in code but not explained. ### Fix Insert The last step is go through the new tree structure and fix the colors of all the nodes, we do this by implementing the `fix_insert` metthod: ```python def fix_insert(self, new_node): while new_node is not self.root and new_node.parent.red == True: if new_node.parent.is_right_child(): uncle = new_node.parent.parent.left if uncle.red: uncle.red = False new_node.parent.red = False new_node.parent.parent.red = True new_node = new_node.parent.parent else: if new_node.is_left_child(): new_node = new_node.parent self.rotate_right(new_node) new_node.parent.red = False new_node.parent.parent.red = True self.rotate_left(new_node.parent.parent) elif new_node.parent.is_left_child(): uncle = new_node.parent.parent.right if uncle.red: uncle.red = False new_node.parent.red = False new_node.parent.parent.red = True new_node = new_node.parent.parent else: if new_node.is_right_child(): new_node = new_node.parent self.rotate_left(new_node) new_node.parent.red = False new_node.parent.parent.red = True self.rotate_right(new_node.parent.parent) self.root.red = False ``` This implementation assumes, an update to the node class with two new helper methods: `is_left_child()` and `is_right_child()`. ```python class RBNode: def __init__(self, val): self.red = False self.parent = None self.val = val self.left = None self.right = None def is_left_child(self): return self is self.parent.left def is_right_child(self): return self is self.parent.right ```