Durch die Implementierung von rotschwarzen Bäumen Probleme beim Einfügen einer doppelten Zahl ⇐ Python

[Anonymous]

Ich implementiere einen rot-schwarzen Baum. Aber ich erhalte immer wieder Fehlermeldungen, wenn die gleiche Nummer mehrmals eingegeben wird (wie die beiden 5 in "Zahlen"). < /P>
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--")
< /code>
Ich habe mehrere kleine Verbesserungen vorgenommen, aber keiner von ihnen löst das Problem. Hat jemand eine Idee, wie man es behebt?Traceback (most recent call last):
File "C:/Users/.../PycharmProjects/pythonProject1/Alberi_rosso_neri", line 209, in
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'
< /code>
Mir ist klar, dass es wahrscheinlich ein logischer Fehler ist, aber ich kann nicht herausfinden, wo es ist und wie man es behebt. Der Code muss in der Lage sein, mehrere gleiche Zahlen zu empfangen.
eine Idee oder Lösung? < /P>