"""
Node implementation for Red-Black Tree data structure.
This module defines the Node class that represents individual nodes in a Red-Black Tree.
Each node contains data and maintains the tree's structural properties including color,
parent-child relationships, and black height for efficient tree balancing operations.
Classes
-------
Node
Represents a single node in a Red-Black Tree with all necessary attributes
for maintaining tree balance and performing tree operations.
"""
from config import COLORS
from typing import Optional
[docs]
class Node:
"""Implements a node in a red-black tree
Attributes
-----------
_data:
Value of the node.
_color: int
Color of the node. (1: black, 0: red)
_parent: Node
Parent of this node.
_left: Node
Left child of this node.
_right: Node
Right child of this node.
_black_height:
Black height of the node.
"""
def __init__(self, data: object, color: int, parent: Optional['Node'], left: Optional['Node'], right: Optional['Node']):
"""Initializes the node.
Parameters:
--------
_data:
Value of the node.
_color: int
Color of the node. (1: black, 0: red)
_parent: Node
Parent of this node.
_left: Node
Left child of this node.
_right: Node
Right child of this node.
"""
self._data: object = data
self._color: int = color
self._parent: Node | None = parent
self._left: Node | None = left
self._right: Node | None = right
self._black_height: int = self.update_black_height()
@property
def black_height(self) -> int:
"""Returns the black height of the node.
Returns
-------
int
The black height of the node.
"""
return self._black_height
@black_height.setter
def black_height(self, value: int):
"""Sets the black height of the node.
Parameters
----------
value: int
New black height for the node.
"""
self._black_height = value
[docs]
def update_black_height(self) -> int:
"""Updates the black_height of the node, also telling its parent to update if it changes
Returns
-------
int
The updated black height of the node.
"""
left_height = self._left.black_height + self._left.color if self._left else 1
right_height = self._right.black_height + self._right.color if self._right else 1
return max(left_height, right_height)
def __black_height_changed(self):
current = self
while current.parent:
prev = current._black_height
new = current.update_black_height()
if prev != new:
current.black_height = new
current = current.parent
continue
break
if not current.parent:
current.black_height = current.update_black_height()
@property
def color(self) -> int:
"""Returns the node's color
Returns
-------
int
Color of the node (1: black, 0: red)
"""
return self._color
@color.setter
def color(self, color: int):
"""Sets the node's color:
Parameters
----------------
color: int
New color for the node
Raises
------
TypeError
If the color given is not an integer.
ValueError
If the number given is not 0 or 1.
"""
if type(color) != int:
raise TypeError("Color should be an integer.")
if color not in {COLORS.RED, COLORS.BLACK}:
raise ValueError("Invalid color.")
self._color = color
if self._parent:
self._parent.__black_height_changed()
@property
def left(self):
"""Returns the left child of the node"""
return self._left
@left.setter
def left(self, left: Optional['Node']):
"""Sets the node's left child.
Parameters
-------------
left: Node | None
New left child.
Raises
------
TypeError
If the parameter given is not a node.
"""
if left and type(left) != Node:
raise TypeError("Left should be an instance of Node.")
self._left = left
self.__black_height_changed()
@property
def right(self):
"""Returns the node's right child."""
return self._right
@right.setter
def right(self, right: Optional['Node']):
"""Sets the node's right child.
Parameters
-------------
right: Node | None
New right child.
Raises
------
TypeError
If the parameter given is not a node.
"""
if right and type(right) != Node:
raise TypeError("Right should be an instance of Node.")
self._right = right
self.__black_height_changed()
@property
def parent(self):
"""Returns the node's parent."""
return self._parent
@parent.setter
def parent(self, parent: Optional['Node']):
"""Sets the node's parent.
Parameters
-------------
parent: Node | None
New parent.
Raises
------
TypeError
If the parameter given is not a node.
"""
if parent and type(parent) != Node:
raise TypeError("Parent should be an instance of Node.")
self._parent = parent
if parent is not None and isinstance(self._parent, Node):
self._parent.__black_height_changed()
@property
def data(self):
"""Returns the node's value."""
return self._data