Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
Aleph::GenTdRbTree< NodeType, Key, Compare > Class Template Reference
Trees

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

#include <tpl_tdRbTree.H>

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

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 = std::less<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
NodeTypeNode template (typically RbNode or RbNodeVtl).
KeyThe type of keys stored in the tree.
CompareComparison functor for ordering keys (default: std::less<Key>).
See also
Gen_Rb_Tree Bottom-up red-black tree implementation.
Avl_Tree Alternative balanced tree with stricter balance.

Definition at line 96 of file tpl_tdRbTree.H.

Member Typedef Documentation

◆ compare_type

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
using Aleph::GenTdRbTree< NodeType, Key, Compare >::compare_type = Compare

Definition at line 101 of file tpl_tdRbTree.H.

◆ key_type

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
using Aleph::GenTdRbTree< NodeType, Key, Compare >::key_type = Key

Definition at line 100 of file tpl_tdRbTree.H.

◆ Node

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
using Aleph::GenTdRbTree< NodeType, Key, Compare >::Node = NodeType<Key>

Definition at line 99 of file tpl_tdRbTree.H.

Constructor & Destructor Documentation

◆ GenTdRbTree() [1/4]

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree ( )
inlinenoexcept

Default constructor.

Definition at line 622 of file tpl_tdRbTree.H.

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

◆ GenTdRbTree() [2/4]

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree ( const Compare &  __cmp)
inlineexplicitnoexcept

Constructor with comparator.

Definition at line 629 of file tpl_tdRbTree.H.

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

◆ GenTdRbTree() [3/4]

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
Aleph::GenTdRbTree< NodeType, Key, Compare >::GenTdRbTree ( GenTdRbTree< NodeType, Key, Compare > &&  other)
inlinenoexcept

Move constructor.

Definition at line 636 of file tpl_tdRbTree.H.

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

◆ GenTdRbTree() [4/4]

template<template< class > class NodeType, typename Key , class Compare = std::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 = std::less<Key>>
virtual Aleph::GenTdRbTree< NodeType, Key, Compare >::~GenTdRbTree ( )
virtualdefault

Member Function Documentation

◆ colorRootAsRed()

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
void Aleph::GenTdRbTree< NodeType, Key, Compare >::colorRootAsRed ( )
inlineprivatenoexcept

Color root red if safe (both children black)

Definition at line 549 of file tpl_tdRbTree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), RED, Aleph::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 = std::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 119 of file tpl_tdRbTree.H.

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

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 = std::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 494 of file tpl_tdRbTree.H.

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

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

◆ findSuccAndSwap()

template<template< class > class NodeType, typename Key , class Compare = std::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 439 of file tpl_tdRbTree.H.

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

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

◆ flipColors()

template<template< class > class NodeType, typename Key , class Compare = std::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 178 of file tpl_tdRbTree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), RED, and Aleph::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 = std::less<Key>>
const Compare & Aleph::GenTdRbTree< NodeType, Key, Compare >::get_compare ( ) const
inlinenoexcept

Definition at line 693 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 = std::less<Key>>
Compare & Aleph::GenTdRbTree< NodeType, Key, Compare >::get_compare ( )
inlinenoexcept

Get reference to comparator.

Definition at line 692 of file tpl_tdRbTree.H.

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

◆ getRoot() [1/2]

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
Node * Aleph::GenTdRbTree< NodeType, Key, Compare >::getRoot ( ) const
inlinenoexcept

Get const root pointer

Definition at line 807 of file tpl_tdRbTree.H.

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

◆ getRoot() [2/2]

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
Node *& Aleph::GenTdRbTree< NodeType, Key, Compare >::getRoot ( )
inlinenoexcept

Get reference to root pointer.

Definition at line 804 of file tpl_tdRbTree.H.

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

◆ getSibling()

template<template< class > class NodeType, typename Key , class Compare = std::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 125 of file tpl_tdRbTree.H.

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

◆ gotoLeftAndColorRed()

template<template< class > class NodeType, typename Key , class Compare = std::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 316 of file tpl_tdRbTree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), RED, Aleph::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 = std::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 378 of file tpl_tdRbTree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), RED, Aleph::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 = std::less<Key>>
void Aleph::GenTdRbTree< NodeType, Key, Compare >::init ( )
inlineprivatenoexcept

Initialize header nodes.

Definition at line 612 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 Aleph::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 = std::less<Key>>
Node * Aleph::GenTdRbTree< NodeType, Key, Compare >::insert ( Node *  p)
inlinenoexcept

Insert a node into the tree.

Parameters
pNode to insert (must be red with null children).
Returns
Pointer to inserted node, or nullptr if key already exists.

Definition at line 700 of file tpl_tdRbTree.H.

References COLOR, Aleph::LLINK(), Aleph::maps(), Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, RED, Aleph::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 = std::less<Key>>
Node * Aleph::GenTdRbTree< NodeType, Key, Compare >::insert_dup ( Node *  p)
inlinenoexcept

Insert a node, allowing duplicates.

Parameters
pNode to insert.
Returns
Pointer to inserted node (always succeeds).

Definition at line 721 of file tpl_tdRbTree.H.

References COLOR, Aleph::LLINK(), Aleph::maps(), Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, RED, Aleph::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 = std::less<Key>>
bool Aleph::GenTdRbTree< NodeType, Key, Compare >::is_empty ( ) const
inlinenoexcept

Check if tree is empty.

Definition at line 689 of file tpl_tdRbTree.H.

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

◆ less()

template<template< class > class NodeType, typename Key , class Compare = std::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 113 of file tpl_tdRbTree.H.

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

◆ operator=() [1/2]

