Árboles con raíz

Diagrama de colaboración para Árboles con raíz:

Aleph maneja distintos tipos y funciones vinculados a los árboles con raíz. Más...

Clases
class	ArrayHeap
	Heap o cola de prioridad implementada con arreglos. Más...
class	Avl_Tree
	Árbol binario de búsqueda AVL con nodos sin destructor virtual. Más...
class	Avl_Tree_Vtl
	Árbol binario de búsqueda AVL con destructor virtual en sus nodos. Más...
class	BinHeap
	Heap de nodos sin destructor virtual. Más...
class	BinHeapVtl
	Heap de nodos con destructor virtual. Más...
class	BinNode
	Nodo binario básico. Más...
class	BinTree
	Árbol binario de búsqueda sin destructores virtuales en los nodos. Más...
class	BinTreeVtl
	Árbol binario de búsqueda con destructores virtuales en los nodos. Más...
class	DynBinHeap
	Heap dinámico de elementos de tipo genérico T con criterio de comparación Compare. Más...
class	DynMapAvlTree
	Mapeo dinámico implementado con árboles binario de búsqueda AVL. Más...
class	DynMapBinTree
	Mapeo dinámico implementado con árboles binario de búsqueda clásicos. Más...
class	DynMapRandTree
	Mapeo dinámico implementado con árboles binario de búsqueda aleatorizados. Más...
class	DynMapRbTree
	Mapeo dinámico implementado con árboles binario de búsqueda rojo-negro. Más...
class	DynMapSplayTree
	Mapeo dinámico implementado con árboles binario de búsqueda splay. Más...
class	DynMapTreap
	Mapeo dinámico implementado con árboles binario de búsqueda treaps. Más...
class	DynMapTree
	Mapeo genérico instrumentado con árboles binarios de búsqueda. Más...
class	DynSetAvlTree
	Conjunto dinámico implementado mediante árboles binarios de búsqueda AVL de tipo Avl_Tree<Key>. Más...
class	DynSetBinTree
	Conjunto dinámico implementado mediante árboles binarios de búsqueda de tipo BinTree<Key>. Más...
class	DynSetRandTree
	Conjunto dinámico implementado mediante árboles binarios de búsqueda aleatorios de tipo Rand_Tree<Key>. Más...
class	DynSetRbTree
	Conjunto dinámico implementado mediante árboles binarios de búsqueda aleatorios treaps de tipo Rb_Tree<Key>. Más...
class	DynSetSplayTree
	Conjunto dinámico implementado mediante árboles binarios de búsqueda splay de tipo Splay_Tree<Key>. Más...
class	DynSetTreap
	Conjunto dinámico implementado mediante árboles binarios de búsqueda aleatorios treaps de tipo Treap<Key>. Más...
class	DynSetTree
	Conjunto dinámico de elementos de tipo genérico T implementado mediante una clase de árboles binarios. Más...
class	Gen_Avl_Tree
	Árbol binario de búsqueda AVL. Más...
class	Gen_Rand_Tree
	Árbol binario de búsqueda aleatorizado genérico. Más...
class	Gen_Rb_Tree
	Árbol binario de búsqueda rojo-negro. Más...
class	Gen_Splay_Tree
	Árbol binario de búsqueda splay. Más...
class	Gen_Treap
	Árbol binario de búsqueda aleatorizado genérico tipo Treap. Más...
class	Gen_Treap_Rk
	Árbol binario extendido de búsqueda aleatorizado genérico de tipo Treap. Más...
class	Gen_Treap_Rk::Iterator
	Iterador sobre los nodos de un treap extendido. Más...
class	GenBinHeap
	Heap genérico de nodos. Más...
class	GenBinTree
	Árbol binario de búsqueda. Más...
class	Huffman_Decoder_Engine
	Decodificador de Huffman. Más...
class	Huffman_Encoder_Engine
	Codificador de Huffman. Más...
class	map
	Implementación Aleph del tipo estándar map<T> basada en árboles binarios de búsqueda con rangos. Más...
class	map::iterator
	Iterador sobre un mapeo. Más...
class	multiset
	Implementación Aleph del tipo estándar multiset<T> basada en árboles binarios de búsqueda con rangos. Más...
class	multiset::iterator
	Iterador sobre un multi-conjunto (multiset). Más...
class	priority_queue
	Implantación Aleph del contenedor estándar prority_queue<T>. Más...
class	Rand_Tree
	Árbol binario de búsqueda aleatorizado de nodos sin destructor virtual. Más...
class	Rand_Tree_Vtl
	Árbol binario de búsqueda aleatorizado de nodos con destructor virtual. Más...
struct	Rb_Tree
	Árbol binario de búsqueda rojo-negro con nodos sin destructor virtual. Más...
struct	Rb_Tree_Vtl
	Árbol binario de búsqueda rojo-negro con destructor virtual en sus nodos. Más...
class	set
	Implementación Aleph del tipo estándar set<T> basada en árboles binarios de búsqueda con rangos. Más...
class	set::iterator
	Iterador sobre un conjunto. Más...
struct	Splay_Tree
	Árbol binario de búsqueda splay con nodos sin destructor virtual. Más...
struct	Splay_Tree_Vtl
	Árbol binario de búsqueda splay sin destructor virtual en sus nodos. Más...
class	Treap
	Árbol binario de búsqueda aleatorizado genérico de tipo treap con nodos sin destructor virtual. Más...
class	Treap_Rk
	Árbol binario extendido de búsqueda aleatorizado genérico de tipo Treap con nodos sin destructor virtual. Más...
class	Treap_Rk_Vtl
	Árbol binario extendido de búsqueda aleatorizado genérico de tipo Treap con destructor virtual en sus nodos. Más...
class	Treap_Vtl
	Árbol binario de búsqueda aleatorizado genérico de tipo Treap con destructor virtual en sus nodos. Más...
class	Tree_Node
	Árboles m-rios genéricos. Más...
Definiciones
#define	COUNT(p)   ((p)->getCount())
	Retorna la cardinalidad del árbol con raíz p en un árbol con rangos.
#define	DECLARE_BINNODE(Name, height, Control_Data)
	Declara nodos binarios de nombre Name<Key>.
#define	DECLARE_BINNODE_SENTINEL(Name, height, Control_Data)
	Declara nodos binarios de nombre Name<Key> con nodos centinelas.
#define	KEY(p)   ((p)->get_key())
	Referencia modificable a la clave del nodo binario.
#define	LLINK(p)   ((p)->getL())
	Puntero al subárbol izquierdo.
#define	RLINK(p)   ((p)->getR())
	Puntero al subárbol derecho.
Funciones
template<class TNode, class BNode>
TNode *	bin_to_forest (BNode *broot)
	Convierte un árbol binario a su arborescencia equivalente.
	BinNode ()
	Constructor vacío.
template<class Node, typename Key>
Node *	build_optimal_tree (Key keys[], double p[], const int &n)
	Construye un árbol binario de búsqueda óptimo según frecuencias estimadas de búsqueda.
template<template< class > class Node, typename Key>
Node< Key > *	build_tree (DynArray< Key > &preorder, const int &l_p, const int &r_p, DynArray< Key > &inorder, const int &l_i, const int &r_i)
	Reconstruye un árbol binario a partir de sus recorridos prefijo e infijo.
template<class Node, class Compare>
bool	check_binary_search_tree (Node *node)
	Verifica consistencia de un árbol binario de búsqueda.
template<class Node>
size_t	compute_cardinality_rec (Node *node)
	Cuenta la cantidad de nodos de un árbol binario.
template<class Node>
size_t	compute_height (Node *root)
	Calcula la altura del árbol root.
template<class Node>
void	compute_nodes_in_level (Node *root, const int &level, DynDlist< Node * > &list)
	Calcula la cantidad de nodos que tiene un nivel.
template<class Node>
size_t	computeHeightRec (Node *node)
	Calcula la altura de un árbol binario.
template<class Node>
Node *	copyRec (Node *src_root) throw (std::exception, std::bad_alloc)
	Copia recursiva de un árbol binario.
