[Python] The implementation of red-black trees gives problems inserting a duplicate number

I'm implementing a red-black tree. But I keep getting error messages when the same number is entered multiple times (like the two 5's in "numbers").

class Node:
def __init__(self, key, color="RED"):
"""
Node class represents a node in the Red-Black Tree.

Args:
key: The key value of the node.
color: The color of the node (RED or BLACK).

Attributes:
key: The key value of the node.
parent: The parent node.
left: The left child node.
right: The right child node.
color: The color of the node (RED or BLACK).
"""
self.key = key
self.parent = None
self.left = None
self.right = None
self.color = color


class RedBlackTree:
def __init__(self):
"""
RedBlackTree class represents a Red-Black Tree.

Attributes:
NIL: The sentinel node representing a null leaf node.
root: The root node of the Red-Black Tree.
"""
self.NIL = Node(None, color="BLACK")
self.root = self.NIL

def insert(self, key):
"""
Inserts a new node with the given key into the Red-Black Tree.

Args:
key: The key value of the node to be inserted.
"""
new_node = Node(key)
new_node.left = self.NIL
new_node.right = self.NIL

parent = None
current = self.root

while current != self.NIL:
parent = current
if key < current.key:
current = current.left
else:
current = current.right

new_node.parent = parent

if parent is None:
self.root = new_node
elif key < parent.key:
parent.left = new_node
else:
parent.right = new_node

self._insert_fixup(new_node)

def _insert_fixup(self, node):
"""
Fixes the Red-Black Tree properties after node insertion.

Args:
node: The newly inserted node.
"""
while node != self.root and node.parent.color == "RED":
if node.parent == node.parent.parent.left:
uncle = node.parent.parent.right
if uncle.color == "RED":
node.parent.color = "BLACK"
uncle.color = "BLACK"
node.parent.parent.color = "RED"
node = node.parent.parent
else:
if node == node.parent.right:
node = node.parent
self._left_rotate(node)
node.parent.color = "BLACK"
node.parent.parent.color = "RED"
self._right_rotate(node.parent.parent)
else:
uncle = node.parent.parent.left
if uncle.color == "RED":
node.parent.color = "BLACK"
uncle.color = "BLACK"
node.parent.parent.color = "RED"
node = node.parent.parent
else:
if node == node.parent.left:
node = node.parent
self._right_rotate(node)
node.parent.color = "BLACK"
node.parent.parent.color = "RED"
self._left_rotate(node.parent.parent)

self.root.color = "BLACK"

def _left_rotate(self, node):
"""
Performs a left rotation on the given node.

Args:
node: The node to perform the left rotation on.
"""
right_child = node.right
node.right = right_child.left
if right_child.left != self.NIL:
right_child.left.parent = node
right_child.parent = node.parent
if node.parent == self.NIL:
self.root = right_child
elif node == node.parent.left:
node.parent.left = right_child
else:
node.parent.right = right_child
right_child.left = node
node.parent = right_child

def _right_rotate(self, node):
"""
Performs a right rotation on the given node.

Args:
node: The node to perform the right rotation on.
"""
if node is None or node.left is None:
return

left_child = node.left
node.left = left_child.right
if left_child.right != self.NIL:
left_child.right.parent = node
left_child.parent = node.parent
if node.parent == self.NIL:
self.root = left_child
elif node == node.parent.left:
node.parent.left = left_child
else:
node.parent.right = left_child

left_child.right = node
node.parent = left_child
node.left.parent = node

def inorder_traversal(self):
"""Performs an inorder traversal of the Red-Black Tree."""
self._inorder_recursive(self.root)

def _inorder_recursive(self, node):
"""
Performs an inorder traversal of the Red-Black Tree recursively.

Args:
node: The current node in the traversal.
"""
if node != self.NIL:
self._inorder_recursive(node.left)
print(node.key, end=" ")
self._inorder_recursive(node.right)

def search(self, key):
"""
Searches for a node with the given key in the Red-Black Tree.

Args:
key: The key value to search for.

Returns:
The node with the given key if found, None otherwise.
"""
return self._search_recursive(self.root, key)

def _search_recursive(self, node, key):
"""
Searches for a node with the given key in the Red-Black Tree recursively.

Args:
node: The current node in the search.
key: The key value to search for.

Returns:
The node with the given key if found, None otherwise.
"""
if node == self.NIL or key == node.key:
return node
if key < node.key:
if node.left != self.NIL:
return self._search_recursive(node.left, key)
else:
if node.right != self.NIL:
return self._search_recursive(node.right, key)
return None


rbt = RedBlackTree()

numbers = [10, 5, 5, 3, 7, 13, 18, 1, 6, 11, 14, 17, 19]

for number in numbers:
rbt.insert(number)

print("Red-Black Tree (inorder traversal):")
rbt.inorder_traversal()

to_search = [6, 12, 321]

print("\n")
for number in to_search:
if rbt.search(number):
print(f"The number {number} was found in the Red-Black Tree.")
else:
print(f"--The number {number} was not found in the Red-Black Tree--")


I've made several small tweaks, but none of them solve the problem, does anyone have any idea how to fix it?

The error I get is:

Traceback (most recent call last):
File "C:/Users/.../PycharmProjects/pythonProject1/Alberi_rosso_neri", line 209, in <module>
rbt.insert(number)
File "C:/Users/.../PycharmProjects/pythonProject1/Alberi_rosso_neri", line 66, in insert
self._insert_fixup(new_node)
File "C:/Users/.../PycharmProjects/pythonProject1/Alberi_rosso_neri", line 89, in _insert_fixup
self._right_rotate(node.parent.parent)
File "C:/Users/.../PycharmProjects/pythonProject1/Alberi_rosso_neri", line 145, in _right_rotate
elif node == node.parent.left:
AttributeError: 'NoneType' object has no attribute 'left'


I realize it's probably a logic error, but I can't figure out where it is and how to fix it. The code must be able to receive multiple equal numbers. Any idea or solution?

Continue reading...