red_black_tree.py

Red-Black Tree implementation for balanced binary search tree operations.

This module implements a self-balancing binary search tree using the Red-Black Tree algorithm. The tree maintains logarithmic time complexity for insertion, deletion, and search operations through color-based balancing rules.

Classes

RedBlackTree

A self-balancing binary search tree that maintains Red-Black properties to ensure O(log n) performance for all major operations.

class red_black_tree.RedBlackTree(element_type: type, collection: Sequence[Any] | None = None, comparator: Callable[[object], Any] | None = None)

Bases: object

A class to represent a Red-Black Tree.

_root

The root of the tree.

Type:

Node | None

_type

The type of the elements in the tree.

Type:

type

_key

A function to compare elements in the tree.

Type:

Callable | None

_smallest

The smallest element in the tree.

Type:

Node | None

_largest

The largest element in the tree.

Type:

Node | None

find(value: object) → tuple[int, Node | None]

Find a value in the tree. :param value: The value to find. :type value: object

Returns:

(0, current) if found, (-1, pos) otherwise.

Return type:

tuple[int, Node | None]

Raises:

TypeError if value of unsupported type. –

higher(value: object, equal_valid: bool) → object

Find nearest successor to the value. If equal_valid is True, return the value itself if present in the tree. :param value: The value to find the successor for. :type value: object :param equal_valid: If True, return the value itself if present in the tree. :type equal_valid: bool

Returns:

The nearest successor to the value.

Return type:

object

insert(value: object) → tuple[int, Node] | tuple[int, Node | None]

Insert a value into the tree. :param value: The value to insert. :type value: object

Returns:

(0, node) if inserted, (-1, None) otherwise.

Return type:

tuple[int, Node] | tuple[int, int]

Raises:

TypeError if value of unsupported type. –

items() → list[Any]

Return a list of all items in the tree ordered by their natural order. :returns: A list of all items in the tree. :rtype: list[Any]

property largest: object

Return the largest element in the tree. :returns: The largest element in the tree. :rtype: object

lower(value: object, equal_valid: bool) → object

Find nearest predecessor to the value. If equal_valid is True, return the value itself if present in the tree. :param value: The value to find the predecessor for. :type value: object :param equal_valid: If True, return the value itself if present in the tree. :type equal_valid: bool

Returns:

The nearest predecessor to the value.

Return type:

object

remove(value: object) → tuple[int, Node] | tuple[int, Node | None]

Remove a value from the tree. :param value: The value to remove. :type value: object

Returns:

(0, node) if removed, (-1, None) otherwise.

Return type:

tuple[int, Node] | tuple[int, int]

Raises:

TypeError if value of unsupported type. –

property root: Node | None

Return the root of the tree. :returns: The root of the tree. :rtype: Node | None

property smallest: object

Return the smallest element in the tree. :returns: The smallest element in the tree. :rtype: object

property type: type

Return the type of the elements in the tree. :returns: The type of the elements in the tree. :rtype: type