Red-black binary search tree implementation (bottom-up). More...

#include <tpl_rb_tree.H>

Inheritance diagram for Aleph::Gen_Rb_Tree< NodeType, Key, Compare >:

Collaboration diagram for Aleph::Gen_Rb_Tree< NodeType, Key, Compare >:

Classes
struct	Iterator
	Iterator over tree nodes in sorted order. More...

Public Types
using	Node = NodeType< Key >

using	key_type = Key

using	compare_type = Compare

Public Member Functions
Compare &	key_comp () noexcept
	Returns a reference to the comparison criteria.

const Compare &	key_comp () const noexcept

Compare &	get_compare () noexcept

const Compare &	get_compare () const noexcept

	Gen_Rb_Tree (Compare __cmp=Compare()) noexcept
	Default constructor with optional comparator.

void	swap (Gen_Rb_Tree &tree) noexcept
	Swaps all elements with another tree in constant time.

	Gen_Rb_Tree (Gen_Rb_Tree &&tree) noexcept
	Move constructor.

Gen_Rb_Tree &	operator= (Gen_Rb_Tree &&tree) noexcept
	Move assignment operator.

virtual	~Gen_Rb_Tree ()=default
	Destructor.

Node *	search (const Key &key) const noexcept
	Search for a key in the tree.

Node *&	getRoot () noexcept
	Get reference to root pointer.

Node *	getRoot () const noexcept
	Get const root pointer.

bool	is_empty () const noexcept
	Returns true if the tree is empty.

size_t	size () const noexcept
	Returns the number of nodes in the tree (O(1))

void	reset () noexcept
	Reset tree to empty state (does not free nodes)

Node *	insert (Node *p) noexcept
	Insert a node into the tree.

Node *	search_or_insert (Node *p) noexcept
	Search for key or insert if not found.

Node *	insert_dup (Node *p) noexcept
	Insert a node allowing duplicates.

bool	verify () const noexcept
	Verify that tree satisfies red-black properties.

Node *	remove (const Key &key) noexcept
	Remove the node containing key.

Private Member Functions
Node *	search_and_stack_rb (const Key &key, signed char &cmp_result) noexcept
	Search for key and stack ancestors (optimistic duplicate detection)

Node *	search_dup_and_stack_rb (const Key &key, signed char &cmp_result) noexcept
	Search for insertion point (allows duplicates) and stack ancestors.

void	fix_red_condition (Node *p) noexcept
	Fix red-red violation after insertion.

void	find_succ_and_swap (Node p, Node &pp) noexcept
	Find successor and swap with node being deleted.

void	fix_black_condition (Node *p) noexcept
	Fix black-height violation after deletion.

void	init () noexcept
	Initialize tree state.

Private Attributes
Node	head_node
	Sentinel header node.

Node *	head
	Pointer to sentinel.

Node *&	root
	Reference to root (right child of head)

FixedStack< Node * >	rb_stack
	Stack for ancestor path.

Compare	cmp
	Comparison functor.

size_t	num_nodes
	Number of nodes in tree.

Static Private Attributes
static constexpr signed char	CmpLess = -1

static constexpr signed char	CmpEqual = 0

static constexpr signed char	CmpGreater = 1

Detailed Description

template<template< typename > class NodeType, typename Key, class Compare>
class Aleph::Gen_Rb_Tree< NodeType, Key, Compare >

Red-black binary search tree implementation (bottom-up).

A red-black tree is a self-balancing binary search tree where each node has a color (red or black). The tree maintains balance through five invariants that guarantee the height is at most 2*log₂(n+1), ensuring O(log n) worst-case time for all operations.

Red-Black Tree Properties:

Every node is either red or black
The root is black
All leaves (null nodes) are black
Red nodes have only black children
Every path from root to leaf has the same number of black nodes

These properties ensure the tree remains approximately balanced, with the longest path at most twice the length of the shortest path.

This is the bottom-up implementation that uses a stack to track ancestors during descent and repairs violations by ascending back to the root.

Template Parameters

NodeType	Node template (typically RbNode or RbNodeVtl).
Key	The type of keys stored in the tree.
Compare	Comparison functor for ordering keys.

Complexity:

