#include <tpl_rand_tree.H>

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

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

Public Types
using	Base = Gen_Rand_Tree< RandNode, Key, Compare >

using	Node = RandNode< Key >

Public Member Functions
Compare &	key_comp () noexcept
	return the comparison criteria

Compare &	get_compare () noexcept

gsl_rng *	gsl_rng_object () noexcept
	Get a pointer to gsl random number generator.

void	set_seed (unsigned long seed) noexcept
	Set the random number generator seed.

void	swap (Gen_Rand_Tree &tree) noexcept
	Swap in constant time all the nodes of `this` with `tree`

Node *	insert (Node *p) noexcept

Node *	insert_dup (Node *p) noexcept

Node *	remove (const Key &key) noexcept

Node *	search (const Key &key) const noexcept

Node *	search_or_insert (Node *p) noexcept

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

size_t	size () const noexcept
	Return the number of nodes that have the tree.

std::pair< long, Node *>	position (const Key &key) noexcept

std::pair< long, Node *>	find_position (const Key &key) noexcept

Node *	remove_pos (const size_t i) noexcept

bool	split_key (const Key &key, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2) noexcept

void	split_key_dup (const Key &key, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2) noexcept

void	split_pos (size_t pos, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2) noexcept

void	join (Gen_Rand_Tree &t, Gen_Rand_Tree &dup) noexcept

void	join_dup (Gen_Rand_Tree &t) noexcept

void	join_exclusive (Gen_Rand_Tree &t) noexcept

Detailed Description

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

Randomized binary sarch tree.

This class implements a randomized binary search tree. It is shown that this type of tree always is equivalent to a classic binary search tree built from a random insertion sequence. Consequently, all the operations of this tree are $O(\lg n)$ expected case, independentely of insertion order and of removals are interleaved with insertions.

The principle of this tree is balancing by taking random decisions whose probabilities guarantee that each node will have a chance of $1/n$ for becoming the root of the tree.

In addition, these trees support select() and position() operations. That is, their keys can be accessed according to their inorder position and logarithmic time. This allows to treat the tree as if it was an array.

This tree type is unbeatable when there are splits and and especially joins operations on very large and independent data sets. Other tree types perform the join of independent data sets in $O(n \lg m)$ , where $n$ and $m$ are the size of two data sets, while the randomized approach takes $O(\max(\lg n, \lg m))$ .

The class internally uses the gsl random number generator of GSL - GNU Scientific Library. By default, the Mersene twister is used and the seed is taken from system time.

See also: Treap Treap_Vtl Treap_Rk

Member Function Documentation

◆ find_position()

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

inlinenoexceptinherited

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 the tuple returns the position that would have key if this was in the tree and the parent node that the key would had. At this regard, there are three cases:

if key is lesser than the minimum key of tree, then first is -1 and the node is one with the smallest key.
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.
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 inmediataly greater than key.

Parameters

[in] key to be searched

Returns: a pair with the inorder position and and related node

◆ get_compare()

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

inlinenoexceptinherited

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

◆ insert()

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

inlinenoexceptinherited

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); othewise, nullptr is returned

◆ insert_dup()

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

inlinenoexceptinherited

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

◆ join()

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

inlinenoexceptinherited

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	ramdomized tree to join with `this`
[out]	dup	ramdomized tree where nodes containing duplicated keys are inserted

◆ join_dup()

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

inlinenoexceptinherited

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 ramdomized tree to join with this keys are inserted

◆ join_exclusive()

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

inlinenoexceptinherited

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

◆ position()

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

inlinenoexceptinherited

Compute the inorder position of a key

Parameters

[in] key to be searched

Returns: a tuple with the position of key and a pointer to the node containing it. If key is not in the tree, then first the first value is -1.

◆ remove()

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

inlinenoexceptinherited

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

◆ remove_pos()

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

inlinenoexceptinherited

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

◆ search()

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

inlinenoexceptinherited

Search a key.

Parameters

[in] key to be searched

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

◆ search_or_insert()

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

inlinenoexceptinherited

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

◆ select()

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

inlineinherited

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

◆ split_key()

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

inlinenoexceptinherited

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

◆ split_key_dup()

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

inlinenoexceptinherited

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`

◆ split_pos()

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

inlinenoexceptinherited

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 -

After completion this becames empty.

Parameters

[in]	pos	position for splitting
[out]	t1	tree where the rank of keys will be put
[out]	t2	tree where the rank of keys will be put

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

tpl_rand_tree.H

Public Types

Public Member Functions

Detailed Description

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

Member Function Documentation

◆ find_position()

◆ get_compare()

◆ insert()

◆ insert_dup()

◆ join()

◆ join_dup()

◆ join_exclusive()

◆ position()

◆ remove()

◆ remove_pos()

◆ search()

◆ search_or_insert()

◆ select()

◆ split_key()

◆ split_key_dup()

◆ split_pos()

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