Building a Red-Black Binary Tree in Python

red black

The post Building a Red-Black Binary Tree in Python first appeared on Qvault.

A red-black tree is a kind of self-balancing binary search tree. Each node stores an extra bit, which we will call the color, red or black. The color ensures that the tree remains approximately balanced during insertions and deletions. When the tree is modified, the new tree is rearranged and repainted to restore the coloring properties that constrain how unbalanced the tree can become in the worst case.

The purpose of a red-black tree is to stay balanced which ensures that its common operations, like lookup and delete, never degrade to worse than O(n*log(n)).

Sorry to interrupt! I just wanted to mention that you should check out my new free Python course, “Big-O Data Structures”. You’ll learn all you need to know to crush your upcoming coding interviews and whiteboard sessions.

Start Python Data Structures Course

What is a balanced binary tree?

Since the reason colors are added to a binary tree is to ensure that it remains balanced, we need to understand how and why a binary tree is balanced. To put it simply, a balanced tree’s branches differ in height by no more than 1.

The following tree is balanced because between its two branches one has a height of 2, and the other 3, meaning they differ by no more than 1.



A / \ B C / D


The next tree is unbalanced because it’s branches differ in height by more than 1. C‘s right side has a height of 2 while its left side has a height of 4).




A / \ B C / / D E / G


Why do we want balanced trees?


Balanced binary search trees ensure speed. The speed of an operation in a binary tree depends on the height of the tree. If the tree is balanced, then the height is only the log of the number of nodes, which means the tree will work as fast as possible. However, if the tree is unbalanced, for example with one really long branch, then the height because the total number of nodes rather than the log.




A / B / C / D


Properties of a red-black tree


In addition to all the properties of a Binary Search Tree, a red-black tree must have the following:


    

  1. Each node is either red or black
    2. 

  2. The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
    3. 

  3. All nil leaf nodes are black.
    4. 

  4. If a node is red, then both its children are black.
    5. 

  5. All paths from a single node go through the same number of black nodes in order to reach any of its descendant nil nodes.
    6. 



Implementing a Red-Black Tree in Python


Step 1 – RBNode Class


Our implementation will use a Tree class and a Node class. The Node will be fairly simple, it’s just a constructor.




class RBNode: def __init__(self, val): self.red = False self.parent = None self.val = val self.left = None self.right = None


Code language: Python (python)


Step 2 – RBTree Class


Next let’s create a tree class with a constructor.




class RBTree: def __init__(self): self.nil = RBNode(0) self.nil.red = False self.nil.left = None self.nil.right = None self.root = self.nil


Code language: Python (python)


Step 3 – Insert method




def insert(self, val): # Ordinary Binary Search Insertion new_node = RBNode(val) new_node.parent = None new_node.left = self.nil new_node.right = self.nil new_node.red = True # new node must be red parent = None current = self.root while current != self.nil: parent = current if new_node.val < current.val: current = current.left elif new_node.val > current.val: current = current.right else: return # Set the parent and insert the new node new_node.parent = parent if parent == None: self.root = new_node elif new_node.val < parent.val: parent.left = new_node else: parent.right = new_node # Fix the tree self.fix_insert(new_node)


Code language: Python (python)


The insert method will look a lot like a traditional binary tree insert method. The biggest difference is that after doing an insert, we’ll call a special fix_insert method. For now just call it, we’ll implement it in just a moment.


Step 4 – Rotate left


We’ll need some rotation methods in our “fix” step that’s coming up. Let’s code those now.




rotate red black tree right






# rotate left at node x def rotate_left(self, x): y = x.right x.right = y.left if y.left != self.nil: y.left.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y


Code language: Python (python)


Step 5 – Rotate right




# rotate right at node x def rotate_right(self, x): y = x.left x.left = y.right if y.right != self.nil: y.right.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.right: x.parent.right = y else: x.parent.left = y y.right = x x.parent = y


Code language: Python (python)


Step 6 – Fix insert


The real bread and butter is in this step, it’s what makes a red-black tree balanced.




def fix_insert(self, new_node): while new_node != self.root and new_node.parent.red: if new_node.parent == new_node.parent.parent.right: u = new_node.parent.parent.left # uncle if u.red: u.red = False new_node.parent.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.rotate_right(new_node) new_node.parent.red = False new_node.parent.parent.red = True self.rotate_left(new_node.parent.parent) else: u = new_node.parent.parent.right # uncle if u.red: u.red = False new_node.parent.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.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


Code language: Python (python)


Full Example of Red-Black Tree in Code