template<class Node>
void	destroy_forest (Node *root)
	Destruye (libera memoria) la arborescencia cuya primer árbol es root.
template<class Node>
void	destroy_tree (Node *root)
	Destruye (libera memoria) el árbol cuya raíz es root.
template<class Node>
void	destroyRec (Node *root)
	Destrucción de un árbol binario.
template<class Node>
Node *	deway_search (Node *root, int path[], const size_t &size)
	Retorna un nodo de una arborescencia dado su número de Deway.
template<class Node>
Node *	find_max (Node *root)
	Encuentra el máximo elemento en un árbol binario de búsqueda.
template<class Node>
Node *	find_min (Node *root)
	Encuentra el mínimo elemento en un árbol binario de búsqueda.
template<class Node>
Node *	find_predecessor (Node *p, Node *&pp)
	Encuentra el nodo predecesor infijo de p.
template<class Node>
Node *	find_successor (Node *p, Node *&pp)
	Encuentra el nodo sucesor infijo de p.
template<class Node>
void	forest_postorder_traversal (Node *root, void(*visitFct)(Node *, int, int))
	Recorre en sufijo una arborescencia.
template<class Node>
void	forest_preorder_traversal (Node *root, void(*visitFct)(Node *, int, int))
	Recorre en prefijo una arborescencia.
template<class TNode, class BNode>
BNode *	forest_to_bin (TNode *root)
	Convierte una arborescencia a su árbol binario equivalente.
template<typename Node, class Write>
void	generate_forest (Node *root, std::ofstream &out=std::cout)
	Genera una entrada para el programa de dibujado de árboles ntrepic.
template<typename Node, class Write>
void	generate_tree (Node *root, std::ofstream &out, const int &tree_number=0)
	Genera una entrada para el programa de dibujado de árboles ntrepic.
template<class Node, class Compare>
size_t	inorder_position (Node *r, const typename Node::key_type &key, Node *&node)
	Determina la posición infija de una clave en un árbol con rangos.
template<class Node>
int	inOrderRec (Node *root, void(*visitFct)(Node *, int, int))
	Recorre recursivamente en infijo un árbol binario.
template<class Node>
size_t	inOrderStack (Node *node, void(*visitFct)(Node *, int, int))
	Recorre en infijo un árbol binario.
template<class Node>
void	inOrderThreaded (Node *root, void(*visitFct)(Node *))
	Recorre en infijo un árbol binario sin usar recursión o pila explícita.
template<class Node, class Compare>
Node *	insert_by_key_xt (Node *&r, Node *p)
	Inserta un nodo en un árbol binario de búsqueda con rangos por substitución de un nodo externo.
template<class Node>
void	insert_by_pos_xt (Node *&r, Node *p, const size_t &pos)
	Inserta un nodo en un árbol binario con rangos.
template<class Node, class Compare>
Node *	insert_in_binary_search_tree (Node *&root, Node *p)
	Inserta un nodo en un árbol binario de búsqueda por substitución de un nodo externo.
template<class Node, class Compare>
Node *	insert_root (Node *&root, Node *p)
	Inserta un nodo como raíz en un árbol binario de búsqueda mediante el algoritmo de partición.
template<class Node, class Key, class Compare>
Node *	insert_root_rec (Node *root, Node *p)
	Inserta un nodo como raíz en un árbol binario de búsqueda mediante retroceso recursivo y rotaciones hasta la raíz.
template<class Node, class Compare>
Node *	insert_root_xt (Node *&root, Node *p)
	Inserta un nodo como raíz en un árbol binario de búsqueda con rangos.
template<class Node>
size_t	internal_path_length (Node *p)
	Calcula la longitud del camino interno de un árbol binario.
template<class Node, class Compare>
Node *	join (Node *t1, Node *t2, Node *&dup)
	Unión de dos árboles binarios de búsqueda.
template<class Node>
Node *	join_exclusive (Node *&ts, Node *&tg)
	Unión exclusiva de dos árboles binarios de búsqueda.
template<class Node>
Node *	join_exclusive_xt (Node *&ts, Node *&tg)
	Unión exclusiva de dos árboles binarios de búsqueda con rangos.
template<class Node, class Compare>
Node *	join_preorder (Node *t1, Node *t2, Node *&dup)
	Unión de dos árboles binarios de búsqueda según algoritmo prefijo.
template<class Node>
void	levelOrder (Node *root, void(*visitFct)(Node *, int, bool), const size_t &queue_size)
	Recorre por niveles un árbol binario.
template<class Node>
int	postOrderRec (Node *root, void(*visitFct)(Node *, int, int))
	Recorre recursivamente en sufijo un árbol binario.
template<class Node>
Node *	preorder_to_binary_search_tree (DynArray< typename Node::key_type > &preorder, const int &l, const int &r)
	Reconstruye un árbol binario de búsqueda a partir de su recorrido prefijo.
template<class Node>
int	preOrderRec (Node *root, void(*visitFct)(Node *, int, int))
	Recorre recursivamente en prefijo un árbol binario.
template<class Node>
size_t	preOrderStack (Node *node, void(*visitFct)(Node *, int, int))
	Recorre en prefijo un árbol binario.
template<class Node>
void	preOrderThreaded (Node *node, void(*visitFct)(Node *))
	Recorre en prefijo un árbol binario sin usar recursión o pila explícita.
Node *	random_join_exclusive (Node *tl, Node *tr)
	Unión exclusiva aleatoria de dos árboles binarios de búsqueda, exclusivos, con rangos.
template<class Node, class Compare>
Node *	remove_by_key_xt (Node *&root, const typename Node::key_type &key)
	Elimina una clave de un árbol binario de búsqueda con rangos mediante la unión exclusiva.
template<class Node>
Node *	remove_by_pos_xt (Node *&root, const size_t &pos)
	Elimina un nodo de un árbol binario de búsqueda con rangos en la posición pos.
template<class Node, class Compare>
Node *	remove_from_search_binary_tree (Node *&root, const typename Node::key_type &key)
	Elimina una clave de un árbol binario de búsqueda mediante la unión exclusiva.
template<class Node>
Node *	rotate_to_left (Node *p, Node *pp)
	Rotación a la izquierda con actualización del padre.
template<class Node>
Node *	rotate_to_left (Node *p)
	Rota hacia la izquierda el árbol binario con raíz p.
template<class Node>
Node *	rotate_to_left_xt (Node *p)
	Rota hacia la izquierda el árbol binario con rangos de raíz p.
template<class Node>
Node *	rotate_to_right (Node *p)
	Rota hacia la derecha el árbol binario con raíz p.
template<class Node>
Node *	rotate_to_right_xt (Node *p)
	Rota hacia la derecha el árbol binario con rangos de raíz p.
template<class Node, class Equal>
Node *	search_deway (Node *root, const typename Node::key_type &key, int deway[], const size_t &size, size_t &n)
	Busca key en arborescencia y calcula el número de Deway del nodo contentivo de la clave key.
template<class Node, class Compare>
Node *	search_parent (Node *root, const typename Node::key_type &key, Node *&parent)
	Búsqueda de clave en árbol binario de búsqueda con determinación del padre.
template<class Node, class Compare>
Node *	search_rank_parent (Node *root, const typename Node::key_type &key)
	Búsqueda fallida de nodo y determinación del padre.
template<class Node, class Compare>
Node *	searchInBinTree (Node *root, const typename Node::key_type &key)
	Busca una clave en un árbol binario de búsqueda.
template<class Node>
Node *	select (Node *r, const size_t &pos) throw (std::exception, std::out_of_range)
	Selecciona un nodo de un árbol binario según su posición infija.
template<class Node>
Node *	select_gotoup_root (Node *root, const size_t &i)
	Selecciona un nodo de un árbol binario según su posición infija y lo convierte en su raíz.
template<class Node>
Node *	select_rec (Node *r, const size_t &i) throw (std::exception, std::out_of_range)
	Selecciona un nodo de un árbol binario según su posición infija.
