Aleph::GenTdRbTree< NodeType, Key, Compare > Class Template Reference

Top-down red-black binary search tree implementation. More...

#include <tpl_tdRbTree.H>

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

Collaboration diagram for Aleph::GenTdRbTree< 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
	GenTdRbTree () noexcept
	Default constructor.
	GenTdRbTree (const Compare &__cmp) noexcept
	Constructor with comparator.
	GenTdRbTree (GenTdRbTree &&other) noexcept
	Move constructor.
GenTdRbTree &	operator= (GenTdRbTree &&other) noexcept
	Move assignment operator.
	GenTdRbTree (const GenTdRbTree &)=delete
	Deleted copy constructor (use explicit copy if needed)
GenTdRbTree &	operator= (const GenTdRbTree &)=delete
	Deleted copy assignment.
void	reset () noexcept
	Reset tree to empty state (does not free nodes)
void	swap (GenTdRbTree &other) noexcept
	Swap contents with another tree.
virtual	~GenTdRbTree ()=default
size_t	size () const noexcept
	Get number of nodes in tree (O(1))
bool	is_empty () const noexcept
	Check if tree is empty.
Compare &	get_compare () noexcept
	Get reference to comparator.
const Compare &	get_compare () const noexcept
Node *	insert (Node *p) noexcept
	Insert a node into the tree.
Node *	insert_dup (Node *p) noexcept
	Insert a node, allowing duplicates.
Node *	search_or_insert (Node *p) noexcept
	Search for key or insert if not found.
Node *	search (const Key &key) const noexcept
	Search for a key in the tree.
Node *	remove (const Key &key) noexcept
	Remove and return node with given key.
Node *&	getRoot () noexcept
	Get reference to root pointer.
Node *	getRoot () const noexcept
	Get const root pointer
bool	verifyRedBlack () const noexcept
	Verify that tree satisfies all red-black properties.
bool	verify () const noexcept
	Alias for verify.

Private Member Functions
bool	less (const Key &a, const Key &b) const noexcept
	Returns true if a < b according to comparator.
bool	equals (const Key &a, const Key &b) const noexcept
	Returns true if a == b (neither a < b nor b < a)
void	restoreRedCondition (Node *p, Node *&fp, Node *ffp, Node *fffp) noexcept
	Restore red-black property after color flip creates two consecutive reds.
Node *	searchFlipColorsAndInsert (Node *q) noexcept
	Search for insertion point, flipping colors proactively to maintain balance.
Node *	searchFlipColorsAndInsertDup (Node *q) noexcept
	Search for insertion point allowing duplicates.
void	colorRootAsRed () noexcept
	Color root red if safe (both children black)
Node *	searchAndColorRed (const Key &key, Node *&fp) noexcept
	Search for key while coloring nodes red for deletion.
void	init () noexcept
	Initialize header nodes.

Static Private Member Functions
static Node *	getSibling (Node *p, Node *fp) noexcept
	Get sibling of node p whose parent is fp.
static void	flipColors (Node *p) noexcept
	Flip colors: black parent with two red children becomes red with two black children.
static Node *	gotoLeftAndColorRed (Node *fp, Node *&ffp) noexcept
	Descend to left child, ensuring current node is red for deletion.
static Node *	gotoRightAndColorRed (Node *fp, Node *&ffp) noexcept
	Descend to right child, ensuring current node is red for deletion.
static void	findSuccAndSwap (Node *p, Node *&fp) noexcept
	Find successor and swap with node p for deletion.
static void	findPredAndSwap (Node *p, Node *&fp) noexcept
	Find predecessor and swap with node p for deletion.
static void	removeAndRendLeafRed (Node *p, Node *fp) noexcept
	Remove node p and ensure it becomes a red leaf.
static bool	testBlackHeight (Node *p, int &max, int bh=0) noexcept
	Test black height property recursively.
static bool	testNode (Node *p) noexcept
	Test red-black properties for a single node.
static bool	verify (Node *p) noexcept
	Recursively verify red-black properties.

Private Attributes
Node	headNode
	Sentinel header node (parent of root)
Node	headParent
	Sentinel grandparent node.
Node *	head
	Pointer to header.
Node *	fHead
	Pointer to header's parent.
Node *&	root
	Reference to root (right child of head)
Compare	cmp
	Comparison functor.
size_t	num_nodes
	Number of nodes in tree.

Detailed Description