import random 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(0) self.nil.red = False self.nil.left = None self.nil.right = None self.root = self.nil def insert(self, val): # Ordinary Binary Search Insertion new_node = RBNode(val) new_node.parent = None new_node.left = self.nil new_node.right = self.nil new_node.red = True # new node must be red parent = None current = self.root while current != self.nil: parent = current if new_node.val < current.val: current = current.left elif new_node.val > current.val: current = current.right else: return # Set the parent and insert the new node new_node.parent = parent if parent == None: self.root = new_node elif new_node.val < parent.val: parent.left = new_node else: parent.right = new_node # Fix the tree self.fix_insert(new_node) def fix_insert(self, new_node): while new_node != self.root and new_node.parent.red: if new_node.parent == new_node.parent.parent.right: u = new_node.parent.parent.left # uncle if u.red: u.red = False new_node.parent.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.rotate_right(new_node) new_node.parent.red = False new_node.parent.parent.red = True self.rotate_left(new_node.parent.parent) else: u = new_node.parent.parent.right # uncle if u.red: u.red = False new_node.parent.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.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 def exists(self, val): curr = self.root while curr != self.nil and val != curr.val: if val < curr.val: curr = curr.left else: curr = curr.right return curr # rotate left at node x def rotate_left(self, x): y = x.right x.right = y.left if y.left != self.nil: y.left.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y # rotate right at node x def rotate_right(self, x): y = x.left x.left = y.right if y.right != self.nil: y.right.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.right: x.parent.right = y else: x.parent.left = y y.right = x x.parent = y def __repr__(self): lines = [] print_tree(self.root, lines) return '\n'.join(lines) def print_tree(node, lines, level=0): if node.val != 0: print_tree(node.left, lines, level + 1) lines.append('-' * 4 * level + '> ' + str(node.val) + ' ' + ('r' if node.red else 'b')) print_tree(node.right, lines, level + 1) def get_nums(num): random.seed(1) nums = [] for _ in range(num): nums.append(random.randint(1, num-1)) return nums def main(): tree = RBTree() for x in range(1, 51): tree.insert(x) print(tree) main()


Code language: Python (python)










Ready to get coding?


Try our coding courses free


Join our Discord community







Have questions or feedback?


Follow and hit me up on Twitter @q_vault if you have any questions or comments. If I’ve made a mistake in the article be sure to let me know so I can get it corrected!









source https://qvault.io/python/red-black-tree-python/






































Comments











Post a Comment























Popular posts from this blog









Why is Exclusive Or (XOR) Important in Cryptography?




















Image







    If you are getting into cryptography, or just trying to understand the fundamentals, you may have noticed that the exclusive-or operation is used quite often, especially in ciphers.  What is XOR ( ⊕ )?  XOR, or “exclusive or” operates on binary data. It returns true if both of its inputs are opposites (one false and one true), otherwise, it returns false.     An example in go code would be something like:  func exclusiveOr(a bool, b bool) bool {         return a != b }  XOR Cipher – The Perfect Cipher  The XOR operation can be used as a simple cipher for encrypting and decrypting messages with a single key. This is known as symmetric encryption.  It is interesting to note that if:   The key is the same size as the message  The key is kept secret and generated truly randomly   Then the cipher is impossible  to crack. This is known as a one time pad . However, a simple XOR shouldn’t be used in production due to the key length needing to be too long to be practical.  Cipher Example  A...








Read more










Base64 vs Base58 Encoding




















Image







 By Lane Wagner –  @wagslane  on Twitter   Base64 is one of the most popular encoding formats for representing data. Have some binary data? Base64 encode it for convenient readability and parsing. Base58 is just another encoding format (with 58 characters instead of 64, and has gained popularity largely due to Bitcoin and other cryptocurrencies.  When it comes to data encoding, there is typically a trade-off made between:   Human Readability: Do humans have a good idea of what is being represented at a glance?  Efficient data compression: How many bytes are used to represent the same data?   Let’s rank Base58, Base64, and ASCII encoding against each other using these metrics!  First: A Note on Binary  All data is stored in a raw binary format on computers. These encoding formats (Base64, Base58, and ASCII) are just different ways of reading and writing binary data. For example, in Base64 the binary code 000000  represents the letter A , but in ASCII the binary 00000000  repres...








Read more










(Very) Basic Intro to Hash Functions (SHA-256, MD-5, etc)




















Image







 This is going to be a basic introduction to hash functions. I will assume most of my audience is here to gain an understanding of why hash functions are used and the basic idea of why they work. My goal is to explain it in a general sense, I will be omitting proofs and implementation details and instead focusing on the high-level principles.     Why Use A Hash Function?  Hash functions are used all over the internet in order to securely store passwords, find duplicate records, quickly store and retrieve data, and more. For example,  Qvault  uses hashes to extend master passwords into private encryption keys.  A longer list of uses here:  https://en.wikipedia.org/wiki/Hash_function#Uses  I want to focus on several important features of hash functions, arguably the most important features.   Hash functions scramble data deterministically  No matter the input, the output of a hash function always has the same size  The original data can not be retrieved from the scrambled d...








Read more