template<class Node>
size_t	simple_preOrderStack (Node *node, void(*visitFct)(Node *, int, int))
	Recorre en prefijo un árbol binario.
template<class Node, class Key, class Compare>
void	split_key (Node *root, const Key &key, Node *&l, Node *&r)
	Particiona iterativamente un árbol binario de búsqueda según una clave.
template<class Node, class Compare>
bool	split_key_rec (Node *root, const typename Node::key_type &key, Node *&ts, Node *&tg)
	Particiona recursivamente un árbol binario de búsqueda según una clave.
template<class Node, class Compare>
bool	split_key_rec_xt (Node *root, const typename Node::key_type &key, Node *&l, Node *&r)
	Particiona un árbol binario de búsqueda con rangos según una clave.
template<class Node>
void	split_pos_rec (Node *r, const size_t &i, Node *&ts, Node *&tg)
	Particiona un árbol binario con rangos en la posición i.
template<class Node>
void	swap_node_with_predecessor (Node *p, Node *&pp, Node *q, Node *&pq)
	Intercambia a nivel de enlaces un nodo con su predecesor.
template<class Node>
void	swap_node_with_successor (Node *p, Node *&pp, Node *q, Node *&pq)
	Intercambia a nivel de enlaces un nodo con su sucesor.
template<class Node>
void	tree_postorder_traversal (Node *root, void(*visitFct)(Node *, int, int))
	Recorre en sufijo un árbol.
template<class Node>
void	tree_preorder_traversal (Node *root, void(*visitFct)(Node *, int, int))
	Recorre en prefijo un árbol.

---

Descripción detallada

Aleph maneja dos tipos básicos de árboles con raíz:

1. Árboles generales: bajo el tipo Tree_Node.
2. Árboles binarios: bajo el tipo fundamental BinNode.

En el discurso sobre las funciones, el árbol Tree_Node se menciona como "árbol" o "arborescencia", mientras que BinNode como "árbol binario".

Prácticamente, la mayoría de las funciones parametrizan bajo el tipo genérico Node el tipo de nodo del árbol. Este debe ser derivado de Tree_Node si se trata de un árbol o arborescencia o de BinNode si es un árbol binario.

Autor:

Leandro R. León (lrleon en ula punto ve)

---

Documentación de las definiciones

#define COUNT

(

p

)

((p)->getCount())

Parámetros:

p

puntero a un nodo con rangos.

Definición en la línea 74 del archivo tpl_binNodeXt.H.

Referenciado por set::empty(), multiset::empty(), Gen_Treap_Rk::Iterator::get_current_position(), Gen_Treap_Rk::Iterator::has_current(), Aleph::inorder_position(), Gen_Rand_Tree< Aleph::RandNodeVtl< Key >, Key, Compare >::insert(), Aleph::insert_by_key_xt(), Aleph::insert_by_pos_xt(), Aleph::insert_root_xt(), Aleph::join_exclusive_xt(), Gen_Rand_Tree< Aleph::RandNodeVtl< Key >, Key, Compare >::random_insert(), Gen_Rand_Tree< Aleph::RandNodeVtl< Key >, Key, Compare >::random_join_exclusive(), Gen_Rand_Tree< Aleph::RandNodeVtl< Key >, Key, Compare >::random_remove(), Gen_Treap_Rk< Aleph::Treap_Rk_Node< Key >, Key, Compare >::remove(), Aleph::remove_by_key_xt(), Aleph::remove_by_pos_xt(), Gen_Treap_Rk::Iterator::reset_last(), Aleph::rotate_to_left_xt(), Aleph::rotate_to_right_xt(), Aleph::select(), Aleph::select_gotoup_root(), Aleph::select_rec(), Gen_Treap_Rk< Aleph::Treap_Rk_Node< Key >, Key, Compare >::size(), set::size(), map::size(), Aleph::split_key_rec_xt(), y Aleph::split_pos_rec().

#define DECLARE_BINNODE	(	Name,
		height,
		Control_Data		)

Valor:

INIT_CLASS_BINNODE(Name, height, Control_Data)                    \
};                                                                \
                                                                  \
template <typename Key> Name<Key> * const Name<Key>::NullPtr = NULL; \
                                                                  \
INIT_CLASS_BINNODE(Name##Vtl, height, Control_Data)               \
virtual ~Name##Vtl() { /* empty */ }                              \
};                                                                \
                                                                  \
template <typename Key> Name##Vtl<Key> * const Name##Vtl<Key>::NullPtr = NULL

DECLARE_BINNODE(Name,height,Control_Data) genera dos clases de nodos binarios llamados Name y NameVtl. La diferencia entre los dos tipos de nodos está dada por el hecho de que NameVtl tiene un destructor virtual.

Las clases generadas tienen un atributo clave llamado key y asequible mediante Key(p), donde p es un puntero a nodo.

Cada clase de nodo binario posee dos tipos de atributos estáticos:

1. NullPtr: es la dirección del nodo que se considera como el árbol binario vacío.
2. MaxHeight: un estimado de la altura máxima que puede alcanzar el árbol binario. Muchos algoritmos sobre árboles~binarios son recursivos, por lo que el consumo de espacio en pila es un factor a considerar. En este sentido, el atributo~[[MaxHeight]] ofrece un aproximado de la altura máxima del árbol binario, cuyo valor sirve a los algoritmos a tomar previsiones acerca del consumo en pila.

Parámetros:

	Name	el nombre del nodo binario.
	height	máxima altura que puede tener un árbol binario.
	Control_Data	datos que se almacenan en el nodo según la índole de su uso.

Ver también:

DECLARE_BINNODE_SENTINEL

Definición en la línea 168 del archivo tpl_binNode.H.

#define DECLARE_BINNODE_SENTINEL	(	Name,
		height,
		Control_Data		)

Valor:

INIT_CLASS_BINNODE(Name, height, Control_Data)                   \
  Name(SentinelCtor) :                                           \
    Control_Data(sentinelCtor), lLink(NullPtr), rLink(NullPtr) {}\
  static Name sentinel_node;                                     \
};                                                               \
                                                                 \
template <typename Key>                                          \
Name<Key> Name<Key>::sentinel_node(sentinelCtor);                \
                                                                 \
template <typename Key>                                          \
Name<Key> * const Name<Key>::NullPtr = &Name<Key>::sentinel_node;\
                                                                 \
INIT_CLASS_BINNODE(Name##Vtl, height, Control_Data)              \
virtual ~Name##Vtl() { /* empty */ }                             \
private:                                                         \
  Name##Vtl(SentinelCtor) :                                      \
    Control_Data(sentinelCtor), lLink(NullPtr), rLink(NullPtr) {}\
  static Name##Vtl sentinel_node;                                \
};                                                               \
                                                                 \
template <typename Key>                                          \
Name##Vtl<Key> Name##Vtl<Key>::sentinel_node(sentinelCtor);      \
                                                                 \
template <typename Key>                                          \
Name##Vtl<Key> * const Name##Vtl<Key>::NullPtr =                 \
  &Name##Vtl<Key>::sentinel_node

DECLARE_BINNODE(Name,height,Control_Data) genera dos clases de nodos binarios llamados Name y NameVtl. La diferencia entre los dos tipos de nodos está dada por el hecho de que NameVtl tiene un destructor virtual.

Las clases generadas instancian un nodo centinela bajo con un constructor con parámetros de tipo SentinelCtor. Este es el constructor del nodo centinela y debe ser especificado por el diseñador del nodo.

Las clases generadas tienen un atributo clave llamado key y asequible mediante Key(p), donde p es un puntero a nodo.

Cada clase de nodo binario posee dos tipos de atributos estáticos:

1. NullPtr: es la dirección del nodo que se considera como el árbol binario vacío.
2. MaxHeight: un estimado de la altura máxima que puede alcanzar el árbol binario. Muchos algoritmos sobre árboles~binarios son recursivos, por lo que el consumo de espacio en pila es un factor a considerar. En este sentido, el atributo~[[MaxHeight]] ofrece un aproximado de la altura máxima del árbol binario, cuyo valor sirve a los algoritmos a tomar previsiones acerca del consumo en pila.

