Referencia de la plantilla de la Clase Aleph::GenBinTree< NodeType, Key, Compare >

#include <tpl_binTree.H>

Tipos públicos
typedef NodeType< Key >	Node

Métodos públicos
void	swap (GenBinTree &tree)
Compare &	key_comp ()
	Retorna una referencia al criterio de comparación.
Compare &	get_compare ()
	GenBinTree (Compare &__cmp)
	GenBinTree (Compare &&__cmp)
Node *	search (const Key &key)
bool	verify ()
Node *&	getRoot ()
	Retorna la raíz del árbol binario de búsqueda.
bool	verifyBin ()
Node *	insert (Node *p)
Node *	insert_dup (Node *p)
Node *	search_or_insert (Node *p)
bool	split (const Key &key, GenBinTree &l, GenBinTree &r)
bool	split_dup (const Key &key, GenBinTree &l, GenBinTree &r)
Node *	remove (const Key &key)
void	join (GenBinTree &tree, GenBinTree &dup)

Descripción detallada

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

Árbol binario de búsqueda.

La clase GenBinTree instrumenta un árbol binario de búsqueda clásico.

Esta clase no está destinada a uso público. Su fin es proveer la funcionalidad básica a las clases BinTree, BinHeapVtl y DynBinHeap.

Parámetros

NodeType	el tipo de nodo que usa el árbol binario; éste será con o sin destructor virtual.
Key	la clave que guarda cada nodo.
Compare	el criterio de comparación entre las claves de los nodos.

Ver también

BinTree BinTreeVtl DynBinTree

Documentación de las funciones miembro

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

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

inline

Inserta p en el árbol binario de búsqueda.

Inserta p en el árbol binario de búsqueda this.

Parámetros

[in]

p

el nodo a insertar.

Devuelve

puntero al nodo insertado si la clave de p no está contenida dentro del árbol; NULL de lo contrario.

Referenciado por Aleph::GenBinTree< BinNodeVtl, Key, Compare >::insert().

Gráfico de llamadas a esta función:

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

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

inline

Inserta p duplicadamente en el árbol binario de búsqueda.

Inserta p en el árbol binario de búsqueda this.

Parámetros

[in]

p

el nodo a insertar.

Devuelve

puntero al nodo insertado si la clave de p no está contenida dentro del árbol; NULL de lo contrario.

Referenciado por Aleph::GenBinTree< BinNodeVtl, Key, Compare >::insert_dup().

Gráfico de llamadas a esta función:

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

void Aleph::GenBinTree< NodeType, Key, Compare >::join ( GenBinTree< NodeType, Key, Compare > &  tree, GenBinTree< NodeType, Key, Compare > &  dup  )

inline

Unión de this con tree.

join(tree,dup) efectúa la unión de los árboles binarios de búsqueda this y tree. Las claves duplicadas de tree son colocadas en dup.

Parámetros

[in,out]	tree	árbol a unir con this. Deviene vacío luego de la llamada.
[out]	dup	árbol binario de búsqueda donde colocar las claves repetidas.

Referenciado por Aleph::GenBinTree< BinNodeVtl, Key, Compare >::join().

Gráfico de llamadas a esta función:

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

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

inline

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

busca en el árbol binario de búsqueda this root un nodo que contenga la clave key. Si el nodo es encontrado, entonces éste se substituye en el árbol binario general por el resultado de la unión exclusiva de los subárboles del nodo eliminado.

Parámetros

[in]

key

clave del nodo a eliminar.

Devuelve

puntero al nodo eliminado si la clave se encuentra en el árbol; NULL de lo contrario.

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

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

inline

Busca una clave en un árbol binario de búsqueda.

search(key) busca en el árbol binario de búsqueda this por una ocurrencia de la clave key.

Parámetros

[in]

key

la clave a buscar.

Devuelve

un puntero al nodo contentivo de la clave key si ésta se encuentra dentro del árbol; NULL de lo contrario.

Referenciado por Aleph::GenBinTree< BinNodeVtl, Key, Compare >::search().

Gráfico de llamadas a esta función:

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

Node* Aleph::GenBinTree< 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 retorna 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).

Referenciado por Aleph::GenBinTree< BinNodeVtl, Key, Compare >::search_or_insert().

Gráfico de llamadas a esta función:

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

bool Aleph::GenBinTree< NodeType, Key, Compare >::split ( const Key &  key, GenBinTree< NodeType, Key, Compare > &  l, GenBinTree< NodeType, Key, Compare > &  r  )

inline

Particiona el árbol binario de búsqueda según una clave.

split(key,l,r) particiona, según la clave key, el árbol binario de búsqueda this en dos árboles l y r. Luego de la operación el árbol, el árbol root deviene vacío, l contiene todas las claves menores que key y r las mayores.

Parámetros

[in]	key	clave de partición.
[out]	l	árbol con las claves menores que key.
[out]	r	árbol con las claves mayores que key.

Devuelve

true si key no está dentro del árbol binario; en cuyo caso la partición fue hecha exitosamente. De lo contrario, si key se encuentra dentro del árbol, el árbol no se particiona y el resultado es false.

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

bool Aleph::GenBinTree< NodeType, Key, Compare >::split_dup ( const Key &  key, GenBinTree< NodeType, Key, Compare > &  l, GenBinTree< NodeType, Key, Compare > &  r  )

inline

Particiona el árbol binario de búsqueda según una clave que puede estar presente en el árbol.

split_dup(key,l,r) particiona, según la clave key, el árbol binario de búsqueda this en dos árboles l y r. Luego de la operación el árbol, el árbol root deviene vacío, l contiene todas las claves menores que key y r las mayores o iguales.

Parámetros

[in]	key	clave de partición.
[out]	l	árbol con las claves menores que key.
[out]	r	árbol con las claves mayores que key.

---

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

• tpl_binTree.H