Red-Black Tree

struct RedBlackTree {
    uint256 root;
    uint256 size;
    uint256 minimum;
    uint256 maximum;
    mapping(uint256 => Node) nodes;
}

​

init

function init(
    RedBlackTree storage tree
) internal

Initializes a red-black tree by setting its root to NULL, size to zero, and minimum and maximum values to their respective extremes.

​

insert

function insert(
    RedBlackTree storage tree,
    uint256 nodeKey
) internal

Inserts a new node with the specified key into the red-black tree, maintaining the tree’s properties and updating the minimum and maximum keys if necessary.

​

remove

function remove(
    RedBlackTree storage tree,
    uint256 nodeKey
) internal

Removes a node with the specified key from the red-black tree, ensuring the tree’s properties are preserved and updating the minimum and maximum keys if necessary.

​

get

function get(
    RedBlackTree storage tree,
    uint256 nodeKey
) internal view returns (Node memory)

Retrieves the node associated with the specified key from the red-black tree.

​

contains

function contains(
    RedBlackTree storage tree,
    uint256 nodeKey
) internal view returns (bool)

Checks if a node with the specified key exists in the red-black tree.

​

getNextBiggest

function getNextBiggest(
    RedBlackTree storage tree,
    uint256 nodeKey
) internal view returns (uint256)

Finds the next largest key in the red-black tree that is greater than the specified key.

​

getNextSmallest

function getNextSmallest(
    RedBlackTree storage tree,
    uint256 nodeKey
) internal view returns (uint256)

Finds the next smallest key in the red-black tree that is less than the specified key.

​

assertInvariants

function assertInvariants(
    RedBlackTree storage tree
) internal view

Verifies that the red-black tree satisfies all its invariants, including properties related to node colors, black height, and binary search tree order.