template<template< class > class NodeType, typename Key , class Compare = std::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 = std::less<Key>>
GenTdRbTree & Aleph::GenTdRbTree< NodeType, Key, Compare >::operator= ( GenTdRbTree< NodeType, Key, Compare > &&  other)
inlinenoexcept

Move assignment operator.

Definition at line 649 of file tpl_tdRbTree.H.

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

◆ remove()

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
Node * Aleph::GenTdRbTree< NodeType, Key, Compare >::remove ( const Key &  key)
inlinenoexcept

Remove and return node with given key.

Parameters
keyKey to remove.
Returns
Pointer to removed node, or nullptr if not found.

Definition at line 786 of file tpl_tdRbTree.H.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::equals(), KEY, Aleph::maps(), 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 = std::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 591 of file tpl_tdRbTree.H.

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

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

◆ reset()

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
void Aleph::GenTdRbTree< NodeType, Key, Compare >::reset ( )
inlinenoexcept

Reset tree to empty state (does not free nodes)

Definition at line 669 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 = std::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 132 of file tpl_tdRbTree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), RED, Aleph::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 = std::less<Key>>
Node * Aleph::GenTdRbTree< NodeType, Key, Compare >::search ( const Key &  key) const
inlinenoexcept

Search for a key in the tree.

Parameters
keyKey to search for.
Returns
Pointer to node containing key, or nullptr if not found.

Definition at line 769 of file tpl_tdRbTree.H.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::equals(), KEY, Aleph::LLINK(), Aleph::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 = std::less<Key>>
Node * Aleph::GenTdRbTree< NodeType, Key, Compare >::search_or_insert ( Node *  p)
inlinenoexcept

Search for key or insert if not found.

Parameters
pNode to search or insert.
Returns
Pointer to p if inserted, or pointer to existing node with same key.

Definition at line 742 of file tpl_tdRbTree.H.

References COLOR, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, RED, Aleph::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 = std::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 559 of file tpl_tdRbTree.H.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::colorRootAsRed(), 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, Aleph::LLINK(), Aleph::maps(), Aleph::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 = std::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 189 of file tpl_tdRbTree.H.

References BLACK, COLOR, 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, Aleph::LLINK(), Aleph::maps(), Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, RED, Aleph::GenTdRbTree< NodeType, Key, Compare >::restoreRedCondition(), Aleph::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 = std::less<Key>>
Node * Aleph::GenTdRbTree< NodeType, Key, Compare >::searchFlipColorsAndInsertDup ( Node *  q)
inlineprivatenoexcept

Search for insertion point allowing duplicates.

Definition at line 255 of file tpl_tdRbTree.H.

References BLACK, COLOR, Aleph::GenTdRbTree< NodeType, Key, Compare >::fHead, Aleph::GenTdRbTree< NodeType, Key, Compare >::flipColors(), Aleph::GenTdRbTree< NodeType, Key, Compare >::head, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes, RED, Aleph::GenTdRbTree< NodeType, Key, Compare >::restoreRedCondition(), Aleph::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 = std::less<Key>>
size_t Aleph::GenTdRbTree< NodeType, Key, Compare >::size ( ) const
inlinenoexcept

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

Definition at line 686 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 = std::less<Key>>
void Aleph::GenTdRbTree< NodeType, Key, Compare >::swap ( GenTdRbTree< NodeType, Key, Compare > &  other)
inlinenoexcept

Swap contents with another tree.

Definition at line 676 of file tpl_tdRbTree.H.

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

◆ testBlackHeight()

template<template< class > class NodeType, typename Key , class Compare = std::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 811 of file tpl_tdRbTree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), max(), Aleph::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 = std::less<Key>>
static bool Aleph::GenTdRbTree< NodeType, Key, Compare >::testNode ( Node *  p)
inlinestaticprivatenoexcept

Test red-black properties for a single node.

Definition at line 831 of file tpl_tdRbTree.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), max(), RED, Aleph::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 = std::less<Key>>
bool Aleph::GenTdRbTree< NodeType, Key, Compare >::verify ( ) const
inlinenoexcept

Alias for verify.

Definition at line 870 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 = std::less<Key>>
static bool Aleph::GenTdRbTree< NodeType, Key, Compare >::verify ( Node *  p)
inlinestaticprivatenoexcept

Recursively verify red-black properties.

Definition at line 848 of file tpl_tdRbTree.H.

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

◆ verifyRedBlack()

template<template< class > class NodeType, typename Key , class Compare = std::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 862 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 = std::less<Key>>
Compare Aleph::GenTdRbTree< NodeType, Key, Compare >::cmp
private

Comparison functor.

Definition at line 109 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 = std::less<Key>>
Node* Aleph::GenTdRbTree< NodeType, Key, Compare >::fHead
private

Pointer to header's parent.

Definition at line 107 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 = std::less<Key>>
Node* Aleph::GenTdRbTree< NodeType, Key, Compare >::head
private

Pointer to header.

Definition at line 106 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 = std::less<Key>>
Node Aleph::GenTdRbTree< NodeType, Key, Compare >::headNode
private

Sentinel header node (parent of root)

Definition at line 104 of file tpl_tdRbTree.H.

◆ headParent

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
Node Aleph::GenTdRbTree< NodeType, Key, Compare >::headParent
private

Sentinel grandparent node.

Definition at line 105 of file tpl_tdRbTree.H.

◆ num_nodes

template<template< class > class NodeType, typename Key , class Compare = std::less<Key>>
size_t Aleph::GenTdRbTree< NodeType, Key, Compare >::num_nodes
private

Number of nodes in tree.

Definition at line 110 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 = std::less<Key>>
Node*& Aleph::GenTdRbTree< NodeType, Key, Compare >::root
private

Reference to root (right child of head)

Definition at line 108 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: