How to search a node in red-black tree
A red-black tree is a type of self-balancing binary tree. This answer will cover searching in a red-black tree in Python.
Algorithm
Search in a red-black tree is similar to searching in a binary tree. It follows the following steps:
First, we check if the root node is the desired node. If yes, return that.
If the value is less than the value of the root node, apply the search function on its left child else, apply the search function on its right child.
Repeat the above steps unless we find the desired value or reach the tree's end. We can check if it's the end of the tree if we encounter a
Nonenode. In that case, returnNoneorFalse.
Example
Look at the code below:
RED = 'red'BLACK = 'black'class Node:def __init__(self, value, color):self.value = valueself.left = Noneself.right = Noneself.color = colorclass RedBlackTree:def __init__(self):self.root = Nonedef _search(self, node, num):if not node:return Falseif node.value == num:return Truereturn self._search(node.left, num) if num < node.value else self._search(node.right, num)def search(self, num):return self._search(self.root, num)tree = RedBlackTree()tree.root = Node(13, BLACK)tree.root.left = Node(11, BLACK)tree.root.right = Node(15, RED)tree.root.right.left = Node(14, BLACK)tree.root.right.right = Node(17, BLACK)print("A node with value 0 was found in the tree:", tree.search(0))print("A node with value 14 was found in the tree:", tree.search(14))
Explanation
Lines 4–9: We define a
Nodeclass that storing a node of the red-black tree.Lines 15–23: We define a wrapper function
search()in theRedBlackTreeclass that calls the recursive function_search(). The_search()function uses recursion to go through the tree and find the node following the algorithm explained above. If the node is found, it returnsTrue, else. it returnsFalse.Lines 25–33: We create a red-black tree, and the
searchfunction is called on it. We can see the result by running the code.
