Functions
template<typename RbNode >
void	insert (RbNode &root, RbNode new_node)
	Inserts a new node into the Red-Black tree.

template<typename RbNode >
void	remove (RbNode &root, RbNode node)
	Removes a node from the Red-Black tree.

template<typename RbNode >
RbNode *	lower_bound (RbNode root, std::size_t key, bool(cmp)(std::size_t, std::size_t))
	Finds the smallest node with value >= key.

void	set_color_red (std::size_t &value)
	Sets the color of a node to RED.

void	set_color_black (std::size_t &value)
	Sets the color of a node to BLACK.

bool	is_red (const std::size_t &value)
	Checks if a node is RED.

bool	is_black (const std::size_t &value)
	Checks if a node is BLACK.

std::size_t	get_value (const std::size_t &value)
	Extracts the actual value without the color bit.

bool	get_color (const std::size_t &value)
	Gets the color bit value.

template<typename RbNode >
void	left_rotate (RbNode &root, RbNode node)
	Performs a left rotation around a node.

template<typename RbNode >
void	right_rotate (RbNode &root, RbNode node)
	Performs a right rotation around a node.

template<typename RbNode >
void	fix_insert (RbNode &root, RbNode z)
	Fixes Red-Black tree properties after insertion.

template<typename RbNode >
void	transplant (RbNode &root, RbNode u, RbNode *v)
	Replaces one subtree with another.

template<typename RbNode >
void	fix_remove (RbNode &root, RbNode x, RbNode *x_parent)
	Fixes Red-Black tree properties after deletion.

Function Documentation

◆ fix_insert()

template<typename RbNode >

void hh::rb_tree::fix_insert	(	RbNode *&	root,
		RbNode *	z
	)

Fixes Red-Black tree properties after insertion.

Restores the Red-Black tree properties that may have been violated during insertion. Handles the following violations:

Red node with red parent (double-red violation)

Uses recoloring and rotations to maintain:

Root is black
No two consecutive red nodes
All paths have same number of black nodes

Template Parameters

RbNode Node type

Parameters

root	Reference to the root pointer
z	The newly inserted node to fix violations from

Postcondition: All Red-Black tree properties are restored; Root is always black

◆ fix_remove()

template<typename RbNode >

void hh::rb_tree::fix_remove	(	RbNode *&	root,
		RbNode *	x,
		RbNode *	x_parent
	)

Fixes Red-Black tree properties after deletion.

Restores Red-Black properties after a black node has been removed. Handles the case where removing a black node creates a "double-black" violation where a path has one fewer black node.

Cases handled:

Sibling is red
Sibling is black with two black children
Sibling is black with red left child and black right child
Sibling is black with red right child

Template Parameters

RbNode Node type

Parameters

root	Reference to the root pointer
x	The node that replaced the deleted node (may be nullptr)
x_parent	Parent of x (needed when x is nullptr)

Postcondition: Red-Black properties are restored; All paths have equal black height; Root is black

◆ get_color()

bool hh::rb_tree::get_color ( const std::size_t & value )

inline

Gets the color bit value.

Parameters

value The node's value field

Returns: true if red, false if black

◆ get_value()

std::size_t hh::rb_tree::get_value ( const std::size_t & value )

inline

Extracts the actual value without the color bit.

Masks out bit 63 (color bit) and returns the actual stored value.

Parameters

value The node's value field including color bit

Returns: The actual value with color bit cleared

◆ insert()

template<typename RbNode >

void hh::rb_tree::insert	(	RbNode *&	root,
		RbNode *	new_node
	)

Inserts a new node into the Red-Black tree.

Inserts the given node into the tree and rebalances to maintain Red-Black tree properties. The node is inserted based on its value (excluding the color bit).

Template Parameters

RbNode Node type with left, right, parent pointers and value field

Parameters

root	Reference to the root pointer of the tree
new_node	Pointer to the node to be inserted (must be allocated)

Precondition: new_node must be properly allocated and initialized; new_node->value must have bit 63 available for coloring

Postcondition: Tree maintains Red-Black properties; root may be modified if tree structure changes

Performs standard BST insertion based on node values (excluding color bit), then calls fix_insert to restore Red-Black properties.

Algorithm:

Find the correct position using BST search
Insert the node as a red leaf
Fix any Red-Black violations

Template Parameters

RbNode Node type

Parameters

root	Reference to the root pointer
new_node	The node to insert (must be allocated)

Precondition: new_node is properly allocated; new_node->value has bit 63 available for coloring

Postcondition: Node is inserted and colored red initially; Red-Black properties are maintained; Tree remains balanced

Note: Duplicate values are inserted to the right

◆ is_black()

bool hh::rb_tree::is_black ( const std::size_t & value )

inline

Checks if a node is BLACK.

Parameters

value The node's value field

Returns: true if the node is black (bit 63 is clear), false otherwise

◆ is_red()

bool hh::rb_tree::is_red ( const std::size_t & value )

inline

Checks if a node is RED.

Parameters

value The node's value field

Returns: true if the node is red (bit 63 is set), false otherwise

◆ left_rotate()

template<typename RbNode >

void hh::rb_tree::left_rotate	(	RbNode *&	root,
		RbNode *	node
	)

