#include <tpl_treapRk.H>

Diagrama de herencias de Aleph::Treap_Rk< Key, Compare >

Diagrama de colaboración para Aleph::Treap_Rk< Key, Compare >:

Métodos públicos
	Treap_Rk (unsigned int seed, Compare &&cmp=Compare())

	Treap_Rk (Compare &&cmp=Compare())

	Treap_Rk (unsigned int seed, Compare &cmp)

	Treap_Rk (Compare &cmp)

Métodos públicos heredados desde Aleph::Gen_Treap_Rk< Treap_Rk_Node, Key, Compare >
Compare &	key_comp ()
	Retorna una referencia al criterio de comparación.

Compare &	get_compare ()

	Gen_Treap_Rk (unsigned int seed, Compare &__cmp)
	Constructor; inicializa generador de números aleatorios.

	Gen_Treap_Rk (unsigned int seed, Compare &&__cmp)

	Gen_Treap_Rk (const Gen_Treap_Rk &)

void	swap (Gen_Treap_Rk &tree)

Node *&	getRoot ()
	Retorna la raíz del treap extendido.

Node *	search (const Key &key)
	Busca la clave key en el treap extendido this.

Node *	insert (Node *p)

Node *	search_or_insert (Node &root, Node p)

Node *	search_or_insert (Node *p)

Node *	insert_dup (Node &root, Node p)

Node *	insert_dup (Node *p)

bool	verify ()

Node *	remove (const Key &key)

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

Node *	select (const size_t &i)

size_t	size () const
	Retorna la cantidad de nodos que contiene el treap.

bool	is_empty () const
	Retorna true si el treap está vacío.

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

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

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

bool	split_key_dup (const Key &key, Gen_Treap_Rk &t1, Gen_Treap_Rk &t2)

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

void	join (Gen_Treap_Rk &t, Gen_Treap_Rk &dup)

void	join_dup (Gen_Treap_Rk &t)

Otros miembros heredados
Tipos públicos heredados desde Aleph::Gen_Treap_Rk< Treap_Rk_Node, Key, Compare >
typedef Treap_Rk_Node< Key >	Node
	El tipo de nodo interno.

Descripción detallada

template<class Key, class Compare = Aleph::less<Key>>
class Aleph::Treap_Rk< Key, Compare >

Árbol binario extendido de búsqueda aleatorizado genérico de tipo Treap con nodos sin destructor virtual.

Un treap extendido es una clase especial de árbol binario de búsqueda en el cual sus operaciones de modificación son aleatorizadas. Consecuentemente, todas las operaciones sobre esta clase de árbol binario son $O(\lg n)$ , independientemente de cualquier sesgo que exista acerca del orden de inserción o eliminación de claves.

El carácter "extendido" facilita las siguientes bondades sobre el conjunto de elementos:

Inserción, búsqueda y eliminación de una clave.
Acceso al i-ésimo elemento del recorrido infijo.
Conocimiento de la posición infija dada una clave.
Unión y partición según clave o posición infija. Todas estas operaciones se realizan en tiempo esperado de $O(\lg n)$ .

El treap es probablemente la clase árbol binario de búsqueda que preserva un equilibrio probabilístico con mejor desempeño. Estudios empíricos sugieren que éste es el tipo de árbol binario de búsqueda más rápido.

En estudios de rendimiento, la clase estándar set<T> y map<T> implantadas mediante el tipo TreapRk demuestran mayor rapidez que las implantaciones gnu y Boost.

Parámetros

Key	el tipo de clave a guardar en los nodos.
Compare	el criterio de comparación entre las claves de los nodos.

Ver también: Treap Treap_Vtl Treap_Rk Treap_Rk_Vtl set multiset map multimap

Documentación del constructor y destructor

template<class Key, class Compare = Aleph::less<Key>>

Aleph::Treap_Rk< Key, Compare >::Treap_Rk	(	unsigned int	seed,
		Compare &&	cmp = `Compare()`
	)

inline

Inicia el generador de números aleatorios con el valor seed y coloca la operación de comparación cmp

La documentación para esta clase fue generada a partir del siguiente fichero:

tpl_treapRk.H

Métodos públicos

Otros miembros heredados

Descripción detallada

template<class Key, class Compare = Aleph::less<Key>> class Aleph::Treap_Rk< Key, Compare >

Documentación del constructor y destructor

template<class Key, class Compare = Aleph::less<Key>>
class Aleph::Treap_Rk< Key, Compare >