#include <tpl_treapRk.H>

Classes
class	Iterator

Public Types
using	Node = NodeType< Key >

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

Compare &	key_comp () noexcept
	return the comparison criteria

Compare &	get_compare () noexcept

	Gen_Treap_Rk (unsigned long seed, Compare __cmp=Compare())

	Gen_Treap_Rk (Compare __cmp=Compare())

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

Node *&	getRoot () noexcept
	Return the tree's root.

Node *	getRoot () const noexcept

Node *	search (const Key &key) const noexcept

Node *	insert (Node *p) noexcept

Node *	insert_dup (Node *p) noexcept

Node *	search_or_insert (Node *p) noexcept

bool	verify () const
	Return `true` if the treap is consistent.

Node *	remove (const Key &key) noexcept

Node *	remove (const size_t beg, const size_t end)

Node *	remove_pos (const size_t pos)

Node *	select (const size_t i) const

size_t	size () const noexcept
	Return the number of nodes contained in the tree.

bool	is_empty () const noexcept
	Return `true` if tree is empty.

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

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

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

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

void	split_pos (size_t pos, Gen_Treap_Rk &t1, Gen_Treap_Rk &t2)

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

void	join_dup (Gen_Treap_Rk &t) noexcept

void	join_exclusive (Gen_Treap_Rk &t) noexcept

Detailed Description

template<template< class > class NodeType, class Key, class Compare>
class Aleph::Gen_Treap_Rk< NodeType, Key, Compare >

Extended treap (a special type of ramdomized binary search tree) which manages selection and splitting for inorder position.

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. In addition, this extended tree uses and second integer for storing subtrees sizes.

The treap is faster than the randomized tree by a constant time (both approaches are logarithmic). 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.

Although tgus approach trends to be faster than the randomized trees, takes in account that this treap is more space consuming because each node requires 2 additional integers to the data (priority and counter) in constrast with the radomized which only requieres one interger (the counter).

For splitting and join of independent and large data sets the ramdomized option trends to be faster. The split is equivalent, but the join is definitively faster. The join of two trees of n and m keys respectively takes $O(n \lg m)$ with treaps, while it takes $O(\max(\lg n, \lg m))$ with radomized trees. In addition,

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

Constructor & Destructor Documentation

◆ Gen_Treap_Rk()

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

Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Gen_Treap_Rk	(	unsigned long	seed,
		Compare	__cmp = `Compare()`
	)

inline

Initialize a treap with random seed and comparison criteria __cmp

Member Function Documentation

◆ find_position()

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

std::pair<int, Node*> Aleph::Gen_Treap_Rk< 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 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

Here is the caller graph for this function:

◆ get_compare()

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

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

inlinenoexcept

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

◆ insert()

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

Node* Aleph::Gen_Treap_Rk< 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.

◆ insert_dup()

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

Node* Aleph::Gen_Treap_Rk< 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

◆ join()

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

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join	(	Gen_Treap_Rk< NodeType, Key, Compare > &	t,
		Gen_Treap_Rk< 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	ramdomized tree to join with `this`
[out]	dup	ramdomized tree where nodes containing duplicated keys are inserted

◆ join_dup()

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

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup ( Gen_Treap_Rk< 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

◆ join_exclusive()

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

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

◆ remove() [1/2]

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

Node* Aleph::Gen_Treap_Rk< 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

◆ remove() [2/2]

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

Node* Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove	(	const size_t	beg,
		const size_t	end
	)

inline

Remove from the treap all the keys between inorder position beg and end.

Parameters

[in]	beg	beggining inorder position
[in]	end	ending inorder position

Returns: a pointer to a tree root containing all the removed nodes

Exceptions

range_error if the range is invalid

◆ remove_pos()

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

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

inline

Remove the node at the inorder position pos

Parameters

[in] pos inorder position of node to be removed

Returns: a vaid pointer to the removed node

Exceptions

out_of_range if pos is greater or equal than the number of nodes of tree

◆ search()

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

Node* Aleph::Gen_Treap_Rk< 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

◆ search_or_insert()

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

Node* Aleph::Gen_Treap_Rk< 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

◆ select()

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

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

inline

Return the i-th node in order sense

Parameters

[in] i inorder position of node to be selected

Returns: a pointer to the i-th node inorder sense

Exceptions

out_of_range if pos is greater or equal than the number of nodes of tree

◆ split_key()

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

bool Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_key	(	const Key &	key,
		Gen_Treap_Rk< NodeType, Key, Compare > &	t1,
		Gen_Treap_Rk< 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

◆ split_key_dup()

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

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_key_dup	(	const Key &	key,
		Gen_Treap_Rk< NodeType, Key, Compare > &	t1,
		Gen_Treap_Rk< 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`

◆ split_pos()

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

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

inline

Split the tree at the inorder position pos

Parameters

[in]	pos	inorder position where to split
[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 class was generated from the following file:

tpl_treapRk.H

Classes

Public Types

Public Member Functions

Detailed Description

template<template< class > class NodeType, class Key, class Compare> class Aleph::Gen_Treap_Rk< NodeType, Key, Compare >

Constructor & Destructor Documentation

◆ Gen_Treap_Rk()

Member Function Documentation

◆ find_position()

◆ get_compare()

◆ insert()

◆ insert_dup()

◆ join()

◆ join_dup()

◆ join_exclusive()

◆ remove() [1/2]

◆ remove() [2/2]

◆ remove_pos()

◆ search()

◆ search_or_insert()

◆ select()

◆ split_key()

◆ split_key_dup()

◆ split_pos()

template<template< class > class NodeType, class Key, class Compare>
class Aleph::Gen_Treap_Rk< NodeType, Key, Compare >