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

Randomized binary search tree with rank support. More...

#include <tpl_rand_tree.H>

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

Classes
struct	Iterator
	Iterator on nodes of the tree. More...

Public Types
using	Node = NodeType< Key >

Public Member Functions
	Gen_Rand_Tree (const Gen_Rand_Tree &)=delete
Gen_Rand_Tree &	operator= (const Gen_Rand_Tree &)=delete
Compare &	key_comp () noexcept
	return the comparison criteria
const Compare &	key_comp () const noexcept
Compare &	get_compare () noexcept
const Compare &	get_compare () const noexcept
gsl_rng *	gsl_rng_object () noexcept
	Get a pointer to gsl random number generator.
void	set_seed (const unsigned long seed) noexcept
	Set the random number generator seed.
	Gen_Rand_Tree (const unsigned int seed, const Compare &__cmp=Compare())
	Initialize a random tree with random seed and comparison criteria __cmp
	Gen_Rand_Tree (const Compare &cmp=Compare()) noexcept
	Initialize a random tree with random seed from system time and comparison criteria cmp
void	swap (Gen_Rand_Tree &tree) noexcept
	Swap in constant time all the nodes of this with tree
	Gen_Rand_Tree (Gen_Rand_Tree &&other) noexcept
	Move constructor - transfers ownership of tree and RNG.
Gen_Rand_Tree &	operator= (Gen_Rand_Tree &&other) noexcept
	Move assignment - transfers ownership of tree and RNG.
virtual	~Gen_Rand_Tree () noexcept
Node *	insert (Node *p) noexcept
	Insert a node in the tree.
Node *	insert_dup (Node *p) noexcept
	Insert a node in the tree.
Node *	remove (const Key &key) noexcept
	Remove a key from the tree.
Node *	search (const Key &key) const noexcept
	Search a key.
Node *	search_or_insert (Node *p) noexcept
	Search or insert a key.
bool	verify () const
	Return true if this is a consistent randomized tree.
Node *&	getRoot () noexcept
	Return the tree's root.
Node *	select (const size_t i) const
	Return the i-th node in inorder sense.
size_t	size () const noexcept
	Return the number of nodes that have the tree.
bool	is_empty () const noexcept
	Return true if the tree is empty.
std::pair< long, Node * >	position (const Key &key) const noexcept
	Compute the inorder position of a key.
std::pair< long, Node * >	find_position (const Key &key) const noexcept
	Find the inorder position of a key in the tree.
Node *	remove_pos (const size_t i)
	Remove the key at inorder position i
bool	split_key (const Key &key, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2) noexcept
	Split the tree according to a key.
void	split_key_dup (const Key &key, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2) noexcept
	Split the tree according to a key that could be in the tree.
void	split_pos (size_t pos, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2) noexcept
	Split a extended binary tree according to a position.
void	join (Gen_Rand_Tree &t, Gen_Rand_Tree &dup) noexcept
	Join this with t filtering the duplicated keys.
void	join_dup (Gen_Rand_Tree &t) noexcept
	Join this with t independently of the presence of duplicated keys.
void	join_exclusive (Gen_Rand_Tree &t) noexcept
	Join exclusive of this with t

Private Member Functions
Node *	random_insert (Node *root, Node *p) noexcept
Node *	random_insert_dup (Node *root, Node *p) noexcept
Node *	random_search_or_insert (Node *&root, Node *p) noexcept
void	init (const unsigned long seed)
Node *	random_join_exclusive (Node *tl, Node *tr) noexcept
Node *	random_remove (Node *&root, const Key &key) noexcept
Node *	remove_pos (Node *&root, const size_t pos) noexcept
Node *	random_join (Node *t1, Node *t2, Node *&dup)
Node *	random_join (Node *t1, Node *t2)

Private Attributes
Node *	tree_root
	The type of node.
gsl_rng *	r
Compare	cmp

Detailed Description

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

Randomized binary search tree with rank support.

This class implements a randomized binary search tree where random decisions during insertion and deletion ensure that the tree has the same expected properties as if it were built from a random permutation of keys, regardless of actual insertion order.

Key Insight:

At each insertion, a random "raffle" determines whether the new node becomes the root (and existing nodes are split around it) or is inserted recursively into a subtree. This ensures that every node has an equal probability of being at any position, producing expected O(log n) height.

Ranked Operations:

Unlike basic BSTs, randomized trees maintain subtree sizes (COUNT), enabling O(log n) access by rank (inorder position):

• select(i): Get the i-th smallest element
• position(key): Get the rank of a key
• remove_pos(i): Remove the i-th element

This allows treating the tree like a sorted dynamic array with O(log n) indexed access, insertion, and deletion.

Split and Join:

Randomized trees excel at split/join operations, which take O(log(max(n,m))) time. This is dramatically better than other balanced trees that require O(n log m) for joining two trees of sizes n and m.

Template Parameters

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

Complexity:

• Search: O(log n) expected
• Insert: O(log n) expected
• Delete: O(log n) expected
• Select (by rank): O(log n) expected
• Position (get rank): O(log n) expected
• Split: O(log n) expected
• Join: O(log(max(n,m))) expected - much better than other trees
• Space: O(n) + O(1) per node for COUNT

Random Number Generator:

Uses GSL (GNU Scientific Library) Mersenne Twister (mt19937) by default. Seed can be set via set_seed() for reproducible behavior.

Example:

Rand_Tree<int> tree;
 
// Insert nodes
tree.insert(new Rand_Tree<int>::Node(42));
tree.insert(new Rand_Tree<int>::Node(17));
tree.insert(new Rand_Tree<int>::Node(99));
tree.insert(new Rand_Tree<int>::Node(8));
 
// Ranked access (treat as sorted array)
auto smallest = tree.select(0);     // Get 0th element (8)
auto median = tree.select(tree.size() / 2);  // Get median
 
// Find position/rank of a key
size_t pos = tree.position(42);  // Returns 2 (0-indexed)
 
// Remove by position
auto removed = tree.remove_pos(1);  // Remove 2nd smallest
delete removed;
 
// Efficient split at key
Rand_Tree<int> left, right;
tree.split_key(50, left, right);  // All <= 50 go to left, > 50 to right
 
// Efficient join (O(log(max(n,m))))
tree.join(left, right);

Note

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

All operations maintain COUNT values for ranked operations.

Best choice when frequent split/join operations are needed.

See also

Rand_Tree Convenient typedef for Rand_Tree<Key, Compare>.

Treap Alternative randomized tree (often faster by constant factor).

TreapRk Treap with rank support.

DynSetRandTree High-level wrapper with automatic memory management.

Definition at line 151 of file tpl_rand_tree.H.

Member Typedef Documentation

Node

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

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

Definition at line 154 of file tpl_rand_tree.H.

Constructor & Destructor Documentation

Gen_Rand_Tree() [1/4]

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

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

delete

Gen_Rand_Tree() [2/4]

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

Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::Gen_Rand_Tree ( const unsigned int  seed, const Compare &  __cmp = Compare()  )

inline

Initialize a random tree with random seed and comparison criteria __cmp

Definition at line 307 of file tpl_rand_tree.H.

References Aleph::init.

Gen_Rand_Tree() [3/4]

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

Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::Gen_Rand_Tree ( const Compare &  cmp = Compare() )

inlinenoexcept

Initialize a random tree with random seed from system time and comparison criteria cmp

Definition at line 315 of file tpl_rand_tree.H.

Gen_Rand_Tree() [4/4]

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

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

inlinenoexcept

Move constructor - transfers ownership of tree and RNG.

Definition at line 329 of file tpl_rand_tree.H.

References Aleph::maps().

~Gen_Rand_Tree()

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

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

inlinevirtualnoexcept

Definition at line 358 of file tpl_rand_tree.H.

