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_Rand_Tree< NodeType, Key, Compare >
Árboles con raíz

#include <tpl_rand_tree.H>

Tipos públicos

typedef NodeType< Key > Node
 Tipo de nodo binario.
 

Métodos públicos

Compare & key_comp ()
 Retorna una referencia al criterio de comparación.
 
Compare & get_compare ()
 
gsl_rng * gsl_rng_object ()
 Obtiene un puntero al objeto gsl_rng generador de números aleatorios.
 
 Gen_Rand_Tree (unsigned int seed, Compare &&__cmp)
 
 Gen_Rand_Tree (unsigned int seed, Compare &__cmp)
 
void swap (Gen_Rand_Tree &tree)
 
virtual ~Gen_Rand_Tree ()
 Destructor (libera generador de números aleatorios.
 
Node * insert (Node *p)
 
Node * insert_dup (Node *p)
 
Node * random_join_exclusive (Node *tl, Node *tr)
 
Node * random_remove (Node *&root, const Key &key)
 
Node * remove (const Key &key)
 
Node * search (const Key &key)
 Busca la clave key en el árbol binario de búsqueda aleatorizado.
 
Node * search_or_insert (Node *p)
 
bool verify () const
 
Node *& getRoot ()
 
Node * select (const size_t &i) const
 
size_t size () const
 Retorna la cantidad de nodos que contiene el árbol.
 
std::pair< int, Node * > position (const Key &key)
 
std::pair< int, Node * > find_position (const Key &key)
 
bool split_key (const Key &key, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2)
 
bool split_key_dup (const Key &key, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2)
 
void split_pos (size_t pos, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2)
 
void join (Gen_Rand_Tree &t, Gen_Rand_Tree &dup)
 
void join_dup (Gen_Rand_Tree &t)
 

Descripción detallada

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

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

Un árbol binario de búsqueda aleatorizado es un árbol binario de búsqueda en el cual las operaciones de modificación (inserción y eliminación) se realizan de forma aleatoria. 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.

Parámetros
NodeTypeel tipo de nodo que manejará el árbol. Puede ser de tipo RandNode o RandNodeVtl 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.

Documentación del constructor y destructor

template<template< typename > class NodeType, typename Key, class Compare>
Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::Gen_Rand_Tree ( unsigned int  seed,
Compare &&  __cmp 
)
inline

Constructor; el generador de números aleatorios es instanciado para el mersen twister.

Documentación de las funciones miembro

template<template< typename > class NodeType, typename Key, class Compare>
std::pair<int,Node*> Aleph::Gen_Rand_Tree< 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 árbol aleatorio 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_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::find_position().

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

template<template< typename > class NodeType, typename Key, class Compare>
Compare& Aleph::Gen_Rand_Tree< 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_Rand_Tree< NodeType, Key, Compare >::getRoot ( )
inline

Obtiene un apuntador a la raíz del árbol binario de búsqueda aleatorizado.

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

Inserción en un árbol binario de búsqueda aleatorizado.

insert(p) inserta el nodo p en el árbol binario de búsqueda aleatorizado this.

Parámetros
[in]pel nodo a insertar.
Devuelve
el puntero al nodo p si la clave de p no está contenida en el árbol aleatorizado; NULL de lo contrario.
template<template< typename > class NodeType, typename Key, class Compare>
Node* Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert_dup ( Node *  p)
inline

Inserción en un árbol binario de búsqueda aleatorizado con posibilidad de duplicación.

insert(p) inserta el nodo p en el árbol binario de búsqueda aleatorizado this.

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

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

position(key) busca en el árbol aleatorio 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< typename > class NodeType, typename Key, class Compare>
Node* Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_remove ( Node *&  root,
const Key &  key 
)
inline

Eliminación aleatorizada en un árbol binario con rangos.

random_remove(root, key) busca en el árbol binario con rangos la clave key y, en caso de encontrar un nodo que contenga esa clave, efectúa una eliminación aleatorizada a través de Gen_Rand_Tree::random_join_exclusive() de los subárboles del nodo eliminado. El árbol binario de búsqueda resultante siempre es aleatorio en el sentido en que es equivalente al producido por una secuencia de inserción aleatoria.

La rutina puede ser utilizada por cualquier clase de árbol binario de búsqueda con rangos derivada de BinNodeXt. Su presencia dentro de la clase Gen_Rand_Tree obedece a la disponibilidad del generador de números aleatorios.

Parámetros
[in,out]rootraíz del árbol binario de búsqueda con rangos.
[in]keyclave a eliminar.
Devuelve
un puntero al nodo eliminado si la clave key se encuentra en el árbol binario de búsqueda con rangos; Node::NullPtr de lo contrario.
Ver también
Gen_Rand_Tree::random_join_exclusive() BinNodeXt

Referenciado por Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::random_remove() y Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::remove().

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

template<template< typename > class NodeType, typename Key, class Compare>
Node* Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove ( const Key &  key)
inline

Elimina una clave de un árbol binario de búsqueda aleatorizado.

remove(key) busca en el árbol binario de búsqueda aleatorizado la clave key y, en caso de encontrar un nodo que contenga esa clave, efectúa su eliminación aleatorizada.

Parámetros
[in]keyclave a eliminar.
Devuelve
un puntero al nodo eliminado si la clave key se encuentra en el árbol binario de búsqueda con rangos; NULL de lo contrario.
template<template< typename > class NodeType, typename Key, class Compare>
Node* Aleph::Gen_Rand_Tree< 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 a p 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>
Node* Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::select ( const size_t &  i) const
inline

Retorna el nodo cuya posición infija en el árbol es i.

select(i) retorna el nodo del árbol 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< typename > class NodeType, typename Key, class Compare>
void Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::swap ( Gen_Rand_Tree< 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