Aleph-w  1.5a.2
Biblioteca general de algoritmos y estructuras de datos
 Todo Clases Archivos Funciones Variables 'typedefs' Enumeraciones Amigas Grupos Páginas
Referencia de la plantilla de la Clase Aleph::Treap_Rk_Vtl< Key, Compare >

#include <tpl_treapRk.H>

+ Diagrama de herencias de Aleph::Treap_Rk_Vtl< Key, Compare >
+ Diagrama de colaboración para Aleph::Treap_Rk_Vtl< Key, Compare >:

Métodos públicos

 Treap_Rk_Vtl (unsigned int seed, Compare &&cmp=Compare())
 
 Treap_Rk_Vtl (Compare &&cmp=Compare())
 
 Treap_Rk_Vtl (unsigned int seed, Compare &cmp)
 
 Treap_Rk_Vtl (Compare &cmp)
 
- Métodos públicos heredados desde Aleph::Gen_Treap_Rk< Treap_Rk_NodeVtl, 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.
 
Nodesearch (const Key &key)
 Busca la clave key en el treap extendido this.
 
Nodeinsert (Node *p)
 
Nodesearch_or_insert (Node *&root, Node *p)
 
Nodesearch_or_insert (Node *p)
 
Nodeinsert_dup (Node *&root, Node *p)
 
Nodeinsert_dup (Node *p)
 
bool verify ()
 
Noderemove (const Key &key)
 
Noderemove (const size_t &beg, const size_t &end)
 
Nodeselect (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_NodeVtl, Key, Compare >
typedef Treap_Rk_NodeVtl< Key > Node
 El tipo de nodo interno.
 

Descripción detallada

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

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

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
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<class Key , class Compare = Aleph::less<Key>>
Aleph::Treap_Rk_Vtl< Key, Compare >::Treap_Rk_Vtl ( 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:

Leandro Rabindranath León