Referencia de la plantilla de la Clase Aleph::BinTree_Operation< Node, Cmp >

#include <tpl_binTreeOps.H>

Diagrama de herencias de Aleph::BinTree_Operation< Node, Cmp >

Tipos públicos
typedef Node::key_type	Key
	El tipo de clave de búsqueda.
typedef Node::key_type	key_type
	El tipo de clave de búsqueda.

Métodos públicos
Cmp &	key_comp ()
	Retorna una referencia al criterio de comparación.
Cmp &	get_compare ()
	BinTree_Operation (Cmp &__cmp)
	BinTree_Operation (Cmp &&__cmp=Cmp())
Node *	search (Node *root, const Key &key)
Node *	search_parent (Node *root, const Key &key, Node *&parent)
Node *	search_rank_parent (Node *root, const Key &key)
Node *	insert (Node *&root, Node *p)
Node *	insert_dup (Node *&root, Node *p)
Node *	search_or_insert (Node *&r, Node *p)
bool	split_key_rec (Node *root, const Key &key, Node *&ts, Node *&tg)
void	split_key_dup_rec (Node *root, const typename Node::key_type &key, Node *&ts, Node *&tg)
Node *	remove (Node *&root, const Key &key)
Node *	insert_root (Node *&root, Node *p)
Node *	insert_dup_root (Node *&root, Node *p)
Node *	join_preorder (Node *t1, Node *t2, Node *&dup)
Node *	join (Node *t1, Node *t2, Node *&dup)
void	split_key (Node *root, const Key &key, Node *&l, Node *&r)
Node *	insert_root_rec (Node *root, Node *p)
Node *	search_or_insert_root_rec (Node *root, Node *p)

Atributos protegidos
Cmp &	cmp

Descripción detallada

template<class Node, class Cmp = Aleph::less<typename Node::key_type>>
class Aleph::BinTree_Operation< Node, Cmp >

Operaciones básica y generales sobre árboles binarios de búsqueda.

La idea de esta clase en englobar eficientemente las diversas operaciones que se pueden efectuar sobre un árbol binario de búsqueda.

La clase maneja dos parámetros tipo:

1. Node: el tipo de nodo binario. Debe ser basado sobre BinNode.
2. Cmp: el criterio de comparación entre las claves.

Ver también

BinNode

Documentación de las funciones miembro

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Cmp& Aleph::BinTree_Operation< Node, Cmp >::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<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::insert ( Node *&  root, Node *  p  )

inline

Inserta un nodo en un árbol binario de búsqueda por substitución de un nodo externo.

insert(root, p) inserta el nodo p en el árbol binario de búsqueda cuya raíz es root según el criterio de comparación Compare()().

Parámetros

[in,out]	root	la raíz del árbol binario de búsqueda.
[in]	p	el nodo a insertar.

Devuelve

la dirección del nodo insertado (p) si la clave de p no está contenida dentro del árbol; Node::NullPtr de lo contrario.

Hace referencia a KEY, LLINK y RLINK.

Referenciado por Aleph::BinTree_Operation< Node, Cmp >::join() y Aleph::BinTree_Operation< Node, Cmp >::join_preorder().

Gráfico de llamadas a esta función:

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::insert_dup ( Node *&  root, Node *  p  )

inline

Inserta un nodo en un árbol binario de búsqueda por substitución de un nodo externo.

insert_dup(root, p) inserta el nodo p en el árbol binario de búsqueda cuya raíz es root según el criterio de comparación Compare()().

Se permiten claves repetidas.

Parámetros

[in,out]	root	la raíz del árbol binario de búsqueda.
[in]	p	el nodo a insertar.

Devuelve

la dirección del nodo insertado (p) si la clave de p no está contenida dentro del árbol; Node::NullPtr de lo contrario.

Hace referencia a KEY, LLINK y RLINK.

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::insert_dup_root ( Node *&  root, Node *  p  )

inline

Inserta un nodo con posibilidad de duplicación como raíz en un árbol binario de búsqueda mediante el algoritmo de partición.

insert_dup_root(root,p) inserta el árbol binario de búsqueda con raíz root el nodo p. Luego de la operación, p deviene raíz del árbol binario de búsqueda.

Las claves iguales a KEY(p) quedan a su izquierda.

La rutina particiona root en dos árboles según la clave contenida en p y luego adjunta las particiones a la rama izquierda y derecha de p.

Parámetros

[in,out]	root	raíz del árbol binario de búsqueda. Luego de la operación root adquiere el valor del parámetro p.
[in]	p	nodo a insertar como raíz.

Devuelve

puntero al nodo insertado (que es la nueva raíz) si la clave de p no está contenida dentro del árbol binario de búsqueda; Node::NullPtr de lo contrario.