template<template< class > class NodeType, typename Key, class Compare = Aleph::less<Key>>
requires StrictWeakOrder<Compare, Key>
class Aleph::GenTdRbTree< NodeType, Key, Compare >

Top-down red-black binary search tree implementation.

This class implements the top-down (single-pass) red-black tree algorithm as described by Guibas and Sedgewick. Unlike the bottom-up approach that requires backtracking after insertion/deletion, this algorithm performs all necessary rotations and color changes while descending the tree.

Advantages over bottom-up:

• No stack needed for ancestor path (saves O(log n) space)
• Better cache locality (single pass through tree)
• Potentially faster due to reduced memory traffic

Disadvantages:

• More complex code
• May perform more color flips than strictly necessary

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)

Template Parameters

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

See also

Gen_Rb_Tree Bottom-up red-black tree implementation.

Avl_Tree Alternative balanced tree with stricter balance.

Definition at line 98 of file tpl_tdRbTree.H.

Member Typedef Documentation

compare_type

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

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

Definition at line 103 of file tpl_tdRbTree.H.

key_type

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

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

Definition at line 102 of file tpl_tdRbTree.H.

Node

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

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

Definition at line 101 of file tpl_tdRbTree.H.

Constructor & Destructor Documentation

GenTdRbTree() [1/4]

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

Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree ( )

inlinenoexcept

Default constructor.

Definition at line 624 of file tpl_tdRbTree.H.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::init().

GenTdRbTree() [2/4]

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

Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree ( const Compare &  __cmp )

inlineexplicitnoexcept

Constructor with comparator.

Definition at line 631 of file tpl_tdRbTree.H.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::init().

GenTdRbTree() [3/4]

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

Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree ( GenTdRbTree< NodeType, Key, Compare > &&  other )

inlinenoexcept

Move constructor.

Definition at line 638 of file tpl_tdRbTree.H.

References BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTree< NodeType, Key, Compare >::fHead, Aleph::GenTdRbTree< NodeType, Key, Compare >::head, RLINK, and Aleph::GenTdRbTree< NodeType, Key, Compare >::root.

GenTdRbTree() [4/4]

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

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

delete

Deleted copy constructor (use explicit copy if needed)

~GenTdRbTree()

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

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

virtualdefault

Member Function Documentation

colorRootAsRed()

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

void Aleph::GenTdRbTree< NodeType, Key, Compare >::colorRootAsRed ( )

inlineprivatenoexcept

Color root red if safe (both children black)

Definition at line 551 of file tpl_tdRbTree.H.

References Aleph::and, BLACK, COLOR, LLINK, RED, RLINK, and Aleph::GenTdRbTree< NodeType, Key, Compare >::root.

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::searchAndColorRed().

equals()

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

bool Aleph::GenTdRbTree< NodeType, Key, Compare >::equals ( const Key &  a, const Key &  b  ) const

inlineprivatenoexcept

Returns true if a == b (neither a < b nor b < a)

Definition at line 121 of file tpl_tdRbTree.H.