Performs a left rotation around a node.

Rotates the subtree so that the right child moves up to take the position of the current node, and the current node becomes the left child of its former right child.

Before: node After: right_child / \ / \ A right_child node C / \ / \ B C A B

Template Parameters

RbNode Node type

Parameters

root	Reference to the root pointer (may be updated)
node	The node around which to rotate

Precondition: node->right must not be nullptr

Postcondition: Tree structure is modified, parent pointers updated

◆ lower_bound()

template<typename RbNode >

RbNode * hh::rb_tree::lower_bound	(	RbNode *	root,
		std::size_t	value,
		bool(*)(std::size_t, std::size_t)	cmp
	)

Finds the smallest node with value >= key.

Finds the first node with value not less than the search key.

Performs a lower_bound search using a custom comparator function. Returns the node with the smallest value that is not less than the key.

Template Parameters

RbNode Node type with left, right, parent pointers and value field

Parameters

root	Pointer to the root of the tree
key	The search key value
cmp	Comparator function returning true if first arg < second arg

Returns: Pointer to the found node, or nullptr if no such node exists

Precondition: cmp must define a strict weak ordering

Postcondition: Tree structure remains unchanged

Performs a binary search to find the smallest node that satisfies !cmp(node_value, key), i.e., the first node where key <= node_value according to the comparator.

This is equivalent to std::lower_bound for binary search trees.

Algorithm:

Start at root and traverse down
If key < current_value, move left (might be result)
If key >= current_value, move right
Return the smallest valid node found

Template Parameters

RbNode Node type

Parameters

root	Pointer to the root of the tree
value	The search key
cmp	Comparator function (returns true if first < second)

Returns: Pointer to the first node >= value, or nullptr if none exists

Precondition: cmp defines a strict weak ordering

Postcondition: Tree structure is unchanged

Note: Time complexity: O(log n) for balanced tree; Returns nullptr if all values are less than the search key

◆ remove()

template<typename RbNode >

void hh::rb_tree::remove	(	RbNode *&	root,
		RbNode *	z
	)

Removes a node from the Red-Black tree.

Removes the specified node from the tree and rebalances to maintain Red-Black tree properties. Does not deallocate the node.

Template Parameters

RbNode Node type with left, right, parent pointers and value field

Parameters

root	Reference to the root pointer of the tree
node	Pointer to the node to be removed

Precondition: node must exist in the tree; root must not be null

Postcondition: Tree maintains Red-Black properties; root may be modified if tree structure changes; Node is removed but NOT deallocated

Removes the specified node from the tree while maintaining Red-Black properties. Handles three cases:

Node has no left child - replace with right child
Node has no right child - replace with left child
Node has both children - replace with successor (minimum of right subtree)

After removal, if a black node was removed, fix_remove is called to restore Red-Black properties.

Template Parameters

RbNode Node type

Parameters

root	Reference to the root pointer
z	The node to remove

Precondition: z exists in the tree; root is not nullptr

Postcondition: z is removed from the tree structure (but not deallocated); Red-Black properties are maintained; Tree remains balanced

Note: The node is NOT deallocated, only removed from tree structure; Caller is responsible for memory management of removed node

◆ right_rotate()

template<typename RbNode >

void hh::rb_tree::right_rotate	(	RbNode *&	root,
		RbNode *	node
	)

Performs a right rotation around a node.

Rotates the subtree so that the left child moves up to take the position of the current node, and the current node becomes the right child of its former left child.

Before: node After: left_child / \ / \ left_child C A node / \ / \ A B B C

Template Parameters

RbNode Node type

Parameters

root	Reference to the root pointer (may be updated)
node	The node around which to rotate

Precondition: node->left must not be nullptr

Postcondition: Tree structure is modified, parent pointers updated

◆ set_color_black()

void hh::rb_tree::set_color_black ( std::size_t & value )

inline

Sets the color of a node to BLACK.

Marks the node as black by clearing bit 63 of the value field.

Parameters

value Reference to the node's value field

Postcondition: Bit 63 of value is set to 0 (BLACK)

◆ set_color_red()

void hh::rb_tree::set_color_red ( std::size_t & value )

inline

Sets the color of a node to RED.

Marks the node as red by setting bit 63 of the value field to 1.

Parameters

value Reference to the node's value field

Postcondition: Bit 63 of value is set to 1 (RED)

◆ transplant()

template<typename RbNode >

void hh::rb_tree::transplant	(	RbNode *&	root,
		RbNode *	u,
		RbNode *	v
	)

Replaces one subtree with another.

Helper function that replaces the subtree rooted at node u with the subtree rooted at node v, updating parent pointers.

Template Parameters

RbNode Node type

Parameters

root	Reference to the root pointer
u	Node to be replaced
v	Node to replace with (can be nullptr)

Postcondition: u's position is taken by v; Parent pointers are correctly updated

Functions

Function Documentation

◆ fix_insert()

◆ fix_remove()

◆ get_color()

◆ get_value()

◆ insert()

◆ is_black()

◆ is_red()

◆ left_rotate()

◆ lower_bound()

◆ remove()

◆ right_rotate()

◆ set_color_black()

◆ set_color_red()

◆ transplant()