Hace referencia a KEY, LLINK, RLINK y Aleph::BinTree_Operation< Node, Cmp >::split_key_dup_rec().

Gráfico de llamadas para esta función:

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::insert_root ( Node *&  root, Node *  p  )

inline

Inserta un nodo como raíz en un árbol binario de búsqueda mediante el algoritmo de partición.

insert_root(root,p) inserta el árbol binario de búsqueda con raíz root el nodo p. Luego de la operación, p deviene raíz del árbol binario de búsqueda.

La rutina particiona root en dos árboles según la clave contenida en p y luego adjunta las particiones a la rama izquierda y derecha de p.

Parámetros

[in,out]	root	raíz del árbol binario de búsqueda. Luego de la operación root adquiere el valor del parámetro p.
[in]	p	nodo a insertar como raíz.

Devuelve

puntero al nodo insertado (que es la nueva raíz) si la clave de p no está contenida dentro del árbol binario de búsqueda; Node::NullPtr de lo contrario.

Hace referencia a KEY, LLINK, RLINK y Aleph::BinTree_Operation< Node, Cmp >::split_key_rec().

Referenciado por Aleph::BinTree_Operation< Node, Cmp >::join().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::insert_root_rec ( Node *  root, Node *  p  )

inline

Inserta un nodo como raíz en un árbol binario de búsqueda mediante retroceso recursivo y rotaciones hasta la raíz.

insert_root_rec(root,p) inserta el árbol binario de búsqueda con raíz root el nodo p. Luego de la operación, p deviene raíz del árbol binario de búsqueda.

La rutina primero inserta p según la inserción clásica, luego rota p hasta que éste devenga la raíz.

Parámetros

[in]	root	raíz del árbol binario de búsqueda.
[in]	p	nodo a insertar como raíz.

Devuelve

puntero al nodo insertado (que es la nueva raíz) si la clave de p no está contenida dentro del árbol binario de búsqueda; Node::NullPtr de lo contrario.

Hace referencia a KEY, LLINK, RLINK, Aleph::rotate_to_left() y Aleph::rotate_to_right().

Gráfico de llamadas para esta función:

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::join ( Node *  t1, Node *  t2, Node *&  dup  )

inline

Unión de dos árboles binarios de búsqueda.

join(t1,t2,dup) construye un árbol binario de búsqueda correspondiente a la unión de t1 con t2. Las claves duplicadas se inserta, en dup.

Parámetros

[in]	t1	árbol binario de búsqueda.
[in]	t2	árbol binario de búsqueda.
[out]	dup	árbol binario de búsqueda con las claves duplicadas de t2.

Devuelve

puntero a la raíz del árbol binario de búsqueda resultante de la unión de t1 y t2.

Ver también

join_preorder()

Nota

Luego de las llamadas los árboles t1 y t2 devienen vacíos; sin embargo los valores de t1 y t2 no se modifican.

Hace referencia a Aleph::BinTree_Operation< Node, Cmp >::insert(), Aleph::BinTree_Operation< Node, Cmp >::insert_root(), KEY, LLINK y RLINK.

Gráfico de llamadas para esta función:

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::join_preorder ( Node *  t1, Node *  t2, Node *&  dup  )

inline

Unión de dos árboles binarios de búsqueda según algoritmo prefijo.

join_preorder(t1,t2,dup) recorre el prefijo el árbol t2. Cada clave de t2 se inserta en t1. Si la clave está duplicada, entonces se inserta en dup.

Parámetros

[in]	t1	árbol binario de búsqueda.
[in]	t2	árbol binario de búsqueda.
[out]	dup	árbol binario de búsqueda con las claves duplicadas de t2.

Devuelve

puntero a la raíz del árbol binario de búsqueda resultante de la unión de t1 y t2.

Ver también

join()

Nota

Luego de las llamadas los árboles t1 y t2 devienen vacíos; sin embargo los valores de t1 y t2 no se modifican.

Hace referencia a Aleph::BinTree_Operation< Node, Cmp >::insert(), LLINK y RLINK.

Gráfico de llamadas para esta función:

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::remove ( Node *&  root, const Key &  key  )

inline

Elimina una clave de un árbol binario de búsqueda mediante la unión exclusiva.

remove_from_search_binary_tree(root,key) busca en el árbol binario de búsqueda con raíz 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,out]	root	raíz del árbol binario de búsqueda.
[in]	key	clave del nodo a eliminar.

Devuelve

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

Ver también

join_exclusive()

Hace referencia a Aleph::join_exclusive(), KEY, LLINK y RLINK.

Gráfico de llamadas para esta función:

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::search ( Node *  root, const Key &  key  )

inline

Busca la clave key en el árbol cuya raíz es root. Retorna puntero al nodo si la encuentra; Node::NullPtr de lo contrario

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::search_or_insert ( Node *&  r, Node *  p  )

