Hybrid top-down/bottom-up red-black tree. More...

#include <tpl_hRbTree.H>

Inheritance diagram for Aleph::HtdRbTree< Key, Compare >:

Collaboration diagram for Aleph::HtdRbTree< Key, Compare >:

Classes
struct	Iterator
	In-order iterator. More...

Public Types
using	Color = unsigned char
	Color type for red-black nodes.

using	Node = RbNode< Key >
	The node type used by this tree.

using	key_type = Key
	The key type stored in nodes.

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

const Compare &	key_comp () const noexcept

Compare &	get_compare () noexcept
	Alias for key_comp()

constexpr const Compare &	get_compare () const noexcept

	HtdRbTree (Compare __cmp=Compare()) noexcept
	Default constructor.

void	swap (HtdRbTree &tree) noexcept
	Swap contents with another tree.

	HtdRbTree (HtdRbTree &&tree) noexcept
	Move constructor.

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

	HtdRbTree (const HtdRbTree &)=delete
	Copy constructor deleted.

HtdRbTree &	operator= (const HtdRbTree &)=delete
	Copy assignment deleted.

virtual	~HtdRbTree ()=default
	Virtual destructor.

constexpr bool	is_empty () const noexcept
	Check if tree is empty.

constexpr size_t	size () const noexcept
	Get number of nodes in tree.