Parámetros:

	Name	el nombre del nodo binario.
	height	máxima altura que puede tener un árbol binario.
	Control_Data	datos que se almacenan en el nodo según la índole de su uso.

Ver también:

DECLARE_BINNODE

Definición en la línea 213 del archivo tpl_binNode.H.

---

Documentación de las funciones

TNode* Aleph::bin_to_forest

(

BNode *

broot

)

[inline]

bin_to_forest(root) toma un árbol binario derivado de BinNode y lo convierte a su arborescencia equivalente.

La rutina maneja dos parámetros tipo:

1. TNode: tipo de árbol basado en Tree_Node.
2. BNode: tipo de árbol binario basado en BinNode.

El procedimiento asume que ambos tipos comparten el mismo tipo de clave.

Parámetros:

[in]

broot

raíz del árbol binario a convertir.

Devuelve:

raíz del primer árbol equivalente a árbol binario dado.

Excepciones:

bad_alloc

si no hay suficiente memoria.

Ver también:

forest_to_bin()

Definición en la línea 928 del archivo tpl_tree_node.H.

Hace referencia a KEY.

Node* Aleph::build_optimal_tree	(	Key	keys[],
		double	p[],
		const int &	n
	)			[inline]

build_optimal_tree(keys,p,n) construye un árbol binario de búsqueda óptimo que contiene n claves almacenadas en el arreglo keys[], cada clave con frecuencia o probabilidad de búsqueda almacenada en el arreglo p[], paralelo a keys[].

Parámetros:

[in]	keys	arreglo contentivo de las claves.
[in]	p	arreglos contentivo de las probabilidades de aparición o búsqueda.
[in]	n	cantidad total de claves; esta es la dimensión de los arreglos.

Devuelve:

la raíz del árbol binario de búsqueda óptimo.

Excepciones:

bad_alloc

si no hay suficiente memoria.

Definición en la línea 142 del archivo opBinTree.H.

Node<Key>* Aleph::build_tree	(	DynArray< Key > &	preorder,
		const int &	l_p,
		const int &	r_p,
		DynArray< Key > &	inorder,
		const int &	l_i,
		const int &	r_i
	)			[inline]

build_tree() toma dos arreglos dinámicos contentivos de los recorridos prefijo e infijo de un árbol y reconstruye el árbol que ocasiona los recorridos en cuestión.

Parámetros:

[in]	preorder	arreglo contentivo del recorrido prefijo.
[in]	l_p	comienzo del recorrido prefijo en el arreglo preorder.
[in]	r_p	final del recorrido prefijo en el arreglo preorder.
[in]	inorder	arreglo contentivo del recorrido infijo.
[in]	l_i	comienzo del recorrido infijo en el arreglo inorder.
[in]	r_i	final del recorrido infijo en el arreglo inorder.

Devuelve:

la raíz de un árbol binario, único, que ocasiona los recorridos dados en parámetros.

Excepciones:

bad_alloc

si no hay suficiente memoria.

Definición en la línea 663 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

bool check_binary_search_tree

(

Node *

node

)

[inline]

check_binary_search_tree(node) verifica si el árbol binario con raíz node satisface la propiedad de orden de un árbol binario de búsqueda para el criterio de comparación Compare()().

Parámetros:

[in]

node

raíz del árbol binario a verificar.

Devuelve:

true si el árbol binario satisface la condición de } orden; false de lo contrario.

Definición en la línea 915 del archivo tpl_binNodeUtils.H.

Hace referencia a KEY, LLINK, y RLINK.

size_t Aleph::compute_cardinality_rec

(

Node *

node

)

[inline]

compute_cardinality_rec(node) todo el árbol con raíz node y contabiliza la cantidad de nodos.

Parámetros:

[in]

node

raíz del árbol a calcular la cardinalidad.

Devuelve:

número de nodos que tiene el árbol.

Definición en la línea 434 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

size_t Aleph::compute_height

(

Node *

root

)

[inline]

Parámetros:

[in]

root

raíz del árbol.

Devuelve:

altura del árbol en raíz root.

Definición en la línea 680 del archivo tpl_tree_node.H.

void Aleph::compute_nodes_in_level	(	Node *	root,
		const int &	level,
		DynDlist< Node * > &	list
	)			[inline]

compute_nodes_in_level(root,level,list) guarda en la lista dinámica list los nodos del nivel level en el árbol cuya raíz es root.

Parámetros:

[in]	root	raíz del árbol binario.
[in]	level	el nivel que se desea contabilizar.
[out]	list	lista dinámica de nodos situados en el nivel level.

Excepciones:

bad_alloc

si no hay suficiente memoria.

Definición en la línea 741 del archivo tpl_binNodeUtils.H.

size_t Aleph::computeHeightRec

(

Node *

node

)

[inline]

computeHeightRec(node) calcula la altura de todo el árbol con raíz node.

Parámetros:

[in]

node

raíz del árbol a calcular altura.

Devuelve:

altura del árbol.

Definición en la línea 452 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

Referenciado por DynSetTree< Aleph::Splay_Tree< Key, Compare >, Key, Compare >::height(), y DynMapTree< Aleph::Avl_Tree< Key, Compare >, Key, Type, Compare >::height().

Node* Aleph::copyRec

(

Node *

src_root

)

throw (std::exception, std::bad_alloc) [inline]

copyRec(src_root) retorna una copia entera del árbol binario con raíz node.

Parámetros:

[in]

src_root

raíz del árbol a copiar.

Devuelve:

una copia del árbol con raíz src_root.

Excepciones:

bad_alloc

si no hay suficiente memoria.

Definición en la línea 473 del archivo tpl_binNodeUtils.H.

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

Referenciado por DynMapTree< Aleph::Avl_Tree< Key, Compare >, Key, Type, Compare >::DynMapTree(), map::map(), DynMapTree< Aleph::Avl_Tree< Key, Compare >, Key, Type, Compare >::operator=(), set::operator=(), map::operator=(), y set::set().

void Aleph::destroy_forest

(

Node *

root

)

[inline]

destroy_forest(root) libera toda la memoria ocupada por el la arborescencia cuyo primer árbol tiene raíz root.

Parámetros:

[in]

root

raíz del primer árbol de la arborescencia que se desea destruir.

Excepciones:

domain_error

si root no es nodo raíz del árbol más a la izquierda de la arborescencia.

Definición en la línea 652 del archivo tpl_tree_node.H.

Hace referencia a Aleph::destroy_tree().

void Aleph::destroy_tree

(

Node *

root

)

[inline]

destroy_tree(root) libera toda la memoria ocupada por el árbol cuya raíz es root.

Parámetros:

[in]

root

raíz del árbol que se desea liberar.

Definición en la línea 621 del archivo tpl_tree_node.H.

Referenciado por Aleph::destroy_forest().

void Aleph::destroyRec

(

Node *

root

)

[inline]

destroyRec(root) destruye (libera toda la memoria) del árbol binario cuya raíz es root.

Parámetros:

[in]

root

raíz del árbol a destruir.

Definición en la línea 509 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

Referenciado por set::clear(), multiset::clear(), map::clear(), Aleph::copyRec(), DynMapTree< Aleph::Avl_Tree< Key, Compare >, Key, Type, Compare >::empty(), set::erase(), map::erase(), DynMapTree< Aleph::Avl_Tree< Key, Compare >, Key, Type, Compare >::operator=(), set::operator=(), multiset::operator=(), map::operator=(), DynMapTree< Aleph::Avl_Tree< Key, Compare >, Key, Type, Compare >::~DynMapTree(), DynSetTree< Aleph::Splay_Tree< Key, Compare >, Key, Compare >::~DynSetTree(), map::~map(), multiset::~multiset(), y set::~set().

Node* Aleph::deway_search	(	Node *	root,
		int	path[],
		const size_t &	size
	)			[inline]

