#include <tpl_treap.H>

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

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

Public Types
using	Base = Gen_Treap< TreapNodeVtl, Key, Compare >

using	Node = TreapNodeVtl< Key >

Public Member Functions
void	set_seed (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

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

Node *	insert (Node *p) noexcept

Node *	search_or_insert (Node *p) noexcept

Node *	insert_dup (Node *p) noexcept

bool	verify () const noexcept
	Return `true` if `this` is a consistent treap.

Node *	remove (const Key &key) noexcept

void	join_exclusive (Gen_Treap &t) noexcept

void	join_dup (Gen_Treap &t) noexcept

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

bool	split_key (const Key &key, Gen_Treap &t1, Gen_Treap &t2)

void	split_key_dup (const Key &key, Gen_Treap &t1, Gen_Treap &t2)

Detailed Description

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

Treap (a special type of ramdomized binary search tree) using nodes with virtual destructors.

The treap is a binary search tree whose very high performance is achieved by randomization. The basic idea is to store a priority value in each node which is randomly chosen. By the side of keys, the tree a binary search, but by the side of priorities, the tree is a heap. It is shown that this class of tree has an expected perfomance of $O(\lg n)$ for the majority of its operations.

The treap is faster than the randomized tree by a constant time (both approaches are logarithmic). However, since the priority is chosen just one time and the adjustements are done in a botton-top way (by contrast with the randomized which is top-bottom), the treap takes less time.

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 Treap_Rk_Vtl Rand_Tree

Member Function Documentation

◆ get_compare()

Compare& Aleph::Gen_Treap< TreapNodeVtl , 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_Treap< TreapNodeVtl , Key, Compare >::insert ( Node * p )

inlinenoexceptinherited

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.

◆ insert_dup()

Node* Aleph::Gen_Treap< TreapNodeVtl , 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_Treap< TreapNodeVtl , Key, Compare >::join	(	Gen_Treap< TreapNodeVtl, Key, Compare > &	t,
		Gen_Treap< TreapNodeVtl, Key, Compare > &	dup
	)

inlinenoexceptinherited

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

◆ join_dup()

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

inlinenoexceptinherited

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

◆ join_exclusive()

void Aleph::Gen_Treap< TreapNodeVtl , Key, Compare >::join_exclusive ( Gen_Treap< TreapNodeVtl, 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

◆ remove()

Node* Aleph::Gen_Treap< TreapNodeVtl , 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

◆ search()

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

inlinenoexceptinherited

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

◆ search_or_insert()

Node* Aleph::Gen_Treap< TreapNodeVtl , 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

◆ split_key()

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

inlineinherited

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_Treap< TreapNodeVtl , Key, Compare >::split_key_dup	(	const Key &	key,
		Gen_Treap< TreapNodeVtl, Key, Compare > &	t1,
		Gen_Treap< TreapNodeVtl, Key, Compare > &	t2
	)

inlineinherited

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`

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

tpl_treap.H

Public Types

Public Member Functions

Detailed Description

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

Member Function Documentation

◆ get_compare()

◆ insert()

◆ insert_dup()

◆ join()

◆ join_dup()

◆ join_exclusive()

◆ remove()

◆ search()

◆ search_or_insert()

◆ split_key()

◆ split_key_dup()

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