void	reset () noexcept
	Reset tree (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 allowing duplicate keys.

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

Node *	remove (const Key &key) noexcept
	Remove node with given key.

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

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

void	verifyRedBlack () const
	Verify red-black tree invariants (DEBUG mode).

bool	verify () const noexcept
	Verify tree is a valid red-black BST.

Private Member Functions
void	restoreRedCondition (Node p, Node &fp, Node ffp, Node fffp)
	Restore red-black condition after insertion.

Node *	searchFlipColorsAndInsert (Node *q) noexcept
	Search for insertion point with proactive color flipping.

Node *	searchFlipColorsAndInsertDup (Node *q) noexcept
	Like searchFlipColorsAndInsert but allows duplicate keys.

Node *	searchAndBuildPath (const Key &key) noexcept
	Search for key while building path stack.

void	findSuccAndSwap (Node p, Node &fp) noexcept
	Find successor and swap with node to delete.

void	balanceDownAndColor (Node p, Node &fp, Node *&sp) noexcept
	Balance down a violating black node.

void	rotateNephewAndColor (Node fp, Node sp, Node *np) noexcept
	Rotate nephew up and recolor to fix violation.

void	doubleRotateNephewAndColor (Node fp, Node sp, Node *snp) noexcept
	Double rotation and recolor to fix violation.

void	removeAndFixBlackCondition (Node *q) noexcept
	Remove node and fix any black-height violations.

Static Private Member Functions
static Node *	getSibling (Node p, Node fp) noexcept
	Returns sibling of p given its parent fp.

static void	flipColors (Node *p) noexcept
	Flip colors of a black node with two red children.

static void	colorSiblingAsRed (Node *sp) noexcept
	Color sibling red to propagate violation upward.

static void	colorParentAndSibling (Node fp, Node sp) noexcept
	Recolor parent and sibling to fix violation.

static void	blackHeight (Node *p, int &max, int bh=0) noexcept
	Verify black height consistency.

static void	testNode (Node *p) noexcept
	Verify red condition and black height for a node.

Private Attributes
Node	headNode
	Auxiliary node, parent of root.

Node	headParent
	Auxiliary node, grandparent of root.

Node	headGrandParent
	Auxiliary node, great-grandparent of root.

Node *	head
	Pointer to head node.

Node *	fHead
	Pointer to head's parent.

Node *	ffHead
	Pointer to head's grandparent.

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

FixedStack< Node * >	path {Node::MaxHeight}
	Stack for deletion path.

size_t	node_count = 0
	Number of nodes in tree.

Compare	cmp
	Comparison functor.

Detailed Description

template<class Key, class Compare = Aleph::less<Key>>
class Aleph::HtdRbTree< Key, Compare >

Hybrid top-down/bottom-up red-black tree.

This class implements a self-balancing binary search tree using the red-black tree algorithm with a hybrid approach:

Insertion: Top-down with proactive color flipping. As we descend to find the insertion point, we preemptively flip colors of nodes with two red children. This ensures the tree remains balanced with at most one rotation after insertion.
Deletion: Bottom-up using a stack to track ancestors. After removing a node, we fix any violations by walking back up the path.

Complexity:

All operations (insert, remove, search): O(log n)
Space: O(n) + O(log n) stack for deletion

Template Parameters

Key	The type of keys stored in the tree
Compare	Comparison functor (default: Aleph::less<Key>)

Author: Leandro Rabindranath León

Definition at line 83 of file tpl_hRbTree.H.

Member Typedef Documentation

◆ Color

template<class Key , class Compare = Aleph::less<Key>>

using Aleph::HtdRbTree< Key, Compare >::Color = unsigned char

Color type for red-black nodes.

Definition at line 87 of file tpl_hRbTree.H.

◆ key_type

template<class Key , class Compare = Aleph::less<Key>>

using Aleph::HtdRbTree< Key, Compare >::key_type = Key

The key type stored in nodes.

Definition at line 749 of file tpl_hRbTree.H.

◆ Node

template<class Key , class Compare = Aleph::less<Key>>

using Aleph::HtdRbTree< Key, Compare >::Node = RbNode<Key>

The node type used by this tree.

Definition at line 90 of file tpl_hRbTree.H.

Constructor & Destructor Documentation

◆ HtdRbTree() [1/3]

template<class Key , class Compare = Aleph::less<Key>>

Aleph::HtdRbTree< Key, Compare >::HtdRbTree ( Compare __cmp = Compare() )

inlinenoexcept

Default constructor.

Definition at line 764 of file tpl_hRbTree.H.

References BLACK, COLOR, Aleph::HtdRbTree< Key, Compare >::ffHead, Aleph::HtdRbTree< Key, Compare >::fHead, Aleph::HtdRbTree< Key, Compare >::head, RbNode< Key >::NullPtr, and Aleph::RLINK().

◆ HtdRbTree() [2/3]

template<class Key , class Compare = Aleph::less<Key>>

Aleph::HtdRbTree< Key, Compare >::HtdRbTree ( HtdRbTree< Key, Compare > && tree )

inlinenoexcept

Move constructor.

Definition at line 788 of file tpl_hRbTree.H.

References BLACK, COLOR, Aleph::HtdRbTree< Key, Compare >::ffHead, Aleph::HtdRbTree< Key, Compare >::fHead, Aleph::HtdRbTree< Key, Compare >::head, RbNode< Key >::NullPtr, Aleph::RLINK(), and Aleph::HtdRbTree< Key, Compare >::swap().

◆ HtdRbTree() [3/3]

template<class Key , class Compare = Aleph::less<Key>>

Aleph::HtdRbTree< Key, Compare >::HtdRbTree ( const HtdRbTree< Key, Compare > & )

delete

Copy constructor deleted.

◆ ~HtdRbTree()

template<class Key , class Compare = Aleph::less<Key>>

virtual Aleph::HtdRbTree< Key, Compare >::~HtdRbTree ( )

virtualdefault

Virtual destructor.

Member Function Documentation

◆ balanceDownAndColor()

template<class Key , class Compare = Aleph::less<Key>>

void Aleph::HtdRbTree< Key, Compare >::balanceDownAndColor	(	Node *	p,
		Node *&	fp,
		Node *&	sp
	)

inlineprivatenoexcept

Balance down a violating black node.

When sibling is red, rotate to make it black. This ensures the sibling-black cases can be applied.

Precondition: p is black, fp is black, sp is red

Parameters

p	Violating node (black, missing a black node)
fp	Parent of p (updated)
sp	Sibling of p (updated to new sibling, which will be black)

Definition at line 483 of file tpl_hRbTree.H.

References BLACK, COLOR, Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::path, RED, Aleph::RLINK(), Aleph::rotate_to_left(), Aleph::rotate_to_right(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::HtdRbTree< Key, Compare >::removeAndFixBlackCondition().

◆ blackHeight()

template<class Key , class Compare = Aleph::less<Key>>

static void Aleph::HtdRbTree< Key, Compare >::blackHeight	(	Node *	p,
		int &	max,
		int	bh = `0`
	)

inlinestaticprivatenoexcept

Verify black height consistency.

Recursively checks that all paths to leaves have the same number of black nodes.

Parameters

p	Node to check from
max	Current maximum black height (initialize to -1)
bh	Current black height count

Definition at line 959 of file tpl_hRbTree.H.

References BLACK, Aleph::HtdRbTree< Key, Compare >::blackHeight(), COLOR, Aleph::LLINK(), Aleph::maps(), max(), RbNode< Key >::NullPtr, and Aleph::RLINK().

Referenced by Aleph::HtdRbTree< Key, Compare >::blackHeight(), and Aleph::HtdRbTree< Key, Compare >::testNode().

◆ colorParentAndSibling()

template<class Key , class Compare = Aleph::less<Key>>

static void Aleph::HtdRbTree< Key, Compare >::colorParentAndSibling	(	Node *	fp,
		Node *	sp
	)

inlinestaticprivatenoexcept

Recolor parent and sibling to fix violation.

Case: parent is red. Swapping colors fixes the tree.

Parameters

fp	Parent (red)
sp	Sibling (black)

Definition at line 612 of file tpl_hRbTree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), RED, and Aleph::RLINK().

Referenced by Aleph::HtdRbTree< Key, Compare >::removeAndFixBlackCondition().

◆ colorSiblingAsRed()

template<class Key , class Compare = Aleph::less<Key>>

static void Aleph::HtdRbTree< Key, Compare >::colorSiblingAsRed ( Node * sp )

inlinestaticprivatenoexcept

Color sibling red to propagate violation upward.

After this, fp becomes the new violating node.

Parameters

sp	Sibling (black, both children black)

Definition at line 599 of file tpl_hRbTree.H.

References BLACK, COLOR, Aleph::maps(), and RED.

Referenced by Aleph::HtdRbTree< Key, Compare >::removeAndFixBlackCondition().

◆ doubleRotateNephewAndColor()

template<class Key , class Compare = Aleph::less<Key>>

void Aleph::HtdRbTree< Key, Compare >::doubleRotateNephewAndColor	(	Node *	fp,
		Node *	sp,
		Node *	snp
	)

inlineprivatenoexcept

Double rotation and recolor to fix violation.

Case: nephew snp is red and on the "inside" (opposite side from sibling). Double rotation (rotate sibling, then parent) fixes the tree.

Precondition: sp is black, snp is red

Parameters

fp	Parent of violating node
sp	Sibling (black)
snp	Sibling's nephew (red, opposite side from sp)

Definition at line 563 of file tpl_hRbTree.H.

References BLACK, COLOR, Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::path, RED, Aleph::RLINK(), Aleph::rotate_to_left(), Aleph::rotate_to_right(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::HtdRbTree< Key, Compare >::removeAndFixBlackCondition().

◆ findSuccAndSwap()

template<class Key , class Compare = Aleph::less<Key>>

void Aleph::HtdRbTree< Key, Compare >::findSuccAndSwap	(	Node *	p,
		Node *&	fp
	)

inlineprivatenoexcept

Find successor and swap with node to delete.

Used during deletion when the node has two children. Finds the in-order successor and swaps pointers (not contents).

Parameters

p	Node to delete
fp	Parent of p (updated to point to new position)

Definition at line 400 of file tpl_hRbTree.H.

References COLOR, Aleph::LLINK(), log(), Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::node_count, RbNode< Key >::NullPtr, Aleph::HtdRbTree< Key, Compare >::path, Aleph::FixedStack< T >::push(), Aleph::RLINK(), Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::HtdRbTree< Key, Compare >::removeAndFixBlackCondition().

◆ flipColors()

template<class Key , class Compare = Aleph::less<Key>>

static void Aleph::HtdRbTree< Key, Compare >::flipColors ( Node * p )

inlinestaticprivatenoexcept

Flip colors of a black node with two red children.

The black node becomes red and its children become black. This is the key operation for top-down insertion.

Parameters

p	Node to flip (must be black with two red children)

Definition at line 185 of file tpl_hRbTree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), RbNode< Key >::NullPtr, RED, and Aleph::RLINK().

Referenced by Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsert(), and Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsertDup().

◆ get_compare() [1/2]

template<class Key , class Compare = Aleph::less<Key>>

Aleph::HtdRbTree< Key, Compare >::get_compare ( ) const

inlineconstexprnoexcept

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 761 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::cmp.

◆ get_compare() [2/2]

template<class Key , class Compare = Aleph::less<Key>>

Compare & Aleph::HtdRbTree< Key, Compare >::get_compare ( )

inlinenoexcept

Alias for key_comp()

Definition at line 758 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::cmp.

◆ getRoot() [1/2]

template<class Key , class Compare = Aleph::less<Key>>

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

inlinenoexcept

Get root pointer (const)

Definition at line 947 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::root.

◆ getRoot() [2/2]

template<class Key , class Compare = Aleph::less<Key>>

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

inlinenoexcept

Get reference to root pointer.

Definition at line 944 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::root.

◆ getSibling()

template<class Key , class Compare = Aleph::less<Key>>

static Node * Aleph::HtdRbTree< Key, Compare >::getSibling	(	Node *	p,
		Node *	fp
	)

inlinestaticprivatenoexcept

Returns sibling of p given its parent fp.

Definition at line 111 of file tpl_hRbTree.H.

References Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::HtdRbTree< Key, Compare >::removeAndFixBlackCondition().

◆ insert()

template<class Key , class Compare = Aleph::less<Key>>

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

inlinenoexcept

Insert a node into the tree.

Parameters

p	Node to insert (must have COLOR=RED and null children)

Returns: Pointer to inserted node, or nullptr if duplicate key

Definition at line 840 of file tpl_hRbTree.H.

References COLOR, Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::node_count, RbNode< Key >::NullPtr, RED, Aleph::RLINK(), Aleph::HtdRbTree< Key, Compare >::root, and Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsert().

Referenced by Aleph::HtdRbTree< Key, Compare >::search_or_insert().

◆ insert_dup()

template<class Key , class Compare = Aleph::less<Key>>

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

inlinenoexcept

Insert allowing duplicate keys.

Parameters

p	Node to insert

Returns: Pointer to inserted node

Definition at line 887 of file tpl_hRbTree.H.

References COLOR, Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::node_count, RbNode< Key >::NullPtr, RED, Aleph::RLINK(), Aleph::HtdRbTree< Key, Compare >::root, and Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsertDup().

◆ is_empty()

template<class Key , class Compare = Aleph::less<Key>>

constexpr bool Aleph::HtdRbTree< Key, Compare >::is_empty ( ) const

inlineconstexprnoexcept

Check if tree is empty.

Definition at line 823 of file tpl_hRbTree.H.

References RbNode< Key >::NullPtr, and Aleph::HtdRbTree< Key, Compare >::root.

◆ key_comp() [1/2]

template<class Key , class Compare = Aleph::less<Key>>

Aleph::HtdRbTree< Key, Compare >::key_comp ( ) const

inlinenoexcept

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 755 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::cmp.

◆ key_comp() [2/2]

template<class Key , class Compare = Aleph::less<Key>>

Compare & Aleph::HtdRbTree< Key, Compare >::key_comp ( )

inlinenoexcept

Returns a reference to the comparison functor.

Definition at line 752 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::cmp.

◆ operator=() [1/2]

template<class Key , class Compare = Aleph::less<Key>>

HtdRbTree & Aleph::HtdRbTree< Key, Compare >::operator= ( const HtdRbTree< Key, Compare > & )

delete

Copy assignment deleted.

◆ operator=() [2/2]

template<class Key , class Compare = Aleph::less<Key>>

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

inlinenoexcept

Move assignment.

Definition at line 807 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::swap().

◆ remove()

template<class Key , class Compare = Aleph::less<Key>>

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

inlinenoexcept

Remove node with given key.

Parameters

key	Key to remove

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

Definition at line 919 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::cmp, Aleph::FixedStack< T >::empty(), KEY, Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::node_count, RbNode< Key >::NullPtr, Aleph::HtdRbTree< Key, Compare >::path, Aleph::HtdRbTree< Key, Compare >::removeAndFixBlackCondition(), RbNode< Key >::reset(), Aleph::HtdRbTree< Key, Compare >::root, and Aleph::HtdRbTree< Key, Compare >::searchAndBuildPath().

◆ removeAndFixBlackCondition()

template<class Key , class Compare = Aleph::less<Key>>

void Aleph::HtdRbTree< Key, Compare >::removeAndFixBlackCondition ( Node * q )

inlineprivatenoexcept

Remove node and fix any black-height violations.

Performs the actual BST deletion (bypass or swap with successor), then walks up the path fixing violations.

Parameters

q	Node to remove (must be on top of path stack)

Definition at line 629 of file tpl_hRbTree.H.

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

◆ reset()

template<class Key , class Compare = Aleph::less<Key>>

void Aleph::HtdRbTree< Key, Compare >::reset ( )

inlinenoexcept

Reset tree (does not free nodes)

Definition at line 829 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::node_count, RbNode< Key >::NullPtr, and Aleph::HtdRbTree< Key, Compare >::root.

◆ restoreRedCondition()

template<class Key , class Compare = Aleph::less<Key>>

void Aleph::HtdRbTree< Key, Compare >::restoreRedCondition	(	Node *	p,
		Node *&	fp,
		Node *	ffp,
		Node *	fffp
	)

inlineprivate

Restore red-black condition after insertion.

Called when we have two consecutive red nodes (p and fp are both red). Performs rotations to fix the violation.

Parameters

p	Violating node (red)
fp	Parent of p (red) - may be updated
ffp	Grandparent of p (black)
fffp	Great-grandparent of p

Definition at line 129 of file tpl_hRbTree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), RED, Aleph::RLINK(), Aleph::HtdRbTree< Key, Compare >::root, Aleph::rotate_to_left(), and Aleph::rotate_to_right().

