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

Treap - A randomized binary search tree using heap-ordered priorities. More...

#include <tpl_treap.H>

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

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

Public Types
using	Node = NodeType< Key >

Public Member Functions
void	set_seed (const unsigned long seed) noexcept
	Set the random number generator seed.
void	swap (Gen_Treap &tree) noexcept
	Swap in constant time all the nodes of this with tree
Compare &	key_comp () noexcept
	return the comparison criteria
Compare &	get_compare () noexcept
	Gen_Treap (const unsigned long seed, const Compare &__cmp=Compare())
	Initialize a treap with random seed and comparison criteria __cmp
	Gen_Treap (const Compare &cmp=Compare())
	Initialize a treap with random seed from system time and comparison criteria cmp
	~Gen_Treap ()
gsl_rng *	gsl_rng_object () noexcept
	Get a pointer to gsl random number generator.
Node *&	getRoot () noexcept
	Return the tree's root.
Node *	search (const Key &key) const noexcept
	Search a key in a treap.
Node *	insert (Node *p) noexcept
	Insert a node in a treap.
Node *	search_or_insert (Node *p) noexcept
	Search or insert a key.
Node *	insert_dup (Node *p) noexcept
	Insert a node in the tree.
bool	verify () const noexcept
	Return true if this is a consistent treap.
Node *	remove (const Key &key) noexcept
	Remove a key from the tree.
void	join (Gen_Treap &t, Gen_Treap &dup) noexcept
	Join this with t filtering the duplicated keys.
void	join_dup (Gen_Treap &t) noexcept
	Join this with t independently of the presence of duplicated keys.
void	join_exclusive (Gen_Treap &t) noexcept
	Join exclusive of this with t
bool	split_key (const Key &key, Gen_Treap &t1, Gen_Treap &t2)
	Split the tree according to a key.
void	split_key_dup (const Key &key, Gen_Treap &t1, Gen_Treap &t2)
	Split the tree according to a key that could be in the tree.

Private Member Functions
void	init (const unsigned int seed)
Node *	insert (Node *root, Node *p) noexcept
Node *	search_or_insert (Node *&root, Node *p) noexcept
Node *	insert_dup (Node *root, Node *p) noexcept
Node *	remove (Node *&root, const Key &key) noexcept
void	join_dup (Node *&t1, Node *t2) noexcept
void	join (Node *&t1, Node *t2, Node *&dup) noexcept

Static Private Member Functions
static Node *	join_exclusive (Node *t1, Node *t2) noexcept

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

Detailed Description

template<template< typename > class NodeType, typename Key, class Compare>
requires StrictWeakOrder<Compare, Key>
class Aleph::Gen_Treap< NodeType, Key, Compare >

Treap - A randomized binary search tree using heap-ordered priorities.

A Treap (tree + heap) is a randomized binary search tree that combines BST properties on keys with heap properties on randomly assigned priorities. Each node has a key (BST-ordered) and a random priority (heap-ordered).

Key Properties:

• Keys follow BST ordering: left < parent < right
• Priorities follow max-heap ordering: parent priority > child priorities
• Priorities are randomly assigned at insertion time
• Expected O(log n) height due to randomization

The dual ordering (BST for keys, heap for priorities) creates a unique tree structure for any set of keys with given priorities, ensuring good balance with high probability.

Comparison with Other Randomized Trees:

• Treap vs Rand_Tree: Treap is typically faster by a constant factor because priorities are chosen once at insertion (bottom-up balancing), while Rand_Tree makes random decisions at each level (top-down).
• Treap vs AVL/RB: Treap has simpler code, uses randomization instead of deterministic balancing, but has expected (not worst-case) guarantees.

Template Parameters

NodeType	Node template (TreapNode or TreapNodeVtl).
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
• Split: O(log n) expected
• Join: O(log n) expected
• Space: O(n) + O(1) per node for priority

Random Number Generator:

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

Example:

Treap<int> tree;
 
// Set seed for reproducibility (optional)
tree.set_seed(12345);
 
// Insert nodes
tree.insert(new Treap<int>::Node(42));
tree.insert(new Treap<int>::Node(17));
tree.insert(new Treap<int>::Node(99));
 
// Search
auto node = tree.search(42);
if (node != nullptr)
  std::cout << "Found: " << node->get_key()
            << " (priority: " << PRIO(node) << ")" << '\n';
 
// Split tree at key 50
Treap<int> left, right;
tree.split_key(50, left, right);
 
// Join trees
tree.join(left, right);
 
// Remove
auto removed = tree.remove(42);
delete removed;

Note

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

Priorities are assigned automatically and transparently.

For ranked operations (indexed access), use TreapRk instead.

See also

Treap Convenient typedef for Treap<Key, Compare>.

TreapRk Treap variant with rank support for O(log n) indexed access.

Rand_Tree Alternative randomized tree with top-down balancing.

DynSetTreap High-level wrapper with automatic memory management.

Definition at line 149 of file tpl_treap.H.

Member Typedef Documentation

Node

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

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

