Red-Black Tree container implementation. More...

#include <RBTree.h>

Collaboration diagram for original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >:

Classes
class	Iterator
	Bidirectional iterator for RBTree. More...

class	RBNode
	Internal node class for Red-Black Tree. More...

Protected Types
using	color = typename RBNode::color
	Color type alias.

using	rebind_alloc_node = typename ALLOC::template rebind_alloc<RBNode>
	Rebound allocator type.

Protected Member Functions
RBNode *	treeCopy () const
	Creates a deep copy of the tree.

RBNode *	getPrecursorNode (RBNode *cur) const
	Gets precursor node (in-order predecessor)

RBNode *	getSuccessorNode (RBNode *cur) const
	Gets successor node (in-order successor)

RBNode *	getMinNode () const
	Gets the minimum node in the tree.

RBNode *	getMaxNode () const
	Gets the maximum node in the tree.

RBNode *	replaceNode (RBNode src, RBNode tar)
	Replaces one node with another while maintaining tree structure.

RBNode *	createNode (const K_TYPE &key=K_TYPE{}, const V_TYPE &value=V_TYPE{}, color color=RED, RBNode parent=nullptr, RBNode left=nullptr, RBNode *right=nullptr) const
	Creates a new node with given parameters.

RBNode *	createNode (RBNode &&other_node) const
	Creates a new node by moving from another node.

void	destroyNode (RBNode *node) noexcept
	Destroys a node and deallocates memory.

bool	highPriority (RBNode cur, RBNode other) const
	Compares priority between two nodes.

bool	highPriority (const K_TYPE &key, RBNode *other) const
	Compares priority between a key and a node.

RBNode *	rotateLeft (RBNode *cur)
	Performs left rotation around a node.

RBNode *	rotateRight (RBNode *cur)
	Performs right rotation around a node.

void	adjustInsert (RBNode *cur)
	Adjusts tree after insertion to maintain RB properties.

void	adjustErase (RBNode *cur)
	Adjusts tree after deletion to maintain RB properties.

void	destroyTree () noexcept
	Destroys entire tree and deallocates all nodes.

	RBTree (Compare compare=Compare{})
	Constructs RBTree with given comparison function.

RBNode *	find (const K_TYPE &key) const
	Finds node with given key.

bool	modify (const K_TYPE &key, const V_TYPE &value)
	Modifies value for existing key.

bool	insert (const K_TYPE &key, const V_TYPE &value)
	Inserts new key-value pair.

bool	erase (const K_TYPE &key)
	Erases node with given key.

	~RBTree ()
	Destructor.

Protected Attributes
RBNode *	root_
	Root node pointer.

u_integer	size_
	Number of elements.

Compare	compare_
	Comparison function.

rebind_alloc_node	rebind_alloc {}
	Node allocator.

friend	Iterator

Static Protected Attributes
static constexpr color	BLACK = color::BLACK
	Black color constant.

static constexpr color	RED = color::RED
	Red color constant.

Detailed Description

template<typename K_TYPE, typename V_TYPE, typename ALLOC = allocator<K_TYPE>, typename Compare = increaseComparator<K_TYPE>>
class original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >

Red-Black Tree container implementation.

Template Parameters

K_TYPE	Key type (must be comparable)
V_TYPE	Value type
ALLOC	Allocator type (default: allocator<K_TYPE>)
Compare	Comparison function type (default: increaseComparator<K_TYPE>)

This class provides a balanced binary search tree implementation with the following properties:

O(log n) search/insert/delete operations
Self-balancing through color properties
Custom comparator support
STL-style allocator support

Constructor & Destructor Documentation

◆ RBTree()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBTree ( Compare compare = Compare{} )

explicitprotected

Constructs RBTree with given comparison function.

Parameters

compare Comparison function to use

◆ ~RBTree()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::~RBTree ( )

protected

Destructor.

Cleans up all tree nodes and allocated memory

Member Function Documentation

◆ adjustErase()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

void original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::adjustErase ( RBNode * cur )

protected

Adjusts tree after deletion to maintain RB properties.

Parameters

cur	Node where deletion occurred

Handles color flips and rotations as needed

◆ adjustInsert()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

void original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::adjustInsert ( RBNode * cur )

protected

Adjusts tree after insertion to maintain RB properties.

Parameters

cur	Newly inserted node

Handles color flips and rotations as needed

◆ createNode() [1/2]

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::createNode	(	const K_TYPE &	key = K_TYPE{},
		const V_TYPE &	value = V_TYPE{},
		color	color = RED,
		RBNode *	parent = nullptr,
		RBNode *	left = nullptr,
		RBNode *	right = nullptr ) const

protected

Creates a new node with given parameters.

Parameters