Search: O(log n) worst case
Insert: O(log n) worst case, at most 2 rotations
Delete: O(log n) worst case, at most 3 rotations
Size: O(1)
Space: O(n) + O(log n) for ancestor stack during operations

Example:: Rb_Tree<int> tree;

tree.insert(new Rb_Tree<int>::Node(42));

tree.insert(new Rb_Tree<int>::Node(17));

tree.insert(new Rb_Tree<int>::Node(99));

auto node = tree.search(42);

if (node != nullptr)

std::cout << "Found: " << node->get_key() << '\n';

tree.remove(42);

Aleph::Gen_Rb_Tree::insert
Node * insert(Node *p) noexcept
Insert a node into the tree.
Definition tpl_rb_tree.H:511

Aleph::Gen_Rb_Tree::search
Node * search(const Key &key) const noexcept
Search for a key in the tree.
Definition tpl_rb_tree.H:472

Aleph::Gen_Rb_Tree::Node
NodeType< Key > Node
Definition tpl_rb_tree.H:121

Aleph::Gen_Rb_Tree::remove
Node * remove(const Key &key) noexcept
Remove the node containing key.
Definition tpl_rb_tree.H:611

Aleph::Rb_Tree
Red-black tree with nodes without virtual destructor.
Definition tpl_rb_tree.H:683

Note: This is a low-level implementation managing raw nodes. For automatic memory management, use DynSetRbTree.

See also: GenTdRbTree Top-down (single-pass) alternative implementation.; DynSetRbTree High-level wrapper with automatic memory management.; Avl_Tree Alternative balanced tree (stricter balance, more rotations).

Definition at line 118 of file tpl_rb_tree.H.

Member Typedef Documentation

◆ compare_type

template<template< typename > class NodeType, typename Key , class Compare >

using Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::compare_type = Compare

Definition at line 123 of file tpl_rb_tree.H.

◆ key_type

template<template< typename > class NodeType, typename Key , class Compare >

using Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::key_type = Key

Definition at line 122 of file tpl_rb_tree.H.

◆ Node

template<template< typename > class NodeType, typename Key , class Compare >

using Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::Node = NodeType<Key>

Definition at line 121 of file tpl_rb_tree.H.

Constructor & Destructor Documentation

◆ Gen_Rb_Tree() [1/2]

template<template< typename > class NodeType, typename Key , class Compare >

Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::Gen_Rb_Tree ( Compare __cmp = Compare() )

inlinenoexcept

Default constructor with optional comparator.

Definition at line 423 of file tpl_rb_tree.H.

◆ Gen_Rb_Tree() [2/2]

template<template< typename > class NodeType, typename Key , class Compare >

Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::Gen_Rb_Tree ( Gen_Rb_Tree< NodeType, Key, Compare > && tree )

inlinenoexcept

Move constructor.

Definition at line 441 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root.

◆ ~Gen_Rb_Tree()

template<template< typename > class NodeType, typename Key , class Compare >

virtual Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::~Gen_Rb_Tree ( )

virtualdefault

Destructor.

Member Function Documentation

◆ find_succ_and_swap()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::find_succ_and_swap	(	Node *	p,
		Node *&	pp
	)

inlineprivatenoexcept

Find successor and swap with node being deleted.

Definition at line 266 of file tpl_rb_tree.H.

