#include <tpl_binTreeOps.H>

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

Diagrama de colaboración para Aleph::BinTreeXt_Operation< Node, Cmp >:

Tipos públicos
typedef Node::key_type	Key

Tipos públicos heredados desde Aleph::BinTree_Operation< Node, Cmp >
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
	BinTreeXt_Operation (Cmp &&cmp=Cmp())

	BinTreeXt_Operation (Cmp &cmp)

int	inorder_position (Node r, const Key &key, Node &p)

int	find_position (Node r, const Key &key, Node &p)

bool	split_key_rec (Node root, const Key &key, Node &l, Node *&r)

void	split_key_dup_rec (Node root, const Key &key, Node &l, Node *&r)

Node *	insert_root (Node &root, Node p)

Node *	insert_dup_root (Node &root, Node p)

Métodos públicos heredados desde Aleph::BinTree_Operation< Node, Cmp >
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)

Otros miembros heredados
Atributos protegidos heredados desde Aleph::BinTree_Operation< Node, Cmp >
Cmp &	cmp

Descripción detallada

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

Operaciones básicas y generales sobre árboles binarios de búsqueda con rangos.

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

La clase maneja dos parámetros tipo:

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

Ver también: BinNodeXt

Documentación de las funciones miembro

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

int Aleph::BinTreeXt_Operation< Node, Cmp >::find_position	(	Node *	r,
		const Key &	key,
		Node *&	p
	)

inline

Determina la posición infija de una clave en un árbol con rangos.

find_position(r,key,node) busca key en el árbol binario de búsqueda con rangos cuya raíz es r. Si la clave es encontrada, entonces la rutina retorna la posición del nodo que alberga la clave y almacena un puntero al nodo en el parámetro node. De lo contrario, la rutina retorna la posición en la cual se encontraría key si éste se insertase en el árbol. En este último caso, el parámetro p contiene un nodo continuo a key en caso de que key no sea mayor que la clave máxima contenida en el árbol.

Si key no se encuentra en el árbol, entonces se pueden distinguir tres casos:

Si key es menor que la mínima clave del árbol, entonces el valor de retorno es -1 y p es el nodo contentivo de la clave mínima.
Si key es mayor que la máxima clave del árbol, entonces el valor de retorno es COUNT(r) (núemro de nodos del árbol) y p es el nodo contentivo de la clave máxima.
En cualquier otro caso, el valor de retorno es la posición que tendría la clave key en árbol y el nodo p es una clave inmediatamente adyancente a key. Note que p puede tener una clave menor o mayor, pero se garantiza que es inmediatamente continua a key.

La rutina emplea el criterio de comparación expresado por la clase Compare.

Parámetros

[in]	r	raíz del árbol binario de búsqueda con rangos.
[in]	key	clave a buscar y determinar posición infija
[out]	p	puntero al nodo contentivo de la clave key (si fue encontrada) o de la clave contenida en el árbol que sea mayor que key.

Devuelve: posición infija del nodo contentivo de la clave key si ésta se encuentra en el árbol; de lo contrario, se retorna la posición donde se encontraría key de insertarse en el árbol.

Hace referencia a COUNT, KEY, LLINK y RLINK.

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

int Aleph::BinTreeXt_Operation< Node, Cmp >::inorder_position	(	Node *	r,
		const Key &	key,
		Node *&	p
	)

inline

Determina la posición infija de una clave en un árbol con rangos.

inorder_position(r,key,node) busca key en el árbol binario de búsqueda con rangos cuya raíz es r. Si la clave es encontrada, entonces la rutina retorna la posición del nodo que alberga la clave y almacena un puntero al nodo en el parámetro node.

La rutina emplea el criterio de comparación expresado por la clase Compare.

Parámetros

[in]	r	raíz del árbol binario de búsqueda con rangos.
[in]	key	clave a buscar y determinar posición infija
[out]	p	puntero al nodo contentivo de la clave key (si fue encontrada).

Devuelve: posición infija del nodo contentivo de la clave key si ésta se encuentra en el árbol; de lo contrario, se retorna -1.

Hace referencia a COUNT, KEY, LLINK y RLINK.

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

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

inline

Inserta un nodo como raíz en un árbol binario de búsqueda con rangos y con posibilidad de duplicación.

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

Parámetros

[in,out]	root	raíz del árbol binario de búsqueda con rangos. 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)

Hace referencia a COUNT, KEY, LLINK, RLINK y Aleph::BinTreeXt_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::BinTreeXt_Operation< Node, Cmp >::insert_root	(	Node *&	root,
		Node *	p
	)

inline

Inserta un nodo como raíz en un árbol binario de búsqueda con rangos.

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

Parámetros

[in,out]	root	raíz del árbol binario de búsqueda con rangos. 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 COUNT, KEY, LLINK, RLINK y Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_rec().

Gráfico de llamadas para esta función:

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

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

inline

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

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

Parámetros

[in,out]	root	puntero a la raíz del árbol binario con rangos que se desea particionar.
[in]	key	clave de partición.
[out]	l	árbol binario de búsqueda con rangos con las claves menores que key.
[out]	r	árbol binario de búsqueda con rangos con las claves mayores que key.

Hace referencia a COUNT, KEY, LLINK y RLINK.

Referenciado por Aleph::BinTreeXt_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::BinTreeXt_Operation< Node, Cmp >::split_key_rec	(	Node *	root,
		const Key &	key,
		Node *&	l,
		Node *&	r
	)

inline

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

split_key_rec(root,key,l,r) particiona, según la clave key, un árbol binario de búsqueda con rangos 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 con rangos que se desea particionar.
[in]	key	clave de partición.
[out]	l	árbol binario de búsqueda con rangos con las claves menores que key.
[out]	r	árbol binario de búsqueda con rangos 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 COUNT, KEY, LLINK y RLINK.

Referenciado por Aleph::BinTreeXt_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

Tipos públicos

Métodos públicos

Otros miembros heredados

Descripción detallada

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

Documentación de las funciones miembro

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