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

#include <tpl_treap.H>

Tipos públicos

typedef NodeType< Key > Node
 Tipo de nodo del treap.
 

Métodos públicos

void swap (Gen_Treap &tree)
 
Compare & key_comp ()
 Retorna una referencia al criterio de comparación.
 
Compare & get_compare ()
 
 Gen_Treap (unsigned int seed, Compare &__cmp)
 Constructor; inicializa generador de números aleatorios.
 
 Gen_Treap (unsigned int seed, Compare &&__cmp)
 
 ~Gen_Treap ()
 Destructor; libera memoria de generador de números aleatorios.
 
gsl_rng * gsl_rng_object ()
 Obtiene un puntero al objeto gsl_rng generador de números aleatorios.
 
Node *& getRoot ()
 Retorna la raíz del treap.
 
Node * search (const Key &key)
 Busca la clave key en el treap.
 
Node * insert (Node *p)
 
Node * search_or_insert (Node *p)
 
Node * insert_dup (Node *p)
 
bool verify ()
 
Node * remove (const Key &key)
 

Descripción detallada

template<template< typename > class NodeType, typename Key, class Compare>
class Aleph::Gen_Treap< NodeType, Key, Compare >

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

Un treap 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 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.

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

Documentación de las funciones miembro

template<template< typename > class NodeType, typename Key, class Compare>
Compare& Aleph::Gen_Treap< 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< typename > class NodeType, typename Key, class Compare>
Node* Aleph::Gen_Treap< NodeType, Key, Compare >::insert ( Node *  p)
inline

Insertar el nodo p en un treap.

insert(p) inserta el nodo p en el treap 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< typename > class NodeType, typename Key, class Compare>
Node* Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup ( Node *  p)
inline

Insertar el nodo p en un treap.

insert(p) inserta el nodo p en el treap 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< typename > class NodeType, typename Key, class Compare>
Node* Aleph::Gen_Treap< NodeType, Key, Compare >::remove ( const Key &  key)
inline

Elimina la clave key del treap.

remove(key) busca la clave key en el treap 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< typename > class NodeType, typename Key, class Compare>
Node* Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert ( Node *  p)
inline

Busca la clave de p en el árbol binario de búsqueda o lo inserta en caso de no encontrarse.

search_or_insert(p) busca en el árbol binario un nodo cuya clave sea KEY(p). Si la clave se encuentra, entonces se rerona un puntero al nodo que la alberga. De lo contrario se inserta p en el árbol binario de búsqueda this.

Parámetros
[in]pel nodo a buscar o insertar.
Devuelve
puntero al nodo insertado si la clave de p no está contenida dentro del árbol; De lo contrario, se retorna un puntero al nodo dentro del árbol que contiene a KEY(p).
template<template< typename > class NodeType, typename Key, class Compare>
void Aleph::Gen_Treap< NodeType, Key, Compare >::swap ( Gen_Treap< 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