different beween self.null and none in red-black tree implementation

Question

I don't understand a part of the code in the implementation of the red-black tree, specifically the use of self.null . Could you explain what self.null represents and how it differs from None? Why are there instances where None is used in some places, but self.null is used in others? If I were to replace self.null with None , what implications would that have on the functionality of the code?

class Node():
    def __init__(self,val):
        self.val = val                                   # Value of Node
        self.parent = None                               # Parent of Node
        self.left = None                                 # Left Child of Node
        self.right = None                                # Right Child of Node
        self.color = 1                                   # Red Node as new node is always inserted as Red Node

# Define R-B Tree
class RBTree():
    def __init__(self):
        self.NULL = Node ( 0 )
        self.NULL.color = 0
        self.NULL.left = None
        self.NULL.right = None
        self.root = self.NULL


    # Insert New Node
    def insertNode(self, key):
        node = Node(key)
        node.parent = None
        node.val = key
        node.left = self.NULL
        node.right = self.NULL
        node.color = 1                                   # Set root colour as Red

        y = None
        x = self.root

        while x != self.NULL :                           # Find position for new node
            y = x
            if node.val < x.val :
                x = x.left
            else :
                x = x.right

I tried to understand the difference between self.null and none, but I couldn't. especially in this line x! self.null

Answer 1

Self.NULL is called a "sentinel node". It's an actual Node object that is used in place of a None or null value at all the places in the tree where nodes are missing.

This is commonly used in red-black trees to simplify the code. The code is simpler, because you can check the color of a sentinel node (nulls are black) without testing first to see if the node exists. This removes a lot if if node == None checks that would otherwise be required.