References COLOR, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::push(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::rb_stack, Aleph::RLINK(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::remove().

◆ fix_black_condition()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::fix_black_condition ( Node * p )

inlineprivatenoexcept

Fix black-height violation after deletion.

Definition at line 311 of file tpl_rb_tree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::popn(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::rb_stack, RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root, Aleph::rotate_to_left(), Aleph::rotate_to_right(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::remove().

◆ fix_red_condition()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::fix_red_condition ( Node * p )

inlineprivatenoexcept

Fix red-red violation after insertion.

Definition at line 204 of file tpl_rb_tree.H.

References BLACK, COLOR, Aleph::FixedStack< T >::empty(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::rb_stack, RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root, Aleph::rotate_to_left(), and Aleph::rotate_to_right().

Referenced by Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert_dup(), and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_or_insert().

◆ get_compare() [1/2]

template<template< typename > class NodeType, typename Key , class Compare >

const Compare & Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::get_compare ( ) const

inlinenoexcept

Definition at line 420 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp.

◆ get_compare() [2/2]

template<template< typename > class NodeType, typename Key , class Compare >

Compare & Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::get_compare ( )

inlinenoexcept

Definition at line 419 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp.

◆ getRoot() [1/2]

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::getRoot ( ) const

inlinenoexcept

Get const root pointer.

Definition at line 491 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root.

◆ getRoot() [2/2]

template<template< typename > class NodeType, typename Key , class Compare >

Node *& Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::getRoot ( )

inlinenoexcept

Get reference to root pointer.

Definition at line 488 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root.

Referenced by write_rb().

◆ init()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::init ( )

inlineprivatenoexcept

Initialize tree state.

Definition at line 408 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::num_nodes.

◆ insert()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert ( Node * p )

inlinenoexcept

Insert a node into the tree.

Parameters

p	Node to insert (must be red with null children).

Returns: Pointer to inserted node, or nullptr if key already exists.

Definition at line 511 of file tpl_rb_tree.H.

Referenced by RbTreeTest::insert_values(), and write_rb().

◆ insert_dup()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert_dup ( Node * p )

inlinenoexcept

Insert a node allowing duplicates.

Parameters

p	Node to insert.

Returns: Pointer to inserted node (always succeeds).

Definition at line 579 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpEqual, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpLess, COLOR, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::fix_red_condition(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::num_nodes, RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root, and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_dup_and_stack_rb().

◆ is_empty()

template<template< typename > class NodeType, typename Key , class Compare >

bool Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::is_empty ( ) const

inlinenoexcept

Returns true if the tree is empty.

Definition at line 494 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root.

◆ key_comp() [1/2]

template<template< typename > class NodeType, typename Key , class Compare >

const Compare & Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::key_comp ( ) const

inlinenoexcept

Definition at line 416 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp.

◆ key_comp() [2/2]

template<template< typename > class NodeType, typename Key , class Compare >

Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::key_comp ( )

inlinenoexcept

Returns a reference to the comparison criteria.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 415 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp.

◆ operator=()

template<template< typename > class NodeType, typename Key , class Compare >

Gen_Rb_Tree & Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::operator= ( Gen_Rb_Tree< NodeType, Key, Compare > && tree )

inlinenoexcept

Move assignment operator.

Definition at line 452 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::num_nodes, and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root.

◆ remove()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::remove ( const Key & key )

inlinenoexcept

Remove the node containing key.

Parameters

key	Key to remove.

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

Definition at line 611 of file tpl_rb_tree.H.

References BLACK, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpEqual, COLOR, Aleph::FixedStack< T >::empty(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::find_succ_and_swap(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::fix_black_condition(), Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::num_nodes, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::rb_stack, Aleph::RLINK(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_and_stack_rb(), and Aleph::FixedStack< T >::top().

◆ reset()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::reset ( )

inlinenoexcept

Reset tree to empty state (does not free nodes)

Definition at line 500 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::num_nodes, and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root.

◆ search()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search ( const Key & key ) const

inlinenoexcept

Search for a key in the tree.

Parameters

key	Key to search for.

Returns: Pointer to node containing key, or nullptr if not found.

Definition at line 472 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp, KEY, Aleph::LLINK(), Aleph::RLINK(), and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root.

Referenced by write_rb().

◆ search_and_stack_rb()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_and_stack_rb	(	const Key &	key,
		signed char &	cmp_result
	)

inlineprivatenoexcept

Search for key and stack ancestors (optimistic duplicate detection)

Definition at line 137 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpEqual, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpGreater, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpLess, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::head, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::popn(), Aleph::FixedStack< T >::push(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::rb_stack, Aleph::RLINK(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root, Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::remove(), and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_or_insert().

◆ search_dup_and_stack_rb()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_dup_and_stack_rb	(	const Key &	key,
		signed char &	cmp_result
	)

inlineprivatenoexcept

Search for insertion point (allows duplicates) and stack ancestors.

Definition at line 177 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpEqual, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpGreater, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpLess, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::head, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::push(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::rb_stack, Aleph::RLINK(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root, and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert_dup().

◆ search_or_insert()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_or_insert ( Node * p )

inlinenoexcept

Search for key or insert if not found.

Parameters

p	Node to search or insert.

Returns: Pointer to p if inserted, or pointer to existing node with same key.

Definition at line 545 of file tpl_rb_tree.H.

◆ size()

template<template< typename > class NodeType, typename Key , class Compare >

size_t Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::size ( ) const

inlinenoexcept

Returns the number of nodes in the tree (O(1))

Definition at line 497 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::num_nodes.

◆ swap()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::swap ( Gen_Rb_Tree< NodeType, Key, Compare > & tree )

inlinenoexcept

Swaps all elements with another tree in constant time.

Parameters

[in] tree the red-black tree to swap with

Definition at line 433 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp, Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::num_nodes, and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root.

◆ verify()

template<template< typename > class NodeType, typename Key , class Compare >

bool Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::verify ( ) const

inlinenoexcept

Verify that tree satisfies red-black properties.

Definition at line 604 of file tpl_rb_tree.H.

References Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp, is_red_black_bst(), and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root.

Member Data Documentation

◆ cmp

template<template< typename > class NodeType, typename Key , class Compare >

Compare Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::cmp

private

Comparison functor.

Definition at line 130 of file tpl_rb_tree.H.

◆ CmpEqual

template<template< typename > class NodeType, typename Key , class Compare >

constexpr signed char Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpEqual = 0

staticconstexprprivate

Definition at line 133 of file tpl_rb_tree.H.

Referenced by Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::remove(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_and_stack_rb(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_dup_and_stack_rb(), and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_or_insert().

◆ CmpGreater

template<template< typename > class NodeType, typename Key , class Compare >

constexpr signed char Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpGreater = 1

staticconstexprprivate

Definition at line 134 of file tpl_rb_tree.H.

Referenced by Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_and_stack_rb(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_dup_and_stack_rb(), and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_or_insert().

◆ CmpLess

template<template< typename > class NodeType, typename Key , class Compare >

constexpr signed char Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::CmpLess = -1

staticconstexprprivate

Definition at line 132 of file tpl_rb_tree.H.

Referenced by Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_and_stack_rb(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_dup_and_stack_rb(), and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_or_insert().

◆ head

template<template< typename > class NodeType, typename Key , class Compare >

Node* Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::head

private

Pointer to sentinel.

Definition at line 127 of file tpl_rb_tree.H.

Referenced by Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_and_stack_rb(), and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_dup_and_stack_rb().

◆ head_node

template<template< typename > class NodeType, typename Key , class Compare >

Node Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::head_node

private

Sentinel header node.

Definition at line 126 of file tpl_rb_tree.H.

◆ num_nodes

template<template< typename > class NodeType, typename Key , class Compare >

size_t Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::num_nodes

private

Number of nodes in tree.

Definition at line 131 of file tpl_rb_tree.H.

◆ rb_stack

template<template< typename > class NodeType, typename Key , class Compare >

FixedStack<Node *> Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::rb_stack

private

Stack for ancestor path.

Definition at line 129 of file tpl_rb_tree.H.

◆ root

template<template< typename > class NodeType, typename Key , class Compare >

Node*& Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::root

private

Reference to root (right child of head)

Definition at line 128 of file tpl_rb_tree.H.

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

tpl_rb_tree.H

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ compare_type

◆ key_type

◆ Node

Constructor & Destructor Documentation

◆ Gen_Rb_Tree() [1/2]

◆ Gen_Rb_Tree() [2/2]

◆ ~Gen_Rb_Tree()

Member Function Documentation

◆ find_succ_and_swap()

◆ fix_black_condition()

◆ fix_red_condition()

◆ get_compare() [1/2]

◆ get_compare() [2/2]

◆ getRoot() [1/2]

◆ getRoot() [2/2]

◆ init()

◆ insert()

◆ insert_dup()

◆ is_empty()

◆ key_comp() [1/2]

◆ key_comp() [2/2]

◆ operator=()

◆ remove()

◆ reset()

◆ search()

◆ search_and_stack_rb()

◆ search_dup_and_stack_rb()

◆ search_or_insert()

◆ size()

◆ swap()

◆ verify()

Member Data Documentation

◆ cmp

◆ CmpEqual

◆ CmpGreater

◆ CmpLess

◆ head

◆ head_node

◆ num_nodes

◆ rb_stack

◆ root