Referencia de la plantilla de la Clase Treap
[Árboles con raíz]
Árbol binario de búsqueda aleatorizado genérico de tipo treap con nodos sin destructor virtual.
Más...
Diagrama de herencias de Treap
Diagrama de colaboración para Treap:
Tipos públicos | |
| typedef NodeType< Key > | Node |
| Tipo de nodo del treap. | |
Métodos públicos | |
| Node *& | getRoot () |
| Retorna la raíz del treap. | |
| gsl_rng * | gsl_rng_object () |
| Obtiene un puntero al objeto gsl_rng generador de números aleatorios. | |
| Node * | insert (Node *p) |
| Insertar el nodo p en un treap. | |
| Node * | remove (const Key &key) |
| Elimina la clave key del treap. | |
| Node * | search (const Key &key) |
| Busca la clave key en el treap. | |
Descripción detallada
template<typename Key, class Compare = Aleph::less<Key>>
class Aleph::Treap< Key, Compare >
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 
, 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:
-
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_Vtl Treap_Rk Treap_Rk_Vtl
Definición en la línea 272 del archivo tpl_treap.H.
Documentación de las funciones miembro
insert(p) inserta el nodo p en el treap 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 183 del archivo tpl_treap.H.
| Node* remove | ( | const Key & | key | ) | [inline, inherited] |
remove(key) busca la clave key en el treap 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 208 del archivo tpl_treap.H.
La documentación para esta clase fue generada a partir del siguiente fichero: