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 None node. In that case, return None or False.

RED = 'red'
BLACK = 'black'
class Node:
    def __init__(self, value, color):
        self.value = value
        self.left = None
        self.right = None
        self.color = color
class RedBlackTree:
    def __init__(self):
        self.root = None
    
    def _search(self, node, num):
        if not node:
            return False
        if node.value == num:
            return True
        return 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 Node class that storing a node of the red-black tree.
Lines 15–23: We define a wrapper function search() in the RedBlackTree class 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 returns True, else. it returns False.
Lines 25–33: We create a red-black tree, and the search function is called on it. We can see the result by running the code.

Free Resources

How to search a node in red-black tree

Algorithm

Example

Explanation