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
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.