The Red-Black Tree is used for high-level sorting of price levels which allows for efficient insertion, deletion and lookup of price levels in the order book. Each nodeKey represents a price level. Note that Limits for each price level, which track the linked lists of orders, are stored separately from the tree.
RedBlackTree
struct RedBlackTree {
    uint256 root;
    uint256 size;
    uint256 minimum;
    uint256 maximum;
    mapping(uint256 => Node) nodes;
}

​
init

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

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

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

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

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

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

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

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.