inline

Busca una clave en un árbol binario de búsqueda y la inserta en caso de no encontrarla.

search_or_insert(root, p) busca la clave KEY(p) árbol binario de búsqueda cuya raíz es root según el criterio de comparación Compare()(). Si la clave se encuentra, entonces se retorna un puntero al nodo que la alberga; de lo contrario, el nodo p es insertado en el árbol y se retorna p.

Parámetros

[in,out]	r	la raíz del árbol binario de búsqueda.
[in]	p	el nodo a buscar o insertar.

Devuelve

la dirección del nodo que contiene a KEY(p) si su clave ya está en el árbol o p si la clave no se encuentra, en cuyo caso se inserta.

Hace referencia a KEY, LLINK y RLINK.

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::search_or_insert_root_rec ( Node *  root, 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_root_rec(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]	r	la raíz del árbol.
[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).

Hace referencia a KEY, LLINK, RLINK, Aleph::rotate_to_left() y Aleph::rotate_to_right().

Gráfico de llamadas para esta función:

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::search_parent ( Node *  root, const Key &  key, Node *&  parent  )

inline

Búsqueda de clave en árbol binario de búsqueda con determinación del padre.

search_parent(root,key,parent) busca la clave key en el árbol binario de búsqueda cuya raíz es root y determina, además del nodo contentivo de la clave, el nodo padre.

Parámetros

[in]	root	la raíz del árbol binario de búsqueda donde realizar la búsqueda.
[in]	key	la clave de búsqueda.
[out]	parent	puntero al nodo padre del que contiene la clave (si fue encontrada).

Devuelve

puntero a nodo contentivo de la clave key si ésta se encuentra en el árbol binario de búsqueda; Node::NullPtr de lo contrario.

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

Node* Aleph::BinTree_Operation< Node, Cmp >::search_rank_parent ( Node *  root, const Key &  key  )

inline

Búsqueda fallida de nodo y determinación del padre.

search_rank_parent(root,key) busca en el árbol binario búsqueda cuya raíz es root la clave key. Si la clave se encuentra en el árbol binario, entonces retorna el nodo contentivo de la clave; de lo contrario, se retorna el nodo que sería padre de la clave si ésta fuese insertada en el árbol binario de búsqueda.

Parámetros

[in]	root	raíz del árbol binario de búsqueda.
[in]	key	clave a buscar.

Devuelve

puntero a nodo contentivo de la clave si ésta se encuentra en el árbol binario; de lo contrario, se retorna un puntero al nodo que sería padre de key si esta clave fuese insertada en el árbol binario de búsqueda.

Nota

No se verifica si el árbol está vacío.

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

void Aleph::BinTree_Operation< Node, Cmp >::split_key ( Node *  root, const Key &  key, Node *&  l, Node *&  r  )

inline

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

split_key(root,key,l,r) particiona iterativamente, según la clave key, un árbol binario de búsqueda 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.

La partición iterativa es más rápida que la recursiva.

Parámetros

[in,out]	root	puntero a la raíz del árbol binario a particionar.
[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 realizada exitosamente. De lo contrario, si key se encuentra dentro del árbol, el árbol no se particiona y el resultado es false.

Nota

A diferencia de split_key_rec() esta rutina incluye la clave de partición en caso de que ésta ya se encuentre dentro del árbol binario.

Hace referencia a KEY, LLINK y RLINK.

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

void Aleph::BinTree_Operation< Node, Cmp >::split_key_dup_rec ( Node *  root, const typename Node::key_type &  key, Node *&  ts, Node *&  tg  )

inline

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

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

Con este enfoque, el recorrido infijo del árbol estará ordenado por las claves y las duplicidades por orden de inserción.

Parámetros

[in,out]	root	puntero a la raíz del árbol binario a particionar.
[in]	key	clave de partición.
[out]	ts	árbol con las claves menores que key.
[out]	tg	árbol con las claves mayores que key.

Hace referencia a KEY, LLINK y RLINK.

Referenciado por Aleph::BinTree_Operation< Node, Cmp >::insert_dup_root().

Gráfico de llamadas a esta función:

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>

bool Aleph::BinTree_Operation< Node, Cmp >::split_key_rec ( Node *  root, const Key &  key, Node *&  ts, Node *&  tg  )

inline

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

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

Parámetros

[in,out]	root	puntero a la raíz del árbol binario a particionar.
[in]	key	clave de partición.
[out]	ts	árbol con las claves menores que key.
[out]	tg	árbol con las claves mayores que key.

Devuelve

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

Hace referencia a KEY, LLINK y RLINK.

Referenciado por Aleph::BinTree_Operation< Node, Cmp >::insert_root().

Gráfico de llamadas a esta función:

---

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

• tpl_binTreeOps.H