key	Key for new node
value	Value for new node
color	Initial color (default: RED)
parent	Parent node pointer (default: nullptr)
left	Left child pointer (default: nullptr)
right	Right child pointer (default: nullptr)

Returns: Pointer to newly created node

Uses allocator to construct node in place

◆ createNode() [2/2]

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::createNode ( RBNode && other_node ) const

protected

Creates a new node by moving from another node.

Parameters

other_node Node to move from

Returns: Pointer to newly created node

Performs move construction of node

◆ destroyNode()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

void original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::destroyNode ( RBNode * node )

protectednoexcept

Destroys a node and deallocates memory.

Parameters

node	Node to destroy

Uses allocator to destroy and deallocate node

◆ destroyTree()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

void original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::destroyTree ( )

protectednoexcept

Destroys entire tree and deallocates all nodes.

Uses breadth-first traversal to destroy all nodes

◆ erase()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::erase ( const K_TYPE & key )

protected

Erases node with given key.

Parameters

key	Key to erase

Returns: true if key was found and erased

Automatically balances tree after deletion

◆ find()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::find ( const K_TYPE & key ) const

protected

Finds node with given key.

Parameters

key	Key to search for

Returns: Pointer to found node, or nullptr if not found

Uses binary search tree traversal

◆ getMaxNode()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::getMaxNode ( ) const

protected

Gets the maximum node in the tree.

Returns: Pointer to the node with maximum key

Traverses right children until reaching the rightmost node

◆ getMinNode()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::getMinNode ( ) const

protected

Gets the minimum node in the tree.

Returns: Pointer to the node with minimum key

Traverses left children until reaching the leftmost node

◆ getPrecursorNode()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::getPrecursorNode ( RBNode * cur ) const

protected

Gets precursor node (in-order predecessor)

Parameters

cur	Current node

Returns: Pointer to precursor node

◆ getSuccessorNode()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::getSuccessorNode ( RBNode * cur ) const

protected

Gets successor node (in-order successor)

Parameters

cur	Current node

Returns: Pointer to successor node

◆ highPriority() [1/2]

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::highPriority	(	const K_TYPE &	key,
		RBNode *	other ) const

protected

Compares priority between a key and a node.

Parameters

key	Key to compare
other	Node to compare

Returns: true if key has higher priority than node's key

Uses the tree's comparison function

◆ highPriority() [2/2]

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::highPriority	(	RBNode *	cur,
		RBNode *	other ) const

protected

Compares priority between two nodes.

Parameters

cur	First node to compare
other	Second node to compare

Returns: true if cur has higher priority than other

Uses the tree's comparison function

◆ insert()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::insert	(	const K_TYPE &	key,
		const V_TYPE &	value )

protected

Inserts new key-value pair.

Parameters

key	Key to insert
value	Value to insert

Returns: true if inserted, false if key already existed

Automatically balances tree after insertion

◆ modify()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

bool original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::modify	(	const K_TYPE &	key,
		const V_TYPE &	value )

protected

Modifies value for existing key.

Parameters

key	Key to modify
value	New value to set

Returns: true if key was found and modified

◆ replaceNode()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::replaceNode	(	RBNode *	src,
		RBNode *	tar )

protected

Replaces one node with another while maintaining tree structure.

Parameters

src	Source node to replace with
tar	Target node to be replaced

Returns: Pointer to the original source node

Preserves all connections and colors during replacement

◆ rotateLeft()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::rotateLeft ( RBNode * cur )

protected

Performs left rotation around a node.

Parameters

cur	Node to rotate around

Returns: New root node after rotation

Maintains tree properties during rotation

◆ rotateRight()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::rotateRight ( RBNode * cur )

protected

Performs right rotation around a node.

Parameters

cur	Node to rotate around

Returns: New root node after rotation

Maintains tree properties during rotation

◆ treeCopy()

template<typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>

original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::RBNode * original::RBTree< K_TYPE, V_TYPE, ALLOC, Compare >::treeCopy ( ) const

protected

Creates a deep copy of the tree.

Returns: Pointer to root of copied tree

The documentation for this class was generated from the following file:

src/core/RBTree.h

Classes

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RBTree()

◆ ~RBTree()

Member Function Documentation

◆ adjustErase()

◆ adjustInsert()

◆ createNode() [1/2]

◆ createNode() [2/2]

◆ destroyNode()

◆ destroyTree()

◆ erase()

◆ find()

◆ getMaxNode()

◆ getMinNode()

◆ getPrecursorNode()

◆ getSuccessorNode()

◆ highPriority() [1/2]

◆ highPriority() [2/2]

◆ insert()

◆ modify()

◆ replaceNode()

◆ rotateLeft()

◆ rotateRight()

◆ treeCopy()