Aleph-w  1.9
General library for algorithms and data structures
Classes | Public Types | Public Member Functions | List of all members
Aleph::Gen_Treap< NodeType, Key, Compare > Class Template Reference
Trees

#include <tpl_treap.H>

Classes

struct  Iterator
 

Public Types

using Node = NodeType< 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
 
 Gen_Treap (unsigned long seed, Compare &__cmp=Compare())
 
 Gen_Treap (Compare cmp=Compare())
 
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 (Gen_Treap &t, Gen_Treap &dup) noexcept
 
void join_dup (Gen_Treap &t) noexcept
 
void join_exclusive (Gen_Treap &t) 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<template< typename > class NodeType, typename Key, class Compare>
class Aleph::Gen_Treap< NodeType, Key, Compare >

Treap (a special type of ramdomized binary search tree).

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). 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

Constructor & Destructor Documentation

◆ Gen_Treap() [1/2]

template<template< typename > class NodeType, typename Key, class Compare>
Aleph::Gen_Treap< NodeType, Key, Compare >::Gen_Treap ( unsigned long  seed,
Compare &  __cmp = Compare() 
)
inline

Initialize a treap with random seed and comparison criteria __cmp

◆ Gen_Treap() [2/2]

template<template< typename > class NodeType, typename Key, class Compare>
Aleph::Gen_Treap< NodeType, Key, Compare >::Gen_Treap ( Compare  cmp = Compare())
inline

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

Member Function Documentation

◆ get_compare()

template<template< typename > class NodeType, typename Key, class Compare>
Compare& Aleph::Gen_Treap< 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< 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]ppointer 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< 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]ppointer to the node to insert
Returns
the p pointer

◆ join()

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

◆ join_dup()

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

◆ join_exclusive()

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

◆ remove()

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]keyto remove
Returns
a valid pointer to the removed node if key was found in the tree, nullptr otherwise

◆ 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]keyto be searched
Returns
a pointer to the node containing key if this is found; otherwise, nullptr is returned

◆ search_or_insert()

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]pnode 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()

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]keyfor splitting
[out]t1tree with keys lesser than key
[out]t2tree 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< 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]keyfor splitting
[out]t1resulting tree with the keys lesser than key
[out]t2resulting tree with the keys greater or equal than key
The documentation for this class was generated from the following file:
Leandro Rabindranath León