Referenced by Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsert(), and Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsertDup().

◆ rotateNephewAndColor()

template<class Key , class Compare = Aleph::less<Key>>

void Aleph::HtdRbTree< Key, Compare >::rotateNephewAndColor	(	Node *	fp,
		Node *	sp,
		Node *	np
	)

inlineprivatenoexcept

Rotate nephew up and recolor to fix violation.

Case: nephew np is red and on the "outside" (same side as sibling). Single rotation fixes the tree.

Precondition: sp is black, np is red

Parameters

fp	Parent of violating node
sp	Sibling (black)
np	Nephew (red, same side as sp)

Definition at line 529 of file tpl_hRbTree.H.

References BLACK, COLOR, Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::path, RED, Aleph::RLINK(), Aleph::rotate_to_left(), Aleph::rotate_to_right(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::HtdRbTree< Key, Compare >::removeAndFixBlackCondition().

◆ search()

template<class Key , class Compare = Aleph::less<Key>>

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

inlinenoexcept

Search for a key.

Parameters

key	Key to search for

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

Definition at line 908 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::cmp, Aleph::maps(), RbNode< Key >::NullPtr, Aleph::HtdRbTree< Key, Compare >::root, and Aleph::searchInBinTree().

Referenced by Aleph::HtdRbTree< Key, Compare >::search_or_insert().

◆ search_or_insert()

template<class Key , class Compare = Aleph::less<Key>>

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

inlinenoexcept

Search for key or insert if not found.

Parameters

p	Node to insert if key not found

Returns: Existing node with key, or p if inserted

Definition at line 861 of file tpl_hRbTree.H.

References COLOR, Aleph::HtdRbTree< Key, Compare >::insert(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::node_count, RbNode< Key >::NullPtr, RED, Aleph::RLINK(), Aleph::HtdRbTree< Key, Compare >::root, and Aleph::HtdRbTree< Key, Compare >::search().

◆ searchAndBuildPath()

template<class Key , class Compare = Aleph::less<Key>>

Node * Aleph::HtdRbTree< Key, Compare >::searchAndBuildPath ( const Key & key )

inlineprivatenoexcept

Search for key while building path stack.

Used for deletion. The path stack is needed to walk back up the tree when fixing violations.

Parameters

key	Key to search for

Returns: Node with key, or leaf where key would be

Definition at line 345 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::cmp, Aleph::HtdRbTree< Key, Compare >::head, KEY, Aleph::LLINK(), log(), Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::node_count, RbNode< Key >::NullPtr, Aleph::HtdRbTree< Key, Compare >::path, Aleph::FixedStack< T >::push(), Aleph::RLINK(), Aleph::HtdRbTree< Key, Compare >::root, and Aleph::FixedStack< T >::size().

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

◆ searchFlipColorsAndInsert()

template<class Key , class Compare = Aleph::less<Key>>

Node * Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsert ( Node * q )

inlineprivatenoexcept

Search for insertion point with proactive color flipping.

Descends the tree looking for where to insert q. During descent, any node with two red children has its colors flipped preemptively.

Parameters

q	Node to insert

Returns: Pointer to inserted node, or nullptr if duplicate

Definition at line 203 of file tpl_hRbTree.H.

References BLACK, Aleph::HtdRbTree< Key, Compare >::cmp, COLOR, Aleph::HtdRbTree< Key, Compare >::ffHead, Aleph::HtdRbTree< Key, Compare >::fHead, Aleph::HtdRbTree< Key, Compare >::flipColors(), Aleph::HtdRbTree< Key, Compare >::head, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::node_count, RbNode< Key >::NullPtr, RED, Aleph::HtdRbTree< Key, Compare >::restoreRedCondition(), Aleph::RLINK(), and Aleph::HtdRbTree< Key, Compare >::root.

Referenced by Aleph::HtdRbTree< Key, Compare >::insert().

◆ searchFlipColorsAndInsertDup()

template<class Key , class Compare = Aleph::less<Key>>

Node * Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsertDup ( Node * q )

inlineprivatenoexcept

Like searchFlipColorsAndInsert but allows duplicate keys.

Definition at line 272 of file tpl_hRbTree.H.

References BLACK, Aleph::HtdRbTree< Key, Compare >::cmp, COLOR, Aleph::HtdRbTree< Key, Compare >::ffHead, Aleph::HtdRbTree< Key, Compare >::fHead, Aleph::HtdRbTree< Key, Compare >::flipColors(), Aleph::HtdRbTree< Key, Compare >::head, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTree< Key, Compare >::node_count, RbNode< Key >::NullPtr, RED, Aleph::HtdRbTree< Key, Compare >::restoreRedCondition(), Aleph::RLINK(), and Aleph::HtdRbTree< Key, Compare >::root.

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

◆ size()

template<class Key , class Compare = Aleph::less<Key>>

constexpr size_t Aleph::HtdRbTree< Key, Compare >::size ( ) const

inlineconstexprnoexcept

Get number of nodes in tree.

Definition at line 826 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::node_count.

◆ swap()

template<class Key , class Compare = Aleph::less<Key>>

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

inlinenoexcept

Swap contents with another tree.

Definition at line 780 of file tpl_hRbTree.H.

References Aleph::HtdRbTree< Key, Compare >::cmp, Aleph::HtdRbTree< Key, Compare >::node_count, and Aleph::HtdRbTree< Key, Compare >::root.

Referenced by Aleph::HtdRbTree< Key, Compare >::HtdRbTree(), and Aleph::HtdRbTree< Key, Compare >::operator=().

◆ testNode()

template<class Key , class Compare = Aleph::less<Key>>

static void Aleph::HtdRbTree< Key, Compare >::testNode ( Node * p )

inlinestaticprivatenoexcept

Verify red condition and black height for a node.

Definition at line 982 of file tpl_hRbTree.H.

References BLACK, Aleph::HtdRbTree< Key, Compare >::blackHeight(), COLOR, Aleph::LLINK(), Aleph::maps(), max(), RED, and Aleph::RLINK().

Referenced by Aleph::HtdRbTree< Key, Compare >::verifyRedBlack().

◆ verify()

template<class Key , class Compare = Aleph::less<Key>>

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

inlinenoexcept

Verify tree is a valid red-black BST.

Returns: true if all red-black properties hold

Definition at line 1009 of file tpl_hRbTree.H.

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

◆ verifyRedBlack()

template<class Key , class Compare = Aleph::less<Key>>

void Aleph::HtdRbTree< Key, Compare >::verifyRedBlack ( ) const

inline

Verify red-black tree invariants (DEBUG mode).

Checks that each node satisfies red-black conditions. Aborts on violation.

Definition at line 1000 of file tpl_hRbTree.H.

References Aleph::preOrderRec(), Aleph::HtdRbTree< Key, Compare >::root, and Aleph::HtdRbTree< Key, Compare >::testNode().

Member Data Documentation

◆ cmp

template<class Key , class Compare = Aleph::less<Key>>

Compare Aleph::HtdRbTree< Key, Compare >::cmp

private

Comparison functor.

Definition at line 108 of file tpl_hRbTree.H.

◆ ffHead

template<class Key , class Compare = Aleph::less<Key>>

Node* Aleph::HtdRbTree< Key, Compare >::ffHead

private

Pointer to head's grandparent.

Definition at line 101 of file tpl_hRbTree.H.

Referenced by Aleph::HtdRbTree< Key, Compare >::HtdRbTree(), Aleph::HtdRbTree< Key, Compare >::HtdRbTree(), Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsert(), and Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsertDup().

◆ fHead

template<class Key , class Compare = Aleph::less<Key>>

Node* Aleph::HtdRbTree< Key, Compare >::fHead

private

Pointer to head's parent.

Definition at line 100 of file tpl_hRbTree.H.

Referenced by Aleph::HtdRbTree< Key, Compare >::HtdRbTree(), Aleph::HtdRbTree< Key, Compare >::HtdRbTree(), Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsert(), and Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsertDup().

◆ head

template<class Key , class Compare = Aleph::less<Key>>

Node* Aleph::HtdRbTree< Key, Compare >::head

private

Pointer to head node.

Definition at line 99 of file tpl_hRbTree.H.

Referenced by Aleph::HtdRbTree< Key, Compare >::HtdRbTree(), Aleph::HtdRbTree< Key, Compare >::HtdRbTree(), Aleph::HtdRbTree< Key, Compare >::searchAndBuildPath(), Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsert(), and Aleph::HtdRbTree< Key, Compare >::searchFlipColorsAndInsertDup().

◆ headGrandParent

template<class Key , class Compare = Aleph::less<Key>>

Node Aleph::HtdRbTree< Key, Compare >::headGrandParent

private

Auxiliary node, great-grandparent of root.

Definition at line 97 of file tpl_hRbTree.H.

◆ headNode

template<class Key , class Compare = Aleph::less<Key>>

Node Aleph::HtdRbTree< Key, Compare >::headNode

private

Auxiliary node, parent of root.

Definition at line 95 of file tpl_hRbTree.H.

◆ headParent

template<class Key , class Compare = Aleph::less<Key>>

Node Aleph::HtdRbTree< Key, Compare >::headParent

private

Auxiliary node, grandparent of root.

Definition at line 96 of file tpl_hRbTree.H.

◆ node_count

template<class Key , class Compare = Aleph::less<Key>>

size_t Aleph::HtdRbTree< Key, Compare >::node_count = 0

private

Number of nodes in tree.

Definition at line 106 of file tpl_hRbTree.H.

◆ path

template<class Key , class Compare = Aleph::less<Key>>

FixedStack<Node *> Aleph::HtdRbTree< Key, Compare >::path {Node::MaxHeight}

private

Stack for deletion path.

Definition at line 104 of file tpl_hRbTree.H.

Referenced by Aleph::HtdRbTree< Key, Compare >::balanceDownAndColor(), Aleph::HtdRbTree< Key, Compare >::doubleRotateNephewAndColor(), Aleph::HtdRbTree< Key, Compare >::findSuccAndSwap(), Aleph::HtdRbTree< Key, Compare >::remove(), Aleph::HtdRbTree< Key, Compare >::removeAndFixBlackCondition(), Aleph::HtdRbTree< Key, Compare >::rotateNephewAndColor(), and Aleph::HtdRbTree< Key, Compare >::searchAndBuildPath().

◆ root

template<class Key , class Compare = Aleph::less<Key>>

Node*& Aleph::HtdRbTree< Key, Compare >::root

private

Reference to root (right child of head)

Definition at line 102 of file tpl_hRbTree.H.

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

tpl_hRbTree.H

Classes

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Color

◆ key_type

◆ Node

Constructor & Destructor Documentation

◆ HtdRbTree() [1/3]

◆ HtdRbTree() [2/3]

◆ HtdRbTree() [3/3]

◆ ~HtdRbTree()

Member Function Documentation

◆ balanceDownAndColor()

◆ blackHeight()

◆ colorParentAndSibling()

◆ colorSiblingAsRed()

◆ doubleRotateNephewAndColor()

◆ findSuccAndSwap()

◆ flipColors()

◆ get_compare() [1/2]

◆ get_compare() [2/2]

◆ getRoot() [1/2]

◆ getRoot() [2/2]

◆ getSibling()

◆ insert()

◆ insert_dup()

◆ is_empty()

◆ key_comp() [1/2]

◆ key_comp() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove()

◆ removeAndFixBlackCondition()

◆ reset()

◆ restoreRedCondition()

◆ rotateNephewAndColor()

◆ search()

◆ search_or_insert()

◆ searchAndBuildPath()

◆ searchFlipColorsAndInsert()

◆ searchFlipColorsAndInsertDup()

◆ size()

◆ swap()

◆ testNode()

◆ verify()

◆ verifyRedBlack()

Member Data Documentation

◆ cmp

◆ ffHead

◆ fHead

◆ head

◆ headGrandParent

◆ headNode

◆ headParent

◆ node_count

◆ path

◆ root