References Aleph::maps(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r.

Member Function Documentation

find_position()

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

std::pair< long, Node * > Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::find_position ( const Key &  key ) const

inlinenoexcept

Find the inorder position of a key in the tree.

find_position(key) determines the inorder position that has or had key in the tree. Themethod return a tuple with a position and a node pointer.

If key is found then its inorder position is returned along with a pointer to the node containing it.

Otherwise, the tuple returns the position that would have key if this was in the tree and the parent node that the key should be. At this regard, there are three cases:

1. if key is lesser than the minimum key of tree, then first is -1 and the node is one with the smallest key.
2. If key is greater than the maximum key in the tree, then first is the number of keys and the node is one with the maximum key in the tree.
3. For any other case, first is the inorder position that would have key if this was in the tree and second is the node whose key is immediately greater than key.

Parameters

[in]

key

to be searched

Returns

a pair with the inorder position and related node

Definition at line 572 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::cmp, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::find_position(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r, and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::find_position(), TEST(), TEST(), TEST(), and TEST().

get_compare() [1/2]

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

Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::get_compare ( ) 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 294 of file tpl_rand_tree.H.

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

get_compare() [2/2]

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

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

inlinenoexcept

Definition at line 291 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::key_comp().

Referenced by TEST().

getRoot()

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

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

inlinenoexcept

Return the tree's root.

Definition at line 508 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

Referenced by destroy_tree(), RankTreeTest< Tree >::TearDown(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and write_rand().

gsl_rng_object()

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

gsl_rng * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::gsl_rng_object ( )

inlinenoexcept

Get a pointer to gsl random number generator.

Definition at line 297 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r.

Referenced by TEST().

init()

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

void Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::init ( const unsigned long  seed )

inlineprivate

Definition at line 274 of file tpl_rand_tree.H.

References ah_bad_alloc_if, Aleph::maps(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r.

insert()

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

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

inlinenoexcept

Insert a node in the tree.

Parameters

[in]

p

pointer to the node to insert

Returns

if p->get_key() is not in the tree, then the pointer p is returned (it was inserted); otherwise, nullptr is returned

Definition at line 372 of file tpl_rand_tree.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert(), Aleph::RLINK(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

Referenced by RankTreeTest< Tree >::insert_all(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and write_rand().

insert_dup()

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

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

inlinenoexcept

Insert a node in the tree.

This method does not fail. It always inserts.

Parameters

[in]

p

pointer to the node to insert

Returns

the p pointer

Definition at line 392 of file tpl_rand_tree.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert_dup(), Aleph::RLINK(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

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

is_empty()

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

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

inlinenoexcept

Return true if the tree is empty.

Definition at line 526 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

Referenced by destroy_tree(), RankTreeTest< Tree >::TearDown(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

join()

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

void Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::join ( Gen_Rand_Tree< NodeType, Key, Compare > &  t, Gen_Rand_Tree< NodeType, Key, Compare > &  dup  )

inlinenoexcept

Join this with t filtering the duplicated keys.

join(t, dup) produces a random tree result of join of this and t. The resulting tree is stored in this.

Nodes containing duplicated keys are inserted in the randomized tree dup. The nodes could belong to any of two trees

Parameters

[in]	t	randomized tree to join with this
[out]	dup	randomized tree where nodes containing duplicated keys are inserted

Definition at line 758 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

join_dup()

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

void Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::join_dup ( Gen_Rand_Tree< NodeType, Key, Compare > &  t )

inlinenoexcept

Join this with t independently of the presence of duplicated keys.

join(t) produces a random tree result of join of this and t. The resulting tree is stored in this.

Parameters

[in]

t

randomized tree to join with this keys are inserted

Definition at line 772 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

join_exclusive()

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

void Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::join_exclusive ( Gen_Rand_Tree< NodeType, Key, Compare > &  t )

inlinenoexcept

Join exclusive of this with t

Exclusive means that all the keys of this are lesser than all the keys of t. This knowledge allows a more efficient way for joining that when the keys ranks are overlapped. However, use very carefully because the algorithm does not perform any check and the result would be incorrect.

Parameters

[in]

t

randomized tree to exclusively join with this keys are inserted

Definition at line 789 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join_exclusive(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

key_comp() [1/2]

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

Aleph::Gen_Rand_Tree< NodeType, 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 288 of file tpl_rand_tree.H.

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

key_comp() [2/2]

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

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

inlinenoexcept

return the comparison criteria

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

Definition at line 285 of file tpl_rand_tree.H.

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

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::get_compare(), TEST(), and TEST().

operator=() [1/2]

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

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

delete

operator=() [2/2]

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

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

inlinenoexcept

Move assignment - transfers ownership of tree and RNG.

Definition at line 337 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::cmp, Aleph::destroyRec(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r, and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

random_insert()

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

Node * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert ( Node *  root, Node *  p  )

inlineprivatenoexcept

Definition at line 161 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::cmp, Aleph::COUNT(), Aleph::BinTreeXt_Operation< Node, Cmp >::insert_root(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert(), Aleph::RLINK(), and root().

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert().

random_insert_dup()

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

Node * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert_dup ( Node *  root, Node *  p  )

inlineprivatenoexcept

Definition at line 201 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::cmp, Aleph::COUNT(), Aleph::BinTreeXt_Operation< Node, Cmp >::insert_dup_root(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert_dup(), Aleph::RLINK(), and root().

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert_dup(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join().

random_join() [1/2]

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

Node * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join ( Node *  t1, Node *  t2  )

inlineprivate

Definition at line 712 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::cmp, Aleph::COUNT(), Aleph::insert_dup_root_xt(), l, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::HTList::reset(), and Aleph::RLINK().

random_join() [2/2]

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

Node * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join ( Node *  t1, Node *  t2, Node *&  dup  )

inlineprivate

Definition at line 661 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::cmp, Aleph::COUNT(), Aleph::insert_root_xt(), KEY, l, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_remove(), Aleph::HTList::reset(), and Aleph::RLINK().

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::join_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join().

random_join_exclusive()

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

Node * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join_exclusive ( Node *  tl, Node *  tr  )

inlineprivatenoexcept

Definition at line 402 of file tpl_rand_tree.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join_exclusive(), and Aleph::RLINK().

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join_exclusive(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_remove(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove_pos().

random_remove()

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

Node * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_remove ( Node *&  root, const Key &  key  )

inlineprivatenoexcept

Definition at line 423 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::cmp, Aleph::COUNT(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join_exclusive(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_remove(), Aleph::HTList::reset(), Aleph::RLINK(), and root().

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_remove(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove().

random_search_or_insert()

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

Node * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_search_or_insert ( Node *&  root, Node *  p  )

inlineprivatenoexcept

Definition at line 226 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::cmp, Aleph::COUNT(), Aleph::insert_root(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_search_or_insert(), Aleph::RLINK(), and root().

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_search_or_insert(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search_or_insert().

remove()

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

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

inlinenoexcept

Remove a key from the tree.

Parameters

[in]

key

to remove

Returns

a valid pointer to the removed node if key was found in the tree, nullptr otherwise

Definition at line 462 of file tpl_rand_tree.H.

References Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_remove(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

Referenced by destroy_tree(), RankTreeTest< Tree >::TearDown(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

remove_pos() [1/2]

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

Node * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove_pos ( const size_t  i )

inline

Remove the key at inorder position i

Parameters

[in]

i

inorder position to be removed

Returns

a valid pointer to the removed node

Exceptions

out_of_range

if i is greater or equal than the number of nodes of tree

Definition at line 607 of file tpl_rand_tree.H.

References ah_out_of_range_error_if, Aleph::COUNT(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove_pos(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

remove_pos() [2/2]

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

Node * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove_pos ( Node *&  root, const size_t  pos  )

inlineprivatenoexcept

Definition at line 583 of file tpl_rand_tree.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join_exclusive(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove_pos(), Aleph::RLINK(), and root().

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove_pos(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove_pos(), TEST(), TEST(), and TEST().

search()

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

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

inlinenoexcept

Search a key.

Parameters

[in]

key

to be searched

Returns

a pointer to the containing key if this was found; otherwise nullptr

Definition at line 475 of file tpl_rand_tree.H.

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

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test(), TEST_F(), TEST_F(), TEST_F(), and write_rand().

search_or_insert()

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

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

inlinenoexcept

Search or insert a key.

search_or_insert(p) searches in the tree the key KEY(p). If this key is found, then a pointer to the node containing it is returned. Otherwise, p is inserted.

Parameters

[in]

p

node containing a key to be searched and eventually inserted

Returns

if the key contained in p is found, then a pointer to the containing key in the tree is returned. Otherwise, p is inserted and returned

Definition at line 493 of file tpl_rand_tree.H.

References Aleph::COUNT(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_search_or_insert(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

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

select()

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

Node * Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::select ( const size_t  i ) const

inline

Return the i-th node in inorder sense.

Parameters

[in]

i

inorder position to be located

Returns

a valid pointer to the i-th node inorder sense

Exceptions

out_of_range

if i is greater or equal that the number of nodes

Definition at line 517 of file tpl_rand_tree.H.

References Aleph::select(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

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

set_seed()

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

void Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::set_seed ( const unsigned long  seed )

inlinenoexcept

Set the random number generator seed.

Definition at line 300 of file tpl_rand_tree.H.

References Aleph::maps(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r.

size()

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

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

inlinenoexcept

Return the number of nodes that have the tree.

Definition at line 523 of file tpl_rand_tree.H.

References Aleph::COUNT(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

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

split_key()

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

bool Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::split_key ( const Key &  key, Gen_Rand_Tree< NodeType, Key, Compare > &  t1, Gen_Rand_Tree< NodeType, Key, Compare > &  t2  )

inlinenoexcept

Split the tree according to a key.

Parameters

[in]	key	for splitting
[out]	t1	tree with keys lesser than key
[out]	t2	tree with keys greater than key

Returns

true if tree was split; that is if key is not in the tree. Otherwise, if key is in the tree, false is returned

Definition at line 622 of file tpl_rand_tree.H.

References Aleph::maps(), Aleph::split_key_rec_xt(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

Referenced by TEST(), and TEST().

split_key_dup()

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

void Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::split_key_dup ( const Key &  key, Gen_Rand_Tree< NodeType, Key, Compare > &  t1, Gen_Rand_Tree< NodeType, Key, Compare > &  t2  )

inlinenoexcept

Split the tree according to a key that could be in the tree.

split_dup(key, t1, t2) splits the tree according to key in two trees t1 which contains the key lesser than key and t2 which contains the keys greater or equal than key.

Parameters

[in]	key	for splitting
[out]	t1	resulting tree with the keys lesser than key
[out]	t2	resulting tree with the keys greater or equal than key

Definition at line 638 of file tpl_rand_tree.H.

References Aleph::maps(), Aleph::split_key_dup_rec_xt(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

Referenced by TEST().

split_pos()

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

void Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::split_pos ( size_t  pos, Gen_Rand_Tree< NodeType, Key, Compare > &  t1, Gen_Rand_Tree< NodeType, Key, Compare > &  t2  )

inlinenoexcept

Split a extended binary tree according to a position.

split_pos(pos, ts, tg) splits the tree two trees t1 and t2 according to a position pos. t1 contains the keys from 0 to pos - 1 inorder sense and tg the keys from pos to n -

1. After completion this becames empty.

Parameters

[in]	pos	position for splitting
[out]	t1	tree where the rank of keys \([0, i)\) will be put
[out]	t2	tree where the rank of keys \([i, n]\) will be put

Definition at line 655 of file tpl_rand_tree.H.

References Aleph::maps(), Aleph::split_pos_rec(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

Referenced by TEST().

swap()

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

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

inlinenoexcept

Swap in constant time all the nodes of this with tree

Definition at line 321 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::cmp, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r, and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

verify()

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

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

inline

Return true if this is a consistent randomized tree.

Definition at line 502 of file tpl_rand_tree.H.

References Aleph::check_rank_tree(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

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

Member Data Documentation

cmp

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

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

private

Definition at line 159 of file tpl_rand_tree.H.

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::find_position(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::get_compare(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::key_comp(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::key_comp(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::operator=(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::position(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_remove(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_search_or_insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::swap().

r

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

gsl_rng* Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::r

private

Definition at line 158 of file tpl_rand_tree.H.

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::~Gen_Rand_Tree(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::find_position(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::gsl_rng_object(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::init(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::operator=(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join_exclusive(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_search_or_insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::set_seed(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::swap().

tree_root

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

Node* Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root

private

The type of node.

Definition at line 157 of file tpl_rand_tree.H.

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::find_position(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::is_empty(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::join_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::operator=(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::position(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove_pos(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::select(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::size(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::split_key(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::split_pos(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::swap(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::verify().

---

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

• tpl_rand_tree.H