deway_search(root,path,size) toma el número de Deway guardado en path, de longitud size y busca en la arborescencia cuyo primer árbol es root un nodo que se corresponda con el número de Deway dado.

Parámetros:

[in]	root	raíz del primer árbol de la arborescencia.
[in]	path	arreglo que contiene el número de Deway.
[in]	size	tamaño del número de deway.

Devuelve:

puntero al nodo correspondiente al número de Deway dado; NULL si no existe,

Definición en la línea 729 del archivo tpl_tree_node.H.

Node* Aleph::find_max

(

Node *

root

)

[inline]

find_max(root) retorna el máximo elemento del árbol binario de búsqueda cuya raíz es root.

Parámetros:

[in]

root

raíz del árbol binario de búsqueda.

Devuelve:

puntero al nodo que contiene el máximo elemento.

Nota:

No se realiza verificación de árbol vacío.

Ver también:

find_min()

Definición en la línea 1054 del archivo tpl_binNodeUtils.H.

Hace referencia a RLINK.

Node* Aleph::find_min

(

Node *

root

)

[inline]

find_min(root) retorna el mínimo elemento del árbol binario de búsqueda cuya raíz es root.

Parámetros:

[in]

root

raíz del árbol binario de búsqueda.

Devuelve:

puntero al nodo que contiene el mínimo elemento.

Nota:

No se realiza verificación de árbol vacío.

Ver también:

find_max()

Definición en la línea 1033 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK.

Node* Aleph::find_predecessor	(	Node *	p,
		Node *&	pp
	)			[inline]

find_predecessor(p,pp) busca el nodo predecesor dentro de la secuencia infija del nodo p.

Parámetros:

[in]	p	puntero a nodo del cual se desea conocer su predecesor infijo.
[out]	pp	puntero al padre del predecesor.

Devuelve:

puntero al nodo predecesor infijo de p.

Ver también:

find_successor()

Definición en la línea 1105 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

Node* Aleph::find_successor	(	Node *	p,
		Node *&	pp
	)			[inline]

find_successor(p,pp) busca el nodo sucesor dentro de la secuencia infija del nodo p.

Parámetros:

[in]	p	puntero a nodo del cual se desea conocer su sucesor infijo.
[out]	pp	puntero al padre del sucesor.

Devuelve:

puntero al nodo sucesor infijo de p.

Ver también:

find_predecessor()

Definición en la línea 1075 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

void Aleph::forest_postorder_traversal	(	Node *	root,
		void(*)(Node *, int, int)	visitFct
	)			[inline]

