#include <tpl_avl.H>

Tipos públicos
typedef NodeType< Key >	Node

typedef Key	key_type
	El tipo de clave que contiene el nodo.

Métodos públicos
Compare &	key_comp ()
	Retorna una referencia al criterio de comparación.

Compare &	get_compare ()

	Gen_Avl_Tree (Compare &&__cmp)
	Instancia un árbol AVL genérico.

	Gen_Avl_Tree (Compare &__cmp)

void	swap (Gen_Avl_Tree &tree)

virtual	~Gen_Avl_Tree ()
	Destruye un árbol AVL genérico.

Node *&	getRoot ()
	Obtiene un puntero a la raíz del árbol.

Node *	search (const Key &key) const

Node *	insert (Node *p)

Node *	search_or_insert (Node *p)

Node *	insert_dup (Node *p)

Node *	remove (const Key &key)

bool	verify ()

Descripción detallada

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

Árbol binario de búsqueda AVL.

Un árbol binario de búsqueda AVL es un árbol binario de búsqueda cuya altura está acotada a $O(\lg n)$ y sus operaciones de modificación acotadas en tiempo por $O(\lg n)$ nodos inspeccionados.

Esta clase es genérica en el sentido de que maneja nodos con o sin destructor virtual. No está destinada a usarse normalmente. En su lugar, use las clases derivadas Avl_Tree o Avl_Tree_Vtl.

Parámetros

NodeType	el tipo de nodo entre AvlNode y AvlNodeVtl (no están documentados).
Key	el tipo de clave que albergan los nodos del árbol.
Compare	clase de comparación entre las claves.

Ver también: Avl_Tree Avl_Tree_Vtl

Documentación de las funciones miembro

template<template< typename > class NodeType, typename Key, class Compare>

Compare& Aleph::Gen_Avl_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_Avl_Tree< NodeType, Key, Compare >::insert ( Node * p )

inline

Inserta el nodo p en el árbol binario de búsqueda AVL. Retorna p si árbol no contiene otro nodo con la misma clave de p; NULL, de lo contrario.

template<template< typename > class NodeType, typename Key, class Compare>

Node* Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert_dup ( Node * p )

inline

Inserta el nodo p en el árbol binario de búsqueda AVL con posibilidad de duplicación.

template<template< typename > class NodeType, typename Key, class Compare>

Node* Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove ( const Key & key )

inline

Elimina de un árbol AVL el nodo que contiene la clave key. Retorna el nodo eliminado si se encuentra la clave; NULL de lo contrario.

template<template< typename > class NodeType, typename Key, class Compare>

Node* Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search ( const Key & key ) const

inline

Busca la clave key en el árbol AVL. Retorna un puntero al nodo que contiene la clave buscada; NULL si la clave no se encuentra.

template<template< typename > class NodeType, typename Key, class Compare>

Node* Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_or_insert ( Node * p )

inline

Busca la clave de p en el árbol avl o lo inserta en caso de no encontrarse.

search_or_insert(p) busca en el árbol avl 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] p el 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_Avl_Tree< NodeType, Key, Compare >::swap ( Gen_Avl_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] tree el treap a intercambiar con this

La documentación para esta clase fue generada a partir del siguiente fichero:

tpl_avl.H

Tipos públicos

Métodos públicos

Descripción detallada

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

Documentación de las funciones miembro

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