Aleph::Treap_Rk

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

Árbol binario extendido de búsqueda aleatorizado genérico de tipo Treap con nodos sin destructor virtual. Más...

Diagrama de herencias de Treap_Rk

Inheritance graph
[leyenda]
Diagrama de colaboración para Treap_Rk:

Collaboration graph
[leyenda]

Lista de todos los miembros.

Tipos públicos

typedef NodeType< Key > Node
 El tipo de nodo interno.

Métodos públicos

Node *& getRoot ()
 Retorna la raíz del treap extendido.
Node * insert (Node *p)
 Insertar el nodo p en el treap extendido this.
size_t position (const Key &key)
 Retorna la posición infija (ordenada) de la clave key.
Node * remove (const size_t &beg, const size_t &end)
 Elimina del treap extendido todas las claves comprendidas entre la posición infija beg y end.
Node * remove (const Key &key)
 Elimina la clave key del treap extendido this.
Node * search (const Key &key)
 Busca la clave key en el treap extendido this.
Node * select (const size_t &i)
 Retorna el nodo cuya posición infija en el treap extendido es i.
size_t size () const
 Retorna la cantidad de nodos que contiene el treap.
void swap (Gen_Treap_Rk &tree)
 Intercambia todos los elementos del treap this con el treap tree en tiempo contante (y extremadamente rápido).

Descripción detallada

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

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:
Key el tipo de clave a guardar en los nodos.
Compare el 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

Definición en la línea 711 del archivo tpl_treapRk.H.

Documentación de las funciones miembro

Node* insert ( Node *  p  )  [inline, inherited]

insert(p) inserta el nodo p en el treap extendido this.

Parámetros:
[in] p el nodo a insertar.
Devuelve:
puntero al nodo recién insertado si su clave no estaba contenida en el treap; NULL de lo contrario.

Definición en la línea 242 del archivo tpl_treapRk.H.

size_t position ( const Key &  key  )  [inline, inherited]

position(key) busca en el treap extendido 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] key clave a buscar y a determinar posición infija.
Devuelve:
posición infija de la clave key dentro del conjunto ordenado.
Excepciones:
domain_error si la clave no está contenida en el treap extendido.

Definición en la línea 400 del archivo tpl_treapRk.H.

Node* remove ( const size_t &  beg,
const size_t &  end 
) [inline, inherited]

rmeove(beg,end) elimina del treap extendido this todas las claves entre las posiciones infijas beg y end. Se retorna un arbol que contiene las claves borradas.

Parámetros:
[in] beg posición infija donde comienza el rango a ser eliminado.
[in] end posición infija donde termina el rango a ser eliminado.
Devuelve:
un puntero a la raíz del treap extendido que contiene todas las claves eliminadas.
Excepciones:
range_error si el rango de posiciones infijas es inválido.

Definición en la línea 349 del archivo tpl_treapRk.H.

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

remove(key) busca la clave key en el treap extendido this y, de encontrarse la clave, elimina el nodo del treap.

Parámetros:
[in] key clave a eliminar.
Devuelve:
puntero al nodo recién eliminado si la clave se encuentra en el treap; NULL de lo contrario.

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

Node* select ( const size_t &  i  )  [inline, inherited]

select(i) retorna el nodo del treap extendido cuya posición infija es i.

Parámetros:
[in] i posición infija a seleccionar.
Devuelve:
puntero al nodo correspondiente a la posición infija i.
Excepciones:
out_of_range si i es mayor o igual que la cantidad de nodos que contiene el treap.

Definición en la línea 377 del archivo tpl_treapRk.H.

void swap ( Gen_Treap_Rk< NodeType, Key, Compare > &  tree  )  [inline, inherited]

Parámetros:
[in] tree el treap a intercambiar con this

Definición en la línea 170 del archivo tpl_treapRk.H.

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