forest_postorder_traversal((root,visit) realiza un recorrido sufijo sobre el árbol con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p en el árbol.
3. child_index: índice de p dentro de sus hermanos.

Parámetros:

[in]	root	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Ver también:

forest_preorder_traversal() tree_preorder_traversal()

tree_postorder_traversal()

Excepciones:

domain_error

si root no es nodo raíz del árbol más a la izquierda de la arborescencia.

Definición en la línea 592 del archivo tpl_tree_node.H.

void Aleph::forest_preorder_traversal	(	Node *	root,
		void(*)(Node *, int, int)	visitFct
	)			[inline]

forest_preorder_traversal((root,visit) realiza un recorrido prefijo sobre la arborescencia root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p en el árbol.
3. child_index: índice de p dentro de sus hermanos.

Parámetros:

[in]	root	raíz del árbol primer árbol en la arborescencia.
[in]	visitFct	puntero a la función de visita.

Excepciones:

domain_error

si root no es un nodo raíz de un árbol.

Ver también:

tree_preorder_traversal() tree_postorder_traversal()

forest_postorder_traversal()

Definición en la línea 511 del archivo tpl_tree_node.H.

BNode* Aleph::forest_to_bin

(

TNode *

root

)

[inline]

forest_to_bin(root) toma una arborescencia derivada de Tree_Node y lo convierte a su equivalente árbol binario.

La rutina maneja dos parámetros tipo:

1. TNode: tipo de árbol basado en Tree_Node.
2. BNode: tipo de árbol binario basado en BinNode.

El procedimiento asume que ambos tipos comparten el mismo tipo de clave.

Parámetros:

[in]

root

raíz del primer árbol perteneciente a la arborescencia a convertir.

Devuelve:

raíz del árbol binario equivalente a la arborescencia dada.

Excepciones:

bad_alloc

si no hay suficiente memoria.

Ver también:

bin_to_forest()

Definición en la línea 862 del archivo tpl_tree_node.H.

Hace referencia a LLINK, y RLINK.

void Aleph::generate_forest	(	Node *	root,
		std::ofstream &	out = std::cout
	)			[inline]

generate_forest(root, out, tree_number) genera una especificación de dibujado de la arborescencia cuyo primer árbol es root para el programa de dibujado ntreepic. La salida es escrita en el archivo asociado a out.

Para escribir el contenido del nodo, la rutina usa la clase parametrizada Write, cuyo operador Write()(nodo) transforma la clave contenida en el nodo a la cadena que se desea sea escrita como contenido del nodo.

Parámetros:

[in]	root	raíz del árbol a dibujar.
[out]	out	archivo asociado donde se desea escribir la especificación de dibujado.

Ver también:

generate_tree()

Definición en la línea 161 del archivo generate_tree.H.

void Aleph::generate_tree	(	Node *	root,
		std::ofstream &	out,
		const int &	tree_number = 0
	)			[inline]

generate_tree(root, out, tree_number) genera una especificación de dibujado del árbol con raíz root para el programa de dibujado ntreepic. La salida es escrita en el archivo asociado a out.

Para escribir el contenido del nodo, la rutina usa la clase parametrizada Write, cuyo operador Write()(nodo) transforma la clave contenida en el nodo a la cadena que se desea sea escrita como contenido del nodo.

Parámetros:

[in]	root	raíz del árbol a dibujar.
[out]	out	archivo asociado donde se desea escribir la especificación de dibujado.
[in]	tree_number	para uso interno NO USAR.

Ver también:

generate_forest()

Definición en la línea 116 del archivo generate_tree.H.

int inorder_position	(	Node *	r,
		const typename Node::key_type &	key,
		Node *&	node
	)			[inline]

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. Una versión especializada asume como criterio la relación "menor que".

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]	node	puntero al nodo contentivo de la clave key(si fue encontrado).

Devuelve:

posición infija del nodo contentivo de la clave key si ésta se encuentra en el árbol.

Excepciones:

domain_error

si la clave no se encuentra en el árbol binario con rangos.

Definición en la línea 184 del archivo tpl_binNodeXt.H.

Hace referencia a COUNT, KEY, LLINK, y RLINK.

Referenciado por Gen_Treap_Rk< Aleph::Treap_Rk_Node< Key >, Key, Compare >::position(), y Gen_Treap_Rk::Iterator::reset_to_key().

int Aleph::inOrderRec	(	Node *	root,
		void(*)(Node *, int, int)	visitFct
	)			[inline]

inOrderRec(root,visit) realiza un recorrido infijo sobre el árbol binario con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p dentro de todo el árbol.
3. pos: el ordinal de visita.

Parámetros:

[in]	root	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Devuelve:

el número de nodos visitados.

Ver también:

preOrderRec() postOrderRec()

Definición en la línea 94 del archivo tpl_binNodeUtils.H.

Referenciado por DynSetTree< Aleph::Splay_Tree< Key, Compare >, Key, Compare >::for_each(), y DynMapTree< Aleph::Avl_Tree< Key, Compare >, Key, Type, Compare >::for_each_in_inorder().

size_t Aleph::inOrderStack	(	Node *	node,
		void(*)(Node *, int, int)	visitFct
	)			[inline]

inOrderStack(root,visit) realiza un recorrido infijo sobre el árbol binario con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p dentro de todo el árbol.
3. pos: el ordinal de visita.

En lugar de apelar a la recursión, esta versión del recorrido infijo utiliza una pila interna, vectorial, de capacidad máxima Node::MaxHeight.

Parámetros:

[in]	node	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Devuelve:

el número de nodos visitados.

Definición en la línea 341 del archivo tpl_binNodeUtils.H.

Hace referencia a ArrayStack::is_empty(), LLINK, ArrayStack::pop(), ArrayStack::push(), RLINK, y ArrayStack::size().

void Aleph::inOrderThreaded	(	Node *	root,
		void(*)(Node *)	visitFct
	)			[inline]

inOrderThreaded(root,visit) realiza un recorrido infijo sobre el árbol binario con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p dentro de todo el árbol.
3. pos: el ordinal de visita.

Esta versión del recorrido infijo no consume espacio en pila.

Parámetros:

[in]	root	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Devuelve:

el número de nodos visitados.

Ver también:

preOrderThreaded()

Nota:

La rutina no es reentrante.

Definición en la línea 773 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

Node * insert_by_key_xt	(	Node *&	r,
		Node *	p
	)			[inline]

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

Una versión especializada usa como criterio de comparación la relación "menor que".

Parámetros:

[in,out]	r	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.

Definición en la línea 230 del archivo tpl_binNodeXt.H.

Hace referencia a COUNT, KEY, LLINK, y RLINK.

void Aleph::insert_by_pos_xt	(	Node *&	r,
		Node *	p,
		const size_t &	pos
	)			[inline]

insert_by_pos_xt(r,p,pos) inserta en el árbol binario con rangos, en la posición infija pos, el nodo p.

Parámetros:

[in,out]	r	raíz del árbol binario con rangos.
[in]	p	nodo a insertar.
[in]	pos	posición infija de inserción.

Nota:

Nótese que la inserción ocurre independientemente del valor de clave que contenga p. Úsese a riesgo si se trata de un árbol binario de búsqueda.

Definición en la línea 436 del archivo tpl_binNodeXt.H.

Hace referencia a COUNT, LLINK, RLINK, y Aleph::split_pos_rec().

Node * insert_in_binary_search_tree	(	Node *&	root,
		Node *	p
	)			[inline]

insert_in_binary_search_tree(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()().

Una versión especializada usa como criterio de comparación la relación "menor que".

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.

Definición en la línea 1251 del archivo tpl_binNodeUtils.H.

Hace referencia a KEY, LLINK, y RLINK.

Node * insert_root	(	Node *&	root,
		Node *	p
	)			[inline]

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.

Ver también:

insert_root_rec

Definición en la línea 1447 del archivo tpl_binNodeUtils.H.

Hace referencia a KEY, LLINK, y RLINK.

Node * insert_root_rec	(	Node *	root,
		Node *	p
	)			[inline]

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.

Ver también:

insert_root

Definición en la línea 1875 del archivo tpl_binNodeUtils.H.

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

Node* Aleph::insert_root_xt	(	Node *&	root,
		Node *	p
	)			[inline]

insert_root_xt(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.

Definición en la línea 347 del archivo tpl_binNodeXt.H.

Hace referencia a COUNT, KEY, LLINK, y RLINK.

size_t Aleph::internal_path_length

(

Node *

p

)

[inline]

Parámetros:

[in]

p

raíz del árbol binario a calcular el ipl.

Devuelve:

la longitud del camino interno del árbol con raíz p.

Definición en la línea 898 del archivo tpl_binNodeUtils.H.

Referenciado por DynMapTree< Aleph::Avl_Tree< Key, Compare >, Key, Type, Compare >::internal_path_length().

Node * join	(	Node *	t1,
		Node *	t2,
		Node *&	dup
	)			[inline]

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.

Definición en la línea 1521 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

Node* Aleph::join_exclusive	(	Node *&	ts,
		Node *&	tg
	)			[inline]

join_exclusive(ts,tg) une dos árboles binarios de búsqueda en uno sólo. Por exclusivo se entiende que todas las claves de ts son menores que todas las claves de tg.

Parámetros:

[in]	ts	árbol binario de búsqueda de claves menores.
[in]	tg	árbol binario de búsqueda de claves mayores.

Devuelve:

árbol resultante de la unión exclusiva.

Nota:

La rutina no valida que ts y tg sean árboles binarios de búsqueda así como tampoco que sus rangos sean excluyentes.

Ver también:

remove_from_search_binary_tree()

Definición en la línea 1356 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

Referenciado por Gen_Splay_Tree< Aleph::BinNodeVtl< Key >, Key, Compare >::remove(), y Aleph::remove_from_search_binary_tree().

Node* Aleph::join_exclusive_xt	(	Node *&	ts,
		Node *&	tg
	)			[inline]

join_exclusive_xt(ts,tg) une dos árboles binarios de búsqueda con rangos en uno sólo. Por exclusivo se entiende que todas las claves de ts son menores que todas las claves de tg.

Parámetros:

[in]	ts	árbol binario de búsqueda de claves menores.
[in]	tg	árbol binario de búsqueda de claves mayores.

Devuelve:

árbol resultante de la unión exclusiva.

Nota:

La rutina no valida que ts y tg sean árboles binarios de búsqueda así como tampoco que sus rangos sean excluyentes.

Ver también:

remove_by_key_xt()

Definición en la línea 464 del archivo tpl_binNodeXt.H.

Hace referencia a COUNT, LLINK, y RLINK.

Referenciado por Aleph::remove_by_key_xt(), y Aleph::remove_by_pos_xt().

Node* Aleph::join_preorder	(	Node *	t1,
		Node *	t2,
		Node *&	dup
	)			[inline]

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.

Definición en la línea 1486 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

void Aleph::levelOrder	(	Node *	root,
		void(*)(Node *, int, bool)	visitFct,
		const size_t &	queue_size
	)			[inline]

levelOrder(root,visit) realiza un recorrido por niveles sobre el árbol binario con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, bool is_left)

Donde:

1. p: puntero al nodo actualmente visitado.
2. pos: el ordinal de visita.
3. is_left: true si el nodo es un hijo izquierdo, false de lo contrario.

Este algoritmo utiliza una cola, vectorial, de capacidad máxima queue_size.

Parámetros:

[in]	root	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.
[in]	queue_size	tamaño de la cola interna.

Devuelve:

el número de nodos visitados.

Nota:

La cola interna es un arreglo contiguo en memoria que es apartado al principio de la rutina y liberado al final. Esto hace que esta rutina sea bastante limitada en memoria. Úsese cuidado.

Definición en la línea 611 del archivo tpl_binNodeUtils.H.

Hace referencia a ArrayQueue::get(), ArrayQueue::is_empty(), LLINK, ArrayQueue::put(), y RLINK.

int Aleph::postOrderRec	(	Node *	root,
		void(*)(Node *, int, int)	visitFct
	)			[inline]

postOrderRec(root,visit) realiza un recorrido infijo sobre el árbol binario con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p dentro de todo el árbol.
3. pos: el ordinal de visita.

Parámetros:

[in]	root	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Devuelve:

el número de nodos visitados.

Ver también:

inOrderRec() preOrderRec()

Definición en la línea 188 del archivo tpl_binNodeUtils.H.

Referenciado por DynMapTree< Aleph::Avl_Tree< Key, Compare >, Key, Type, Compare >::for_each_in_postorder().

Node* Aleph::preorder_to_binary_search_tree	(	DynArray< typename Node::key_type > &	preorder,
		const int &	l,
		const int &	r
	)			[inline]

Parámetros:

[in]	preorder	arreglo dinámico contentivo del recorrido prefijo de las claves de un árbol binario de búsqueda.
[in]	l	índice de comienzo de la secuencia prefija en el arreglo dinámico preorder.
[in]	r	índice de término de la secuencia prefija en el arreglo dinámico preorder.

Devuelve:

raíz del árbol binario de búsqueda que produce la secuencia prefija dada.

Excepciones:

bad_alloc

si no hay suficiente memoria.

Definición en la línea 961 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

int Aleph::preOrderRec	(	Node *	root,
		void(*)(Node *, int, int)	visitFct
	)			[inline]

preOrderRec(root,visit) realiza un recorrido prefijo sobre el árbol binario con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p dentro de todo el árbol.
3. pos: el ordinal de visita.

Parámetros:

[in]	root	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Devuelve:

el número de nodos visitados.

Ver también:

inOrderRec() postOrderRec()

Definición en la línea 141 del archivo tpl_binNodeUtils.H.

Referenciado por DynSetTree< Aleph::Splay_Tree< Key, Compare >, Key, Compare >::for_each_in_preorder(), y DynMapTree< Aleph::Avl_Tree< Key, Compare >, Key, Type, Compare >::for_each_in_preorder().

size_t Aleph::preOrderStack	(	Node *	node,
		void(*)(Node *, int, int)	visitFct
	)			[inline]

preOrderRec(root,visit) realiza un recorrido prefijo sobre el árbol binario con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p dentro de todo el árbol.
3. pos: el ordinal de visita.

En lugar de apelar a la recursión, esta versión del recorrido prefijo utiliza una pila interna, vectorial, de capacidad máxima Node::MaxHeight.

Parámetros:

[in]	node	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Devuelve:

el número de nodos visitados.

Ver también:

simple_preOrderStack()

Definición en la línea 278 del archivo tpl_binNodeUtils.H.

Hace referencia a ArrayStack::is_empty(), LLINK, ArrayStack::pop(), ArrayStack::push(), RLINK, y ArrayStack::size().

void Aleph::preOrderThreaded	(	Node *	node,
		void(*)(Node *)	visitFct
	)			[inline]

prerderThreaded(root,visit) realiza un recorrido prefijo sobre el árbol binario con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p dentro de todo el árbol.
3. pos: el ordinal de visita.

Esta versión del recorrido prefijo no consume espacio en pila.

Parámetros:

[in]	node	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Devuelve:

el número de nodos visitados.

Ver también:

inOrderThreaded()

Nota:

La rutina no es reentrante.

Definición en la línea 840 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

Node* random_join_exclusive	(	Node *	tl,
		Node *	tr
	)			[inline, inherited]

random_join_exclusive(tl,tr) une dos árboles binarios de búsqueda con rangos en uno sólo. Por exclusivo se entiende que todas las claves de tl son menores que todas las claves de tr. A diferencia de join_exclusive(), random_join_exclusive() escoge aleatoriamente cuál de las raíces de tl y tr devendrá raíz del árbol binario resultante. Consecuentemente, el árbol siempre será aleatorio.

La rutina puede ser utilizada por cualquier clase de árbol binario de búsqueda con rangos derivada de BinNodeXt. Su presencia dentro de la clase Gen_Rand_Tree obedece a la disponibilidad del generador de números aleatorios.

Parámetros:

[in]	tl	árbol binario de búsqueda con rangos de claves menores.
[in]	tr	árbol binario de búsqueda con rangos de claves mayores.

Devuelve:

árbol resultante de la unión exclusiva.

Nota:

La rutina no valida que tl y tr sean árboles binarios de búsqueda así como tampoco que sus rangos sean excluyentes.

Ver también:

BinNodeXt join_exclusive() Gen_Rand_Tree::random_insert()

Definición en la línea 227 del archivo tpl_rand_tree.H.

Referenciado por Gen_Rand_Tree< Aleph::RandNodeVtl< Key >, Key, Compare >::random_join_exclusive(), y Gen_Rand_Tree< Aleph::RandNodeVtl< Key >, Key, Compare >::random_remove().

Node * remove_by_key_xt	(	Node *&	root,
		const typename Node::key_type &	key
	)			[inline]

remove_by_key_xt(root,key) busca en el árbol binario de búsqueda con rangos de 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_xt()

Definición en la línea 504 del archivo tpl_binNodeXt.H.

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

Node* Aleph::remove_by_pos_xt	(	Node *&	root,
		const size_t &	pos
	)			[inline]

remove_by_pos_xt(root,pos) elimina del árbol binario con rangos des raíz root el nodo en la posición pos. 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]	pos	posición infija del nodo a eliminar.

Devuelve:

puntero al nodo eliminado.

Ver también:

join_exclusive()

Definición en la línea 570 del archivo tpl_binNodeXt.H.

Hace referencia a COUNT, Aleph::join_exclusive_xt(), LLINK, y RLINK.

Node * remove_from_search_binary_tree	(	Node *&	root,
		const typename Node::key_type &	key
	)			[inline]

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()

Definición en la línea 1394 del archivo tpl_binNodeUtils.H.

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

Node* Aleph::rotate_to_left	(	Node *	p,
		Node *	pp
	)			[inline]

rotate_to_left(p, pp) rota hacia la izquierda el árbol binario con raíz p y actualiza en pp, el padre de p, la rama que apunta al árbol binario rotado resultante.

Parámetros:

[in]	p	raíz del árbol a rotar.
[in,out]	pp	padre de p. Luego de la operación, la rama de pp que apunta a p es actualizada al árbol binario resultante de la rotación.

Devuelve:

Árbol binario resultante de la rotación.

Definición en la línea 1629 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

Referenciado por Aleph::insert_root_rec(), y Gen_Treap< Aleph::TreapNodeVtl< Key >, Key, Compare >::remove().

Node * search_deway	(	Node *	root,
		const typename Node::key_type &	key,
		int	deway[],
		const size_t &	size,
		size_t &	n
	)			[inline]

search_deway(root,key,deway,n) busca en la arborescencia cuyo primer árbol es root un nodo que contenga la clave key. Si el nodo es encontrado, entonces la rutina guarda en deway[] el número de Deway del nodo encontrado.

La búsqueda se realiza con criterio de igualdad Equal()(). Una versión especializada realiza la búsqueda con criterio "menor que".

Parámetros:

[in]	root	raíz del primer árbol de la arborescencia.
[in]	key	clave a buscar
[out]	deway	arreglo que contiene el número de Deway.
[in]	size	tamaño máximo del número de deway.
[out]	n	tamaño del número de Deway calculado (si se encuentra el nodo).

Devuelve:

puntero al nodo contentivo de la clave key; NULL si no existe ningún nodo con clave key,

Excepciones:

overflow_error

si size no es suficiente para almacenar la secuencia de Deway.

Definición en la línea 769 del archivo tpl_tree_node.H.

Node * search_parent	(	Node *	root,
		const typename Node::key_type &	key,
		Node *&	parent
	)			[inline]

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.

La rutina utiliza como criterio de comparación Compare()(). Una versión especializada asume la relación "menor que" como criterio de comparación

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; NULL de lo contrario.

Ver también:

searchInBinTree()

Definición en la línea 1144 del archivo tpl_binNodeUtils.H.

Hace referencia a KEY, LLINK, y RLINK.

Node * search_rank_parent	(	Node *	root,
		const typename Node::key_type &	key
	)			[inline]

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.

Definición en la línea 1200 del archivo tpl_binNodeUtils.H.

Hace referencia a KEY, LLINK, y RLINK.

Referenciado por set::lower_bound(), map::lower_bound(), set::upper_bound(), y map::upper_bound().

Node * searchInBinTree	(	Node *	root,
		const typename Node::key_type &	key
	)			[inline]

searchInBinTree(root,key) busca en un árbol binario de búsqueda un nodo contentivo de la clave key.

El árbol binario de búsqueda está ordenado con criterio de comparación Compare()().

Una versión especializada utiliza como comparación la relación "menor que".

Parámetros:

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

Devuelve:

puntero a nodo contentivo de key este se encuentra en el árbol binario de búsqueda; NULL de lo contrario.

Definición en la línea 1001 del archivo tpl_binNodeUtils.H.

Hace referencia a KEY, LLINK, y RLINK.

Node* Aleph::select	(	Node *	r,
		const size_t &	pos
	)			throw (std::exception, std::out_of_range) [inline]

select(r,i) retorna el nodo cuya posición infija es in del árbol binario con rangos cuya raíz es r.

Este algoritmo de selección es iterativo. Es más eficiente y seguro que select_rec().

Parámetros:

[in]	r	raíz del árbol binario con rangos.
[in]	pos	posición infija que se desea acceder.

Devuelve:

puntero al nodo en la posición infija i.

Excepciones:

out_of_range

si i es mayor o igual que la cantidad total de nodos del árbol binario.

Ver también:

select_rec()

Definición en la línea 131 del archivo tpl_binNodeXt.H.

Hace referencia a COUNT, LLINK, y RLINK.

Referenciado por Gen_Treap_Rk< Aleph::Treap_Rk_Node< Key >, Key, Compare >::select().

Node* Aleph::select_gotoup_root	(	Node *	root,
		const size_t &	i
	)			[inline]

select_gotoup_root(r,i) selecciona el nodo con posición infija i y lo rota hasta que éste devenga su raíz.

Este algoritmo de selección es recursivo.

Parámetros:

[in]	root	raíz del árbol binario con rangos.
[in]	i	posición infija que se desea acceder.

Devuelve:

puntero al nodo en la posición infija i el cual luego de la llamada es raíz del árbol binario.

Excepciones:

out_of_range

si i es mayor o igual que la cantidad total de nodos del árbol binario.

Ver también:

select() select_rec_xt()

Definición en la línea 72 del archivo tpl_balanceXt.H.

Hace referencia a COUNT, LLINK, RLINK, Aleph::rotate_to_left_xt(), y Aleph::rotate_to_right_xt().

Node* Aleph::select_rec	(	Node *	r,
		const size_t &	i
	)			throw (std::exception, std::out_of_range) [inline]

select_rec(r,i) retorna el nodo con posición infija i en árbol binario con rangos cuya raíz es r.

Este algoritmo de selección es recursivo.

Parámetros:

[in]	r	raíz del árbol binario con rangos.
[in]	i	posición infija que se desea acceder.

Devuelve:

puntero al nodo en la posición infija i.

Excepciones:

out_of_range

si i es mayor o igual que la cantidad total de nodos del árbol binario.

Ver también:

select()

Definición en la línea 93 del archivo tpl_binNodeXt.H.

Hace referencia a COUNT, LLINK, y RLINK.

size_t Aleph::simple_preOrderStack	(	Node *	node,
		void(*)(Node *, int, int)	visitFct
	)			[inline]

simple_preOrderRec(root,visit) realiza un recorrido prefijo sobre el árbol binario con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p dentro de todo el árbol.
3. pos: el ordinal de visita.

En lugar de apelar a la recursión, esta versión del recorrido prefijo utiliza una pila interna, vectorial, de capacidad máxima Node::MaxHeight.

Parámetros:

[in]	node	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Devuelve:

el número de nodos visitados.

Ver también:

preOrderStack()

Definición en la línea 223 del archivo tpl_binNodeUtils.H.

Hace referencia a ArrayStack::is_empty(), LLINK, ArrayStack::pop(), ArrayStack::push(), RLINK, y ArrayStack::size().

void split_key	(	Node *	root,
		const Key &	key,
		Node *&	l,
		Node *&	r
	)			[inline]

split_key(root,key,l,r) particiona ietartivamente, 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.

Ver también:

split_key_rec

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.

Definición en la línea 1674 del archivo tpl_binNodeUtils.H.

Hace referencia a KEY, LLINK, y RLINK.

bool split_key_rec	(	Node *	root,
		const typename Node::key_type &	key,
		Node *&	ts,
		Node *&	tg
	)			[inline]

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.

Ver también:

split_key()

Definición en la línea 1297 del archivo tpl_binNodeUtils.H.

Hace referencia a KEY, LLINK, y RLINK.

bool split_key_rec_xt	(	Node *	root,
		const typename Node::key_type &	key,
		Node *&	l,
		Node *&	r
	)			[inline]

split_key_rec_xt(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.

Definición en la línea 288 del archivo tpl_binNodeXt.H.

Hace referencia a COUNT, KEY, LLINK, y RLINK.

void Aleph::split_pos_rec	(	Node *	r,
		const size_t &	i,
		Node *&	ts,
		Node *&	tg
	)			[inline]

split_pos_rec(r,i,ts,tg) particiona un árbol binario de búsqueda con rangos, según la posición infija u, en dos árboles ts y tg. Luego de la operación el árbol, el árbol root deviene vacío, ts contiene todas las claves entre [0..i] y tg entre (i..n) donde n es la cantidad de nodos del árbol binario. que key y tg las mayores.

Parámetros:

[in,out]	r	puntero a la raíz del árbol binario con rangos que se desea particionar.
[in]	i	posición infija de partición.
[out]	ts	árbol binario de búsqueda con rangos con las claves [0..i].
[out]	tg	árbol binario de búsqueda con rangos con las claves (i..n).

Definición en la línea 382 del archivo tpl_binNodeXt.H.

Hace referencia a COUNT, LLINK, y RLINK.

Referenciado por Aleph::insert_by_pos_xt(), y Gen_Treap_Rk< Aleph::Treap_Rk_Node< Key >, Key, Compare >::remove().

void Aleph::swap_node_with_predecessor	(	Node *	p,
		Node *&	pp,
		Node *	q,
		Node *&	pq
	)			[inline]

swap_node_with_predecessor(p,pp,q,pq) intercambia, a nivel de sus enlaces en un árbol binario, el nodo p con su nodo predecesor infijo q. Los enlaces de los padres de p y q son los parámetros pp y pq que se requieren para realizar la actualización.

La rutina está esencialmente destinada para usarse en la eliminación en un árbol binario de búsqueda.

Parámetros:

[in]	p	nodo a intercambiar con su predecesor.
[in,out]	pp	padre del nodo p.
[in]	q	predecesor del nodo p.
[in,out]	pq	padre del sucesor q.

Ver también:

swap_node_with_predecessor

Definición en la línea 1814 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

void Aleph::swap_node_with_successor	(	Node *	p,
		Node *&	pp,
		Node *	q,
		Node *&	pq
	)			[inline]

swap_node_with_successor(p,pp,q,pq) intercambia, a nivel de sus enlaces en un árbol binario, el nodo p con su nodo sucesor infijo q. Los enlaces de los padres de p y q son los parámetros pp y pq que se requieren para realizar la actualización.

La rutina está esencialmente destinada para usarse en la eliminación en un árbol binario de búsqueda.

Parámetros:

[in]	p	nodo a intercambiar con su sucesor.
[in,out]	pp	padre del nodo p.
[in]	q	sucesor del nodo p.
[in,out]	pq	padre del sucesor q.

Ver también:

swap_node_with_predecessor

Definición en la línea 1753 del archivo tpl_binNodeUtils.H.

Hace referencia a LLINK, y RLINK.

void Aleph::tree_postorder_traversal	(	Node *	root,
		void(*)(Node *, int, int)	visitFct
	)			[inline]

tree_postorder_traversal((root,visit) realiza un recorrido prefijo sobre el árbol con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p en el árbol.
3. child_index: índice de p dentro de sus hermanos.

Parámetros:

[in]	root	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Ver también:

forest_preorder_traversal() tree_preorder_traversal()

forest_postorder_traversal()

Definición en la línea 562 del archivo tpl_tree_node.H.

void Aleph::tree_preorder_traversal	(	Node *	root,
		void(*)(Node *, int, int)	visitFct
	)			[inline]

tree_preorder_traversal((root,visit) realiza un recorrido prefijo sobre el árbol con raíz root. Si visitFct es especificado, entonces, por cada nodo visitado, se invoca la función.

La función de vista tiene la siguiente especificación:

void (*visitFct)(Node* p, int level, int pos)

Donde:

1. p: puntero al nodo actualmente visitado.
2. level: el nivel de p en el árbol.
3. child_index: índice de p dentro de sus hermanos.

Parámetros:

[in]	root	raíz del árbol a visitar.
[in]	visitFct	puntero a la función de visita.

Ver también:

forest_preorder_traversal() tree_postorder_traversal()

forest_postorder_traversal()

Excepciones:

domain_error

si root no es un nodo raíz de un árbol.

Definición en la línea 479 del archivo tpl_tree_node.H.