Which is terrific! But?..theres a caveat to this. All of the algorithms are based on an assumption that the data is going to come in in a random order. This can quickly become a hinderance if the order in which the inputs are coming in are increasing or decreasing only. Binary search trees add items to themselves down the left if the item being added has a value less than the previous value, and down the right if the item has a value greater more than the previous value. If the values that come in start resembling sorted values this can effectively turn part of our nicely balanced tree into what essentially amounts to a linked list, turning out our nice O(log n) into O(n) and ruining our efficiency
So how do we solve this issue? One approach is to use one of the members in the family data structures known as self-balancing trees, in this case we?ll be focusing on Red-Black trees!
How these trees work and keep their structure
Theory behind red black trees all has to do with colors and rotations. So let?s start there. While a basic binary tree aims just to store inputs as the come and , and hope that these inputs preserve the structure that the tree aims for, Red-black trees aim to keep the order balanced without affecting the complexity of the methods used to perform operations on it. How this is executed in this data structure is by coloring each node in the tree black or red and checking that the deepest path in the tree (the tree height) does not exceed twice the path to the shortest one.
Let?s go over some properties of Red-Black trees!
- Every node has a color that is either black or red.
- Every leaf that does not contain data, but is there to preserve the structure of the tree ( a node with a NULL value) is colored black. These are sometimes referred to as sentinel nodes
- If a node is colored red, then both of its child nodes are colored black.
- Every path down from a node to a descendant leaf should contain the same number of black nodes.
These properties assure that the trees operations will stay a constant O(log n) no matter what order the inputs come in, making this a very efficient algorithm for storage, retrieval, insertion and deletion. With this in mind, let?s take a look at some of the methods!
Red-Black Tree methods with Complexity
- This method is used to check that a given node is ( in most implementations) either red or black, it returns a boolean based off of whether or not a node is the root( a root will always be black) or if the node itself is red, this will be important later on
- This method may be used to collect all of the red nodes in a given tree
- Some implementations for code clarity will use this method, the caveat is this does take an extra bit in order to execute
- This method may be used to collect all of the black nodes in a given tree
- This method is the same as you would implement for a regular binary search tree
- O(log n) the same as a regular binary tree
- When a node is added and is a leaf, its children with automatically be instantiated with null values, and be colored black
- What makes this method different to a regular add in a binary search tree is that if any of the properties of the tree (listed in the section above) are violated, a rotation will have to be made to re-balance the tree, and therefore keep all operations in O(log n). Rotations are covered in the next three methods below and these may either be a left rotation or a right rotation.
- This method will always run in (O)n due to having to recursively call this function to check the state of nodes in a tree until they?re fixed and the tree satisfies all of the required properties of a red-black tree as stated in the previous section. This work also involves being the updates to the node references on a given tree via rotations, covered below
- This is what makes and keeps a red-black tree and its structure intact!
- After an add, this method checks the color of the node?s parent?s and the noes parents parents to make sure that the trees color of node in order are correct, this is that if a node is read, then moth its children must be black, and that the root node is red. This may involved recoloring of nodes to make sure that the tree is still balanced. This may also include rotating nodes to make sure that all nodes are level and that all NIL nodes have the same number of parents back to the root node. Rotation are covered below.
Rotations are the base of why any good self balancing tree stays balanced. because a tree can quickly become unbalanced due to non-randomized inputs that an either essentially turn part of that tree into a linked-list, or that certain NIL nodes after insertion may not have the same number of parent nodes leading to the same root. Rotations, if necessary are done after ever add (or delete) to make sure that the work never ?piles up?. Because we are only updating node references, this step runs in (O)1 for any number of rotation needed.
- This turns sibling?s left subtree into node?s right subtree
- The pictures below describe the movement to the left, of node references from one subtree to the parents other subtree
- This turns sibling?s right subtree into node?s left subtree. ,
- The pictures below describe the movement to the right, of node references from one subtree to the parents other subtree
FULL CODE IMPLEMENTATION SECTION
**Please note that some of the comments have been removed due to mediums formatting, for full comments please refer to my github at the bottom)**
#!/usr/bin/pythonclass NilNode(object): “”” The nil class is specifically for balancing a tree by giving all traditional leaf noes tw children that are null and waiting to be filled “”” def __init__(self): self.red = FalseNIL = NilNode() # Nil is the sentinel value for nodesclass RBNode(object): “”” Class for implementing the nodes that the tree will use For self.color: red == False black == True If the node is a leaf it will either “”” def __init__(self,data): self.red = False self.parent = None self.data = data self.left = None self.right = Noneclass RedBlackTree(object): “”” Class for implementing a standard red-black trees “”” def __init__(self): self.root = None def add(self,data,curr = None): “”” :param data: an int, float, or any other comparable value :param curr: :return: None but midifies tree to have an additional node “”” new_node = RBNode(data) # Base Case – Nothing in the tree if self.root == None: new_node.red = False self.root = new_node return # Search to find the node’s correct place currentNode = self.root while currentNode != None: potentialParent = currentNode if new_node.data < currentNode.data: currentNode = currentNode.left else: currentNode = currentNode.right # Assign parents and siblings to the new node new_node.parent = potentialParent if new_node.data < new_node.parent.data: new_node.parent.left = new_node else: new_node.parent.right = new_node self.fix_tree_after_add(new_node) def contains(self,data, curr=None): “”” :return: “”” if curr == None: curr = self.root while curr != NIL and data != curr.key: if data < curr.data: curr = curr.left else: curr = curr.right return curr def fix_tree_after_add(self,new_node): “”” This method is meant to check and rebalnce a tree back to satisfying all of the red-black properties :return: None, but modifies tree “”” while new_node.parent.red == True and new_node != self.root: if new_node.parent == new_node.parent.parent.left: uncle = new_node.parent.parent.right if uncle.red: new_node.parent.red = False uncle.red = False new_node.parent.parent.red = True new_node = new_node.parent.parent else: if new_node == new_node.parent.right: new_node = new_node.parent self.left_rotate(new_node) new_node.parent.red = False new_node.parent.parent.red = True self.right_rotate(new_node.parent.parent) else: uncle = new_node.parent.parent.left if uncle.red: new_node.parent.red = False uncle.red = False new_node.parent.parent.red = True new_node = new_node.parent.parent else: if new_node == new_node.parent.left: new_node = new_node.parent self.right_rotate(new_node) new_node.parent.red = False new_node.parent.parent.red = True self.left_rotate(new_node.parent.parent) self.root.red = False def rotate_left(self,new_node): “”” :return: “”” print(“Rotating left!”) sibling = new_node.right new_node.right = sibling.left # Turn sibling’s left subtree into node’s right subtree if sibling.left != None: sibling.left.parent = new_node sibling.parent = new_node.parent if new_node.parent == None: self.root = sibling else: if new_node == new_node.parent.left: new_node.parent.left = sibling else: new_node.parent.right = sibling sibling.left = new_node new_node.parent = sibling def rotate_right(self,new_node): “”” :return: “”” print(“Rotating right!”) sibling = new_node.left new_node.right = sibling.right # Turn sibling’s left subtree into node’s right subtree if sibling.right != None: sibling.right.parent = new_node sibling.parent = new_node.parent if new_node.parent == None: self.root = sibling else: if new_node == new_node.parent.right: new_node.parent.right = sibling else: new_node.parent.left = sibling sibling.right = new_node new_node.parent = sibling def get_all_nodes(self): “”” :return: “”” pass def is_red(self): “”” This is the class that usually decides that a node is wither red or black, some implementations take the extra bit and will implement an is_black method for additional clarity. Generally, True == Red and False == Black :return: “”” return self.root != None and self.root.red == 1; def is_black(self): “”” Note that this method is not necessary as some implementations only check is the is_red class method is True or False :return: True if the node is black or is a leaf “”” return self.root != None and self.root.black == 1;
The link to the code shown in this article:
CS 2.1: Advanced Trees & Sorting Algorithms. Contribute to Novandev/CS-2.1-Advanced-Trees-and-Sorting-Algorithms?