Aleph-w  1.5a.2
Biblioteca general de algoritmos y estructuras de datos
 Todo Clases Archivos Funciones Variables 'typedefs' Enumeraciones Amigas Grupos Páginas
Clases | Tipos públicos | Métodos públicos | Lista de todos los miembros
Referencia de la plantilla de la Clase Aleph::Gen_Treap_Rk< NodeType, Key, Compare >
Árboles con raíz

#include <tpl_treapRk.H>

Clases

class  Iterator
 

Tipos públicos

typedef NodeType< Key > Node
 El tipo de nodo interno.
 

Métodos públicos

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 * search_or_insert (Node *&root, Node *p)
 
Node * insert_dup (Node *&root, Node *p)
 
Node * insert (Node *p)
 
Node * insert_dup (Node *p)
 
Node * search_or_insert (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)
 

Descripción detallada

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

Árbol binario extendido de búsqueda aleatorizado genérico de tipo Treap.

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:

  1. Inserción, búsqueda y eliminación de una clave.
  2. Acceso al i-ésimo elemento del recorrido infijo.
  3. Conocimiento de la posición infija dada una clave.
  4. 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
NodeTypeel tipo de nodo que manejará el árbol. Puede ser de tipo TreapNode o TreapNodeVtl según se desee o no tener destructores virtuales.
Keyel tipo de clave a guardar en los nodos.
Compareel 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<template< class > class NodeType, class Key, class Compare>
Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Gen_Treap_Rk ( const Gen_Treap_Rk< NodeType, Key, Compare > &  )
inline

Constructor copia "tronco".

Este constructor es provisto con fines de "uso provisorio". No efectúa copia del estado del árbol.

Documentación de las funciones miembro

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

Retorna la posición infija (ordenada) de la clave key.

find_position(key) busca en el treap extendido la clave key (lo cual toma tiempo $O(\lg n)$) y retorna la posición infija del nodo que contiene la clave junto con el nodo. En caso de que la clave no esté en el árbol, position(key) retorna la posición donde debería estar si key perteneciese al árbol.

El valor de retorno es un pair<int,Node*>. El campo first es la posición infija y second el nodo.

Si key no se encuentra en el árbol, entonces se pueden distinguir tres casos:

  1. Si key es menor que la mínima clave del árbol, entonces first -1 y second es el nodo contentivo de la clave mínima.
  2. Si key es mayor que la máxima clave del árbol, entonces first es COUNT(r) (número de nodos del árbol) y second es el nodo contentivo de la clave máxima.
  3. En cualquier otro caso, first es la posición que tendría la clave key en árbol y second nodo p es una clave inmediatamente adyancente a key. Note que second puede tener una clave menor o mayor, pero se garantiza que es inmediatamente continua a key.
Parámetros
[in]keyclave a buscar y a determinar posición infija.
Devuelve
un par conteniendo la posición infija de la clave key dentro del conjunto ordenado junto con el nodo si la clave se encuentra en el mapeo; de lo contrarion, se retorna -1 y el nodo es indeterminado.

Referenciado por Aleph::Gen_Treap_Rk< Treap_Rk_Node, Key, Compare >::find_position().

+ Gráfico de llamadas a esta función:

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

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

template<template< class > class NodeType, class Key, class Compare>
Node* Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert ( Node *  p)
inline

Insertar el nodo p en el treap extendido this.

insert(p) inserta el nodo p en el treap extendido this.

Parámetros
[in]pel nodo a insertar.
Devuelve
puntero al nodo recién insertado si su clave no estaba contenida en el treap; NULL de lo contrario.
template<template< class > class NodeType, class Key, class Compare>
Node* Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup ( Node *  p)
inline

Inserta el nodo p en el treap extendido this con posibilidad de duplicación.

insert_dup(p) inserta el nodo p en el treap extendido this.

Parámetros
[in]pel nodo a insertar.
Devuelve
puntero al nodo recién insertado.
template<template< class > class NodeType, class Key, class Compare>
std::pair<int, Node*> Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::position ( const Key &  key)
inline

Retorna la posición infija (ordenada) de la clave key.

position(key) busca en el treap extendido la clave key (lo cual toma tiempo $O(\lg n)$) y retorna la posición infija del nodo que contiene la clave.

Parámetros
[in]keyclave a buscar y a determinar posición infija.
Devuelve
un par conteniendo la posición infija de la clave key dentro del conjunto ordenado junto con el nodo si la clave se encuentra en el mapeo; de lo contrarion, se retorna -1 y el nodo es indeterminado.
template<template< class > class NodeType, class Key, class Compare>
Node* Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove ( const Key &  key)
inline

Elimina la clave key del treap extendido this.

remove(key) busca la clave key en el treap extendido this y, de encontrarse la clave, elimina el nodo del treap.

Parámetros
[in]keyclave a eliminar.
Devuelve
puntero al nodo recién eliminado si la clave se encuentra en el treap; NULL de lo contrario.
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

Elimina del treap extendido todas las claves comprendidas entre la posición infija beg y end.

rmeove(beg,end) elimina del treap extendido this todas las claves entre las posiciones infijas beg y end. Se retorna un arbol que contiene las claves borradas.

Parámetros
[in]begposición infija donde comienza el rango a ser eliminado.
[in]endposición infija donde termina el rango a ser eliminado.
Devuelve
un puntero a la raíz del treap extendido que contiene todas las claves eliminadas.
Excepciones
range_errorsi el rango de posiciones infijas es inválido.
template<template< class > class NodeType, class Key, class Compare>
Node* Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert ( Node *  p)
inline

Busca o inserta la clave KEY(p).

search_or_insert() busca en el treap un nodo que contenga la clave KEY(p). Si tal nodo se encuentra, entonces éste se retorna; de lo contrario, se inserta p y se retorna como resultado.

Parámetros
[in]pnodo a eventualmente insertar.
Devuelve
si KEY(p) se encuentra en el árbol, entonces se retorna un puntero al nodo contentivo de KEY(p). De lo contrario, se inserta p en el treap y se retorna p.
template<template< class > class NodeType, class Key, class Compare>
Node* Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::select ( const size_t &  i)
inline

Retorna el nodo cuya posición infija en el treap extendido es i.

select(i) retorna el nodo del treap extendido cuya posición infija es i.

Parámetros
[in]iposición infija a seleccionar.
Devuelve
puntero al nodo correspondiente a la posición infija i.
Excepciones
out_of_rangesi i es mayor o igual que la cantidad de nodos que contiene el treap.
template<template< class > class NodeType, class Key, class Compare>
void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::swap ( Gen_Treap_Rk< NodeType, Key, Compare > &  tree)
inline

Intercambia todos los elementos del treap this con el treap tree en tiempo contante (y extremadamente rápido).

Parámetros
[in]treeel treap a intercambiar con this
La documentación para esta clase fue generada a partir del siguiente fichero:
Leandro Rabindranath León