#include <tpl_treapRk.H>
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. | |
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_NodeVtl, Key, Compare > | |
typedef Treap_Rk_NodeVtl< Key > | Node |
El tipo de nodo interno. | |
Á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 , 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:
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.
Key | el tipo de clave a guardar en los nodos. |
Compare | el criterio de comparación entre las claves de los nodos. |
|
inline |
Inicia el generador de números aleatorios con el valor seed y coloca la operación de comparación cmp