References Aleph::and, Aleph::GenTdRbTree< NodeType, Key, Compare >::cmp, and Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::remove(), Aleph::GenTdRbTree< NodeType, Key, Compare >::search(), Aleph::GenTdRbTree< NodeType, Key, Compare >::searchAndColorRed(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsert().

findPredAndSwap()

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

static void Aleph::GenTdRbTree< NodeType, Key, Compare >::findPredAndSwap ( Node *  p, Node *&  fp  )

inlinestaticprivatenoexcept

Find predecessor and swap with node p for deletion.

Definition at line 496 of file tpl_tdRbTree.H.

References COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoLeftAndColorRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoRightAndColorRed(), LLINK, pred, and RLINK.

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::removeAndRendLeafRed().

findSuccAndSwap()

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

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

inlinestaticprivatenoexcept

Find successor and swap with node p for deletion.

Definition at line 441 of file tpl_tdRbTree.H.

References COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoLeftAndColorRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoRightAndColorRed(), LLINK, and RLINK.

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::removeAndRendLeafRed().

flipColors()

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

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

inlinestaticprivatenoexcept

Flip colors: black parent with two red children becomes red with two black children.

Definition at line 180 of file tpl_tdRbTree.H.

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

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

get_compare() [1/2]

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

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

inlinenoexcept

Definition at line 695 of file tpl_tdRbTree.H.

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

get_compare() [2/2]

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

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

inlinenoexcept

Get reference to comparator.

Definition at line 694 of file tpl_tdRbTree.H.

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

getRoot() [1/2]

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

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

inlinenoexcept

Get const root pointer

Definition at line 809 of file tpl_tdRbTree.H.

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

getRoot() [2/2]

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

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

inlinenoexcept

Get reference to root pointer.

Definition at line 806 of file tpl_tdRbTree.H.

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

getSibling()

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

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

inlinestaticprivatenoexcept

Get sibling of node p whose parent is fp.

Definition at line 127 of file tpl_tdRbTree.H.

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

gotoLeftAndColorRed()

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

static Node * Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoLeftAndColorRed ( Node *  fp, Node *&  ffp  )

inlinestaticprivatenoexcept

Descend to left child, ensuring current node is red for deletion.

Definition at line 318 of file tpl_tdRbTree.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, RED, RLINK, Aleph::rotate_to_left(), and Aleph::rotate_to_right().

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::findPredAndSwap(), Aleph::GenTdRbTree< NodeType, Key, Compare >::findSuccAndSwap(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::searchAndColorRed().

gotoRightAndColorRed()

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

static Node * Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoRightAndColorRed ( Node *  fp, Node *&  ffp  )

inlinestaticprivatenoexcept

Descend to right child, ensuring current node is red for deletion.

Definition at line 380 of file tpl_tdRbTree.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, RED, RLINK, Aleph::rotate_to_left(), and Aleph::rotate_to_right().

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::findPredAndSwap(), Aleph::GenTdRbTree< NodeType, Key, Compare >::findSuccAndSwap(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::searchAndColorRed().

init()

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

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

inlineprivatenoexcept

Initialize header nodes.

Definition at line 614 of file tpl_tdRbTree.H.

References BLACK, COLOR, Aleph::GenTdRbTree< NodeType, Key, Compare >::fHead, Aleph::GenTdRbTree< NodeType, Key, Compare >::head, Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, and RLINK.

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree().

insert()

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

Node * Aleph::GenTdRbTree< 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 702 of file tpl_tdRbTree.H.

References Aleph::and, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, RED, RLINK, Aleph::GenTdRbTree< NodeType, Key, Compare >::root, and Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsert().

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

insert_dup()

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

Node * Aleph::GenTdRbTree< 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 723 of file tpl_tdRbTree.H.

References Aleph::and, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, RED, RLINK, Aleph::GenTdRbTree< NodeType, Key, Compare >::root, and Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsertDup().

Referenced by TEST(), and TEST().

is_empty()

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

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

inlinenoexcept

Check if tree is empty.

Definition at line 691 of file tpl_tdRbTree.H.

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

less()

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

bool Aleph::GenTdRbTree< NodeType, Key, Compare >::less ( const Key &  a, const Key &  b  ) const

inlineprivatenoexcept

Returns true if a < b according to comparator.

Definition at line 115 of file tpl_tdRbTree.H.

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

operator=() [1/2]

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

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

delete

Deleted copy assignment.

operator=() [2/2]

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

GenTdRbTree & Aleph::GenTdRbTree< NodeType, Key, Compare >::operator= ( GenTdRbTree< NodeType, Key, Compare > &&  other )

inlinenoexcept

Move assignment operator.

Definition at line 651 of file tpl_tdRbTree.H.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, and Aleph::GenTdRbTree< NodeType, Key, Compare >::root.

remove()

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

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

inlinenoexcept

Remove and return node with given key.

Parameters

key	Key to remove.

Returns

Pointer to removed node, or nullptr if not found.

Definition at line 788 of file tpl_tdRbTree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTree< NodeType, Key, Compare >::equals(), KEY, Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, Aleph::GenTdRbTree< NodeType, Key, Compare >::removeAndRendLeafRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::root, and Aleph::GenTdRbTree< NodeType, Key, Compare >::searchAndColorRed().

Referenced by TEST(), TEST(), TEST(), and TEST().

removeAndRendLeafRed()

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

static void Aleph::GenTdRbTree< NodeType, Key, Compare >::removeAndRendLeafRed ( Node *  p, Node *  fp  )

inlinestaticprivatenoexcept

Remove node p and ensure it becomes a red leaf.

Definition at line 593 of file tpl_tdRbTree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTree< NodeType, Key, Compare >::findPredAndSwap(), Aleph::GenTdRbTree< NodeType, Key, Compare >::findSuccAndSwap(), LLINK, and RLINK.

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

reset()

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

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

inlinenoexcept

Reset tree to empty state (does not free nodes)

Definition at line 671 of file tpl_tdRbTree.H.

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

restoreRedCondition()

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

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

inlineprivatenoexcept

Restore red-black property after color flip creates two consecutive reds.

Definition at line 134 of file tpl_tdRbTree.H.

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

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

search()

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

Node * Aleph::GenTdRbTree< 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 771 of file tpl_tdRbTree.H.

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

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::search_or_insert(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

search_or_insert()

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

Node * Aleph::GenTdRbTree< 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 744 of file tpl_tdRbTree.H.

References Aleph::and, COLOR, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, RED, RLINK, Aleph::GenTdRbTree< NodeType, Key, Compare >::root, Aleph::GenTdRbTree< NodeType, Key, Compare >::search(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsert().

Referenced by TEST(), and TEST().

searchAndColorRed()

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

Node * Aleph::GenTdRbTree< NodeType, Key, Compare >::searchAndColorRed ( const Key &  key, Node *&  fp  )

inlineprivatenoexcept

Search for key while coloring nodes red for deletion.

Definition at line 561 of file tpl_tdRbTree.H.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::colorRootAsRed(), Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTree< NodeType, Key, Compare >::equals(), Aleph::GenTdRbTree< NodeType, Key, Compare >::fHead, Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoLeftAndColorRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoRightAndColorRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::head, KEY, LLINK, RLINK, and Aleph::GenTdRbTree< NodeType, Key, Compare >::root.

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

searchFlipColorsAndInsert()

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

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

inlineprivatenoexcept

Search for insertion point, flipping colors proactively to maintain balance.

Definition at line 191 of file tpl_tdRbTree.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTree< NodeType, Key, Compare >::equals(), Aleph::GenTdRbTree< NodeType, Key, Compare >::fHead, Aleph::GenTdRbTree< NodeType, Key, Compare >::flipColors(), Aleph::GenTdRbTree< NodeType, Key, Compare >::head, KEY, LLINK, Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, RED, Aleph::GenTdRbTree< NodeType, Key, Compare >::restoreRedCondition(), RLINK, and Aleph::GenTdRbTree< NodeType, Key, Compare >::root.

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

searchFlipColorsAndInsertDup()

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

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

inlineprivatenoexcept

Search for insertion point allowing duplicates.

Definition at line 257 of file tpl_tdRbTree.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTree< NodeType, Key, Compare >::fHead, Aleph::GenTdRbTree< NodeType, Key, Compare >::flipColors(), Aleph::GenTdRbTree< NodeType, Key, Compare >::head, KEY, LLINK, Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, RED, Aleph::GenTdRbTree< NodeType, Key, Compare >::restoreRedCondition(), RLINK, and Aleph::GenTdRbTree< NodeType, Key, Compare >::root.

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

size()

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

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

inlinenoexcept

Get number of nodes in tree (O(1))

Definition at line 688 of file tpl_tdRbTree.H.

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

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

swap()

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

void Aleph::GenTdRbTree< NodeType, Key, Compare >::swap ( GenTdRbTree< NodeType, Key, Compare > &  other )

inlinenoexcept

Swap contents with another tree.

Definition at line 678 of file tpl_tdRbTree.H.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, and Aleph::GenTdRbTree< NodeType, Key, Compare >::root.

testBlackHeight()

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

static bool Aleph::GenTdRbTree< NodeType, Key, Compare >::testBlackHeight ( Node *  p, int &  max, int  bh = 0  )

inlinestaticprivatenoexcept

Test black height property recursively.

Definition at line 813 of file tpl_tdRbTree.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, max(), RLINK, and Aleph::GenTdRbTree< NodeType, Key, Compare >::testBlackHeight().

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::testBlackHeight(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::testNode().

testNode()

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

static bool Aleph::GenTdRbTree< NodeType, Key, Compare >::testNode ( Node *  p )

inlinestaticprivatenoexcept

Test red-black properties for a single node.

Definition at line 833 of file tpl_tdRbTree.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, max(), RED, RLINK, and Aleph::GenTdRbTree< NodeType, Key, Compare >::testBlackHeight().

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::verify().

verify() [1/2]

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

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

inlinenoexcept

Alias for verify.

Definition at line 872 of file tpl_tdRbTree.H.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack().

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::verify(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack().

verify() [2/2]

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

static bool Aleph::GenTdRbTree< NodeType, Key, Compare >::verify ( Node *  p )

inlinestaticprivatenoexcept

Recursively verify red-black properties.

Definition at line 850 of file tpl_tdRbTree.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), LLINK, RLINK, Aleph::GenTdRbTree< NodeType, Key, Compare >::testNode(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verify().

verifyRedBlack()

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

bool Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack ( ) const

inlinenoexcept

Verify that tree satisfies all red-black properties.

Returns

true if tree is valid, false otherwise.

Definition at line 864 of file tpl_tdRbTree.H.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::root, and Aleph::GenTdRbTree< NodeType, Key, Compare >::verify().

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verify().

Member Data Documentation

cmp

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

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

private

Comparison functor.

Definition at line 111 of file tpl_tdRbTree.H.

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::equals(), Aleph::GenTdRbTree< NodeType, Key, Compare >::get_compare(), Aleph::GenTdRbTree< NodeType, Key, Compare >::get_compare(), Aleph::GenTdRbTree< NodeType, Key, Compare >::less(), Aleph::GenTdRbTree< NodeType, Key, Compare >::operator=(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::swap().

fHead

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

Node* Aleph::GenTdRbTree< NodeType, Key, Compare >::fHead

private

Pointer to header's parent.

Definition at line 109 of file tpl_tdRbTree.H.

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree(), Aleph::GenTdRbTree< NodeType, Key, Compare >::init(), Aleph::GenTdRbTree< NodeType, Key, Compare >::searchAndColorRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsert(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsertDup().

head

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

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

private

Pointer to header.

Definition at line 108 of file tpl_tdRbTree.H.

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree(), Aleph::GenTdRbTree< NodeType, Key, Compare >::init(), Aleph::GenTdRbTree< NodeType, Key, Compare >::searchAndColorRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsert(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsertDup().

headNode

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

Node Aleph::GenTdRbTree< NodeType, Key, Compare >::headNode

private

Sentinel header node (parent of root)

Definition at line 106 of file tpl_tdRbTree.H.

headParent

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

Node Aleph::GenTdRbTree< NodeType, Key, Compare >::headParent

private

Sentinel grandparent node.

Definition at line 107 of file tpl_tdRbTree.H.

num_nodes

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

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

private

Number of nodes in tree.

Definition at line 112 of file tpl_tdRbTree.H.

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::init(), Aleph::GenTdRbTree< NodeType, Key, Compare >::insert(), Aleph::GenTdRbTree< NodeType, Key, Compare >::insert_dup(), Aleph::GenTdRbTree< NodeType, Key, Compare >::operator=(), Aleph::GenTdRbTree< NodeType, Key, Compare >::remove(), Aleph::GenTdRbTree< NodeType, Key, Compare >::reset(), Aleph::GenTdRbTree< NodeType, Key, Compare >::search_or_insert(), Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsert(), Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsertDup(), Aleph::GenTdRbTree< NodeType, Key, Compare >::size(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::swap().

root

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

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

private

Reference to root (right child of head)

Definition at line 110 of file tpl_tdRbTree.H.

Referenced by Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree(), Aleph::GenTdRbTree< NodeType, Key, Compare >::colorRootAsRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::getRoot(), Aleph::GenTdRbTree< NodeType, Key, Compare >::getRoot(), Aleph::GenTdRbTree< NodeType, Key, Compare >::insert(), Aleph::GenTdRbTree< NodeType, Key, Compare >::insert_dup(), Aleph::GenTdRbTree< NodeType, Key, Compare >::is_empty(), Aleph::GenTdRbTree< NodeType, Key, Compare >::operator=(), Aleph::GenTdRbTree< NodeType, Key, Compare >::remove(), Aleph::GenTdRbTree< NodeType, Key, Compare >::reset(), Aleph::GenTdRbTree< NodeType, Key, Compare >::restoreRedCondition(), Aleph::GenTdRbTree< NodeType, Key, Compare >::search(), Aleph::GenTdRbTree< NodeType, Key, Compare >::search_or_insert(), Aleph::GenTdRbTree< NodeType, Key, Compare >::searchAndColorRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsert(), Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsertDup(), Aleph::GenTdRbTree< NodeType, Key, Compare >::swap(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack().

---

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

• tpl_tdRbTree.H