Definition at line 152 of file tpl_treap.H.

Constructor & Destructor Documentation

Gen_Treap() [1/2]

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

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

inline

Initialize a treap with random seed and comparison criteria __cmp

Definition at line 191 of file tpl_treap.H.

References Aleph::init, and seed.

Gen_Treap() [2/2]

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

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

inline

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

Definition at line 199 of file tpl_treap.H.

~Gen_Treap()

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

Aleph::Gen_Treap< NodeType, Key, Compare >::~Gen_Treap ( )

inline

Definition at line 204 of file tpl_treap.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Treap< NodeType, Key, Compare >::r.

Member Function Documentation

get_compare()

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

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

inlinenoexcept

Definition at line 187 of file tpl_treap.H.

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

getRoot()

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

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

inlinenoexcept

Return the tree's root.

Definition at line 214 of file tpl_treap.H.

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

Referenced by main(), TreapTest::tree_empty(), TreapTest::tree_size(), and write_treap().

gsl_rng_object()

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

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

inlinenoexcept

Get a pointer to gsl random number generator.

Definition at line 211 of file tpl_treap.H.

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

Referenced by main().

init()

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

void Aleph::Gen_Treap< NodeType, Key, Compare >::init ( const unsigned int  seed )

inlineprivate

Definition at line 161 of file tpl_treap.H.

References ah_bad_alloc_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::head_ptr, Aleph::Min_Priority, Aleph::PRIO(), Aleph::Gen_Treap< NodeType, Key, Compare >::r, and seed.

insert() [1/2]

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

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

inlinenoexcept

Insert a node in a treap.

insert(p) inserta el nodo p en el treap this.

Parameters

[in]

p

pointer to the node to be inserted

Returns

if p->get_key() is not in the tree, then p is inserted and this node pointer is returned. Otherwise, it is returned nullptr.

Definition at line 320 of file tpl_treap.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::PRIO(), Aleph::Gen_Treap< NodeType, Key, Compare >::r, and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

insert() [2/2]

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

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

inlineprivatenoexcept

Definition at line 229 of file tpl_treap.H.

References Aleph::Gen_Treap< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), KEY, LLINK, Aleph::PRIO(), RLINK, root(), Aleph::rotate_to_left(), and Aleph::rotate_to_right().

Referenced by Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), TreapTest::insert_values(), Aleph::Gen_Treap< NodeType, Key, Compare >::join(), main(), and write_treap().

insert_dup() [1/2]

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

Node * Aleph::Gen_Treap< 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 362 of file tpl_treap.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), Aleph::PRIO(), Aleph::Gen_Treap< NodeType, Key, Compare >::r, and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

insert_dup() [2/2]

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

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

inlineprivatenoexcept

Definition at line 292 of file tpl_treap.H.

References Aleph::Gen_Treap< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), KEY, LLINK, Aleph::PRIO(), RLINK, root(), Aleph::rotate_to_left(), and Aleph::rotate_to_right().

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

join() [1/2]

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

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

inlinenoexcept

Join this with t filtering the duplicated keys.

join(t, dup) produces a treap 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	ramdomized tree to join with this
[out]	dup	ramdomized tree where nodes containing duplicated keys are inserted

Definition at line 507 of file tpl_treap.H.

References Aleph::Gen_Treap< NodeType, Key, Compare >::join(), and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

join() [2/2]

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

void Aleph::Gen_Treap< NodeType, Key, Compare >::join ( Node *&  t1, Node *  t2, Node *&  dup  )

inlineprivatenoexcept

Definition at line 474 of file tpl_treap.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap< NodeType, Key, Compare >::join(), KEY, l, LLINK, Aleph::Gen_Treap< NodeType, Key, Compare >::r, Aleph::Gen_Treap< NodeType, Key, Compare >::remove(), and RLINK.

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

join_dup() [1/2]

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

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

inlinenoexcept

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

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

Parameters

[in]

t

ramdomized tree to join with this keys are inserted

Definition at line 521 of file tpl_treap.H.

References Aleph::Gen_Treap< NodeType, Key, Compare >::join_dup(), and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

join_dup() [2/2]

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

void Aleph::Gen_Treap< NodeType, Key, Compare >::join_dup ( Node *&  t1, Node *  t2  )

inlineprivatenoexcept

Definition at line 462 of file tpl_treap.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap< NodeType, Key, Compare >::join_dup(), l, LLINK, Aleph::Gen_Treap< NodeType, Key, Compare >::r, and RLINK.

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

join_exclusive() [1/2]

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

