Aleph::Gen_Rand_Tree

Referencia de la plantilla de la Clase Gen_Rand_Tree
[Árboles con raíz]

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

Diagrama de herencias de Gen_Rand_Tree

Inheritance graph
[leyenda]

Lista de todos los miembros.

Tipos públicos

typedef NodeType< Key > Node
 Tipo de nodo binario.

Métodos públicos

 Gen_Rand_Tree ()
 Constructor; el generador de números aleatorios es instanciado para el mersen twister.
Node *& getRoot ()
 Obtiene un apuntador a la raíz del árbol binario de búsqueda aleatorizado.
gsl_rng * gsl_rng_object ()
 Obtiene un puntero al objeto gsl_rng generador de números aleatorios.
Node * insert (Node *p)
 Inserción en un árbol binario de búsqueda aleatorizado.
Node * random_insert (Node *root, Node *node)
 Inserción aleatorizada en un árbol binario de búsqueda con rangos.
Node * random_join_exclusive (Node *tl, Node *tr)
 Unión exclusiva aleatoria de dos árboles binarios de búsqueda, exclusivos, con rangos.
Node * random_remove (Node *&root, const Key &key)
 Eliminación aleatorizada en un árbol binario con rangos.
Node * remove (const Key &key)
 Elimina una clave de un árbol binario de búsqueda aleatorizado.
Node * search (const Key &key)
 Busca la clave key en el árbol binario de búsqueda aleatorizado.
virtual ~Gen_Rand_Tree ()
 Destructor (libera generador de números aleatorios.

Descripción detallada

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

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:
NodeType el tipo de nodo que manejará el árbol. Puede ser de tipo RandNode o RandNodeVtl según se desee o no tener destructores virtuales.
Key el tipo de clave a guardar en los nodos.
Compare el criterio de comparación entre las claves de los nodos.

Definición en la línea 78 del archivo tpl_rand_tree.H.

Documentación de las funciones miembro

Node* insert ( Node *  p  )  [inline]

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

Parámetros:
[in] p el 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.

Definición en la línea 186 del archivo tpl_rand_tree.H.

Node* random_insert ( Node *  root,
Node *  node 
) [inline]

random_insert(root,node) inserta aleatoriamente el nodo node en el árbol binario de búsqueda con rangos root independientemente del valor de clave que contenga node. 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 pertenece a la clase Gen_Rand_Tree, pero puede usarse en general para cualquier clase de árbol binario de búsqueda con rango derivado de BinNodeXt. Se circunscribe dentro de Gen_Rand_Tree por el generador de números aleatorios.

Parámetros:
[in] root la raíz del árbol binario de búsqueda con rangos.
[in] node el nodo a insertar.
Devuelve:
si la clave de node no se encuentra en el árbol binario, entonces se retorna la raíz del árbol binario de búsqueda con rangos que contiene el nuevo nodo; de lo contrario, la rutina retorna Node::NullPtr.
Ver también:
BinNodeXt

Definición en la línea 139 del archivo tpl_rand_tree.H.

Referenciado por Gen_Rand_Tree< Aleph::RandNodeVtl< Key >, Key, Compare >::insert(), y Gen_Rand_Tree< Aleph::RandNodeVtl< Key >, Key, Compare >::random_insert().

Node* random_remove ( Node *&  root,
const Key &  key 
) [inline]

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] root raíz del árbol binario de búsqueda con rangos.
[in] key clave 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

Definición en la línea 278 del archivo tpl_rand_tree.H.

Referenciado por Gen_Rand_Tree< Aleph::RandNodeVtl< Key >, Key, Compare >::random_remove(), y Gen_Rand_Tree< Aleph::RandNodeVtl< Key >, Key, Compare >::remove().

Node* remove ( const Key &  key  )  [inline]

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] key clave 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.

Definición en la línea 322 del archivo tpl_rand_tree.H.

La documentación para esta clase fue generada a partir del siguiente fichero:
Leandro R. León