void Aleph::Gen_Treap< NodeType, Key, Compare >::join_exclusive ( Gen_Treap< 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 knowlege allows a more effcient 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

ramdomized tree to exclusively join with this keys are inserted

Definition at line 538 of file tpl_treap.H.

References Aleph::Gen_Treap< NodeType, Key, Compare >::join_exclusive(), and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

join_exclusive() [2/2]

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

static Node * Aleph::Gen_Treap< NodeType, Key, Compare >::join_exclusive ( Node *  t1, Node *  t2  )

inlinestaticprivatenoexcept

Definition at line 427 of file tpl_treap.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::join_exclusive(), LLINK, Aleph::PRIO(), and RLINK.

Referenced by Aleph::Gen_Treap< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Treap< NodeType, Key, Compare >::join_exclusive(), and Aleph::Gen_Treap< NodeType, Key, Compare >::remove().

key_comp()

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

Aleph::Gen_Treap< 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 184 of file tpl_treap.H.

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

Referenced by Aleph::Gen_Treap< NodeType, Key, Compare >::get_compare().

remove() [1/2]

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

Node * Aleph::Gen_Treap< 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 381 of file tpl_treap.H.

References Aleph::and, Aleph::Gen_Treap< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::head_ptr, KEY, LLINK, Aleph::PRIO(), RLINK, Aleph::rotate_to_left(), Aleph::rotate_to_right(), and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

Referenced by Aleph::Gen_Treap< NodeType, Key, Compare >::join(), main(), and Aleph::Gen_Treap< NodeType, Key, Compare >::remove().

remove() [2/2]

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

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

inlineprivatenoexcept

Definition at line 444 of file tpl_treap.H.

References Aleph::Gen_Treap< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::join_exclusive(), KEY, LLINK, Aleph::Gen_Treap< NodeType, Key, Compare >::remove(), RLINK, and root().

search()

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

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

inlinenoexcept

Search a key in a treap.

Parameters

[in]

key

to be searched

Returns

a pointer to the node containing key if this is found; otherwise, nullptr is returned

Definition at line 222 of file tpl_treap.H.

References Aleph::Gen_Treap< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::searchInBinTree(), and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

Referenced by main(), and write_treap().

search_or_insert() [1/2]

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

Node * Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert ( Node *&  root, Node *  p  )

inlineprivatenoexcept

Definition at line 263 of file tpl_treap.H.

References Aleph::Gen_Treap< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, Aleph::PRIO(), RLINK, root(), Aleph::rotate_to_left(), Aleph::rotate_to_right(), and Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert().

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

search_or_insert() [2/2]

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

Node * Aleph::Gen_Treap< 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 346 of file tpl_treap.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::PRIO(), Aleph::Gen_Treap< NodeType, Key, Compare >::r, Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert(), and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

set_seed()

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

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

inlinenoexcept

Set the random number generator seed.

Definition at line 173 of file tpl_treap.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Treap< NodeType, Key, Compare >::r, and seed.

Referenced by main(), and TreapTest::SetUp().

split_key()

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

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

inline

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 552 of file tpl_treap.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::split_key_rec(), and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

split_key_dup()

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

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

inline

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 567 of file tpl_treap.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::split_key_dup_rec(), and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

swap()

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

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

inlinenoexcept

Swap in constant time all the nodes of this with tree

Definition at line 176 of file tpl_treap.H.

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

verify()

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

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

inlinenoexcept

Return true if this is a consistent treap.

Definition at line 373 of file tpl_treap.H.

References Aleph::is_treap(), and Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root.

Member Data Documentation

cmp

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

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

private

Definition at line 159 of file tpl_treap.H.

Referenced by Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap< NodeType, Key, Compare >::key_comp(), Aleph::Gen_Treap< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap< NodeType, Key, Compare >::search(), Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert(), and Aleph::Gen_Treap< NodeType, Key, Compare >::swap().

head

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

Node Aleph::Gen_Treap< NodeType, Key, Compare >::head

private

The type of node.

Definition at line 155 of file tpl_treap.H.

head_ptr

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

Node* Aleph::Gen_Treap< NodeType, Key, Compare >::head_ptr

private

Definition at line 156 of file tpl_treap.H.

Referenced by Aleph::Gen_Treap< NodeType, Key, Compare >::init(), and Aleph::Gen_Treap< NodeType, Key, Compare >::remove().

r

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

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

private

Definition at line 158 of file tpl_treap.H.

Referenced by Aleph::Gen_Treap< NodeType, Key, Compare >::~Gen_Treap(), Aleph::Gen_Treap< NodeType, Key, Compare >::gsl_rng_object(), Aleph::Gen_Treap< NodeType, Key, Compare >::init(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap< NodeType, Key, Compare >::join(), Aleph::Gen_Treap< NodeType, Key, Compare >::join_dup(), Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::set_seed(), and Aleph::Gen_Treap< NodeType, Key, Compare >::swap().

tree_root

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

Node*& Aleph::Gen_Treap< NodeType, Key, Compare >::tree_root

private

Definition at line 157 of file tpl_treap.H.

Referenced by Aleph::Gen_Treap< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap< NodeType, Key, Compare >::join(), Aleph::Gen_Treap< NodeType, Key, Compare >::join_dup(), Aleph::Gen_Treap< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Treap< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap< NodeType, Key, Compare >::search(), Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::split_key(), Aleph::Gen_Treap< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Treap< NodeType, Key, Compare >::swap(), and Aleph::Gen_Treap< NodeType, Key, Compare >::verify().

---

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

• tpl_treap.H