Clases
class	Aleph::Huffman_Encoder_Engine

class	Aleph::Huffman_Decoder_Engine

class	Aleph::ArrayHeap< T, Compare >

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

class	Aleph::Avl_Tree< Key, Compare >

class	Aleph::Avl_Tree_Vtl< Key, Compare >

class	Aleph::GenBinHeap< NodeType, Key, Compare >

struct	Aleph::BinHeap< Key, Compare >

struct	Aleph::BinHeapVtl< Key, Compare >

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

class	Aleph::BinTree< Key, Compare >

class	Aleph::BinTreeVtl< Key, Compare >

class	Aleph::BinTree_Operation< Node, Cmp >

class	Aleph::BinTreeXt_Operation< Node, Cmp >

class	Aleph::DynArrayHeap< T, Compare >

class	Aleph::DynBinHeap< T, Compare >

class	Aleph::DynMapTree< Key, Data, Tree, Compare >

class	Aleph::DynMapBinTree< Key, Type, Compare >

class	Aleph::DynMapAvlTree< Key, Type, Compare >

class	Aleph::DynMapRbTree< Key, Type, Compare >

class	Aleph::DynMapRandTree< Key, Type, Compare >

class	Aleph::DynMapTreap< Key, Type, Compare >

class	Aleph::DynMapTreapRk< Key, Type, Compare >

class	Aleph::DynMapSplayTree< Key, Type, Compare >

class	Aleph::DynSetTree< Key, Tree, Compare >

class	Aleph::DynSetBinTree< Key, Compare >

class	Aleph::DynSetAvlTree< Key, Compare >

class	Aleph::DynSetSplayTree< Key, Compare >

class	Aleph::DynSetRandTree< Key, Compare >

class	Aleph::DynSetTreap< Key, Compare >

class	Aleph::DynSetTreapRk< Key, Compare >

class	Aleph::DynSetRbTree< Key, Compare >

class	Aleph::Gen_Rand_Tree< NodeType, Key, Compare >

class	Aleph::Rand_Tree< Key, Compare >

class	Aleph::Rand_Tree_Vtl< Key, Compare >

class	Aleph::Gen_Rb_Tree< NodeType, Key, Compare >

struct	Aleph::Rb_Tree< Key, Compare >

struct	Aleph::Rb_Tree_Vtl< Key, Compare >

class	Aleph::Tree_Iterator< Tree_Type >

class	Aleph::Gen_Treap< NodeType, Key, Compare >

class	Aleph::Treap< Key, Compare >

class	Aleph::Treap_Vtl< Key, Compare >

class	Aleph::Gen_Treap_Rk< NodeType, Key, Compare >

class	Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator

class	Aleph::Treap_Rk< Key, Compare >

class	Aleph::Treap_Rk_Vtl< Key, Compare >

class	Aleph::Tree_Node< T >

class	BinNode
	Nodo binario básico. Más...

'defines'
#define	DECLARE_BINNODE(Name, height, Control_Data)

#define	DECLARE_BINNODE_SENTINEL(Name, height, Control_Data)

#define	LLINK(p) ((p)->getL())

#define	RLINK(p) ((p)->getR())

#define	KEY(p) ((p)->get_key())

#define	COUNT(p) ((p)->getCount())

Funciones
template<typename Node , class Write = Dft_Write<Node>>
void	Aleph::generate_tree (Node *root, std::ostream &out, const int &tree_number=0)

template<typename Node , class Write = Dft_Write<Node>>
void	Aleph::generate_forest (Node *root, std::ostream &out)

template<typename Node , class Write >
void	Aleph::generate_btree (Node *root, std::ostream &out)

void	huffman_to_btreepic (Freq_Node *p, const bool with_level_adjust=false)

template<class Node , typename Key >
Node *	Aleph::build_optimal_tree (Key keys[], double p[], const int &n)

template<class Node >
Node *	Aleph::select_gotoup_root (Node *root, const size_t &i)

template<class Node >
int	Aleph::inOrderRec (Node root, void(visitFct)(Node *, int, int))

template<class Node >
int	Aleph::preOrderRec (Node root, void(visitFct)(Node *, int, int))

template<class Node >
int	Aleph::postOrderRec (Node root, void(visitFct)(Node *, int, int))

template<class Node >
size_t	Aleph::simple_preOrderStack (Node node, void(visitFct)(Node *, int, int))

template<class Node >
size_t	Aleph::preOrderStack (Node node, void(visitFct)(Node *, int, int))

template<class Node >
size_t	Aleph::inOrderStack (Node node, void(visitFct)(Node *, int, int))

template<class Node >
size_t	Aleph::postOrderStack (Node root, void(visitFct)(Node *, int, int))

template<class Node >
DynList< Node * >	Aleph::prefix (Node *root)

template<class Node >
DynList< Node * >	Aleph::infix (Node *root)

template<class Node >
DynList< Node * >	Aleph::suffix (Node *root)

template<class Node >
size_t	Aleph::compute_cardinality_rec (Node *node)

template<class Node >
size_t	Aleph::computeHeightRec (Node *node)

template<class Node >
void	Aleph::destroyRec (Node *&root)

template<class Node >
Node *	Aleph::copyRec (Node *src_root) throw (std::exception, std::bad_alloc)

template<class Node >
void	Aleph::levelOrder (Node root, void(visitFct)(Node *, int, bool), size_t queue_size)

template<class Node , class Operation >
bool	Aleph::level_traverse (Node *root, Operation &operation)

template<template< class > class Node, typename Key >
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)

template<class Node >
void	Aleph::compute_nodes_in_level (Node root, const int &level, DynDlist< Node > &list)

template<class Node >
void	Aleph::inOrderThreaded (Node root, void(visitFct)(Node *))

template<class Node >
void	Aleph::preOrderThreaded (Node node, void(visitFct)(Node *))

template<class Node >
size_t	Aleph::internal_path_length (Node *p)

template<class Node >
void	Aleph::tree_to_bits (Node *root, BitArray &array)

template<class Node >
BitArray	Aleph::tree_to_bits (Node *root)

template<class Node >
Node *	Aleph::bits_to_tree (BitArray &array, int idx=0)

template<class Node , class Get_Key >
void	Aleph::save_tree_keys_in_prefix (Node *root, ofstream &output)

template<class Node , class Load_Key >
void	Aleph::load_tree_keys_in_prefix (Node *root, ifstream &input)

template<class Node , class Get_Key >
void	Aleph::save_tree (Node *root, ofstream &output)

template<class Node , class Load_Key >
Node *	Aleph::load_tree (ifstream &input)

template<class Node , class Get_Key >
void	Aleph::save_tree_in_array_of_chars (Node *root, const string &array_name, ofstream &output)

template<class Node , class Load_Key >
Node *	Aleph::load_tree_from_array (const unsigned char bits[], const size_t &num_bits, const char *keys[])

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
bool	Aleph::check_binary_search_tree (Node *p)

template<class Node >
Node *	Aleph::preorder_to_binary_search_tree (DynArray< typename Node::key_type > &preorder, const int &l, const int &r)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::searchInBinTree (Node *root, const typename Node::key_type &key, Compare &cmp)

template<class Node >
Node *	Aleph::find_min (Node *root)

template<class Node >
Node *	Aleph::find_max (Node *root)

template<class Node >
Node *	Aleph::find_successor (Node p, Node &pp)

template<class Node >
Node *	Aleph::find_predecessor (Node p, Node &pp)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_parent (Node root, const typename Node::key_type &key, Node &parent, Compare &&cmp=Compare())

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_rank_parent (Node *root, const typename Node::key_type &key, Compare &&cmp=Compare())

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_in_binary_search_tree (Node &root, Node p)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_dup_in_binary_search_tree (Node &root, Node p)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_or_insert_in_binary_search_tree (Node &r, Node p)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
bool	Aleph::split_key_rec (Node root, const typename Node::key_type &key, Node &ts, Node *&tg)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
void	Aleph::split_key_dup_rec (Node root, const typename Node::key_type &key, Node &ts, Node *&tg)

template<class Node >
Node *	Aleph::join_exclusive (Node &ts, Node &tg)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::remove_from_search_binary_tree (Node *&root, const typename Node::key_type &key)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_root (Node &root, Node p)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_dup_root (Node &root, Node p)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::join_preorder (Node t1, Node t2, Node *&dup)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::join (Node t1, Node t2, Node *&dup)

template<class Node >
Node *	Aleph::rotate_to_right (Node *p)

template<class Node >
Node *	Aleph::rotate_to_left (Node *p)

template<class Node >
Node *	Aleph::rotate_to_left (Node p, Node pp)

template<class Node , class Key , class Compare = Aleph::less<typename Node::key_type>>
void	Aleph::split_key (Node root, const Key &key, Node &l, Node *&r)

template<class Node >
void	Aleph::swap_node_with_successor (Node p, Node &pp, Node q, Node &pq)

template<class Node >
void	Aleph::swap_node_with_predecessor (Node p, Node &pp, Node q, Node &pq)

template<class Node , class Key , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_root_rec (Node root, Node p)

template<class Node , class Key , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_or_insert_root_rec (Node root, Node p)

template<class Node >
Node *	Aleph::select_rec (Node *r, const size_t &i) throw (std::exception, std::out_of_range)

template<class Node >
Node *	Aleph::select (Node *r, const size_t &pos) throw (std::exception, std::out_of_range)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
long	Aleph::inorder_position (Node r, const typename Node::key_type &key, Node &p)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
long	Aleph::find_position (Node r, const typename Node::key_type &key, Node &p)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_by_key_xt (Node &r, Node p)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_dup_by_key_xt (Node &r, Node p)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
bool	Aleph::split_key_rec_xt (Node root, const typename Node::key_type &key, Node &l, Node *&r)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
void	Aleph::split_key_dup_rec_xt (Node root, const typename Node::key_type &key, Node &l, Node *&r)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_root_xt (Node &root, Node p)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_dup_root_xt (Node &root, Node p)

template<class Node >
void	Aleph::split_pos_rec (Node r, const size_t i, Node &ts, Node *&tg)

template<class Node >
void	Aleph::insert_by_pos_xt (Node &r, Node p, const size_t &pos)

template<class Node >
Node *	Aleph::join_exclusive_xt (Node &ts, Node &tg)

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::remove_by_key_xt (Node *&root, const typename Node::key_type &key)

template<class Node >
Node *	Aleph::remove_by_pos_xt (Node *&root, const size_t &pos)

template<class Node >
Node *	Aleph::rotate_to_right_xt (Node *p)

template<class Node >
Node *	Aleph::rotate_to_left_xt (Node *p)

DynSetTree &	Aleph::DynSetTree< Key, Tree, Compare >::join (DynSetTree &t, DynSetTree &dup)

DynSetTree &	Aleph::DynSetTree< Key, Tree, Compare >::join_dup (DynSetTree &t)

Node *	Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join_exclusive (Node tl, Node tr)

template<class Node >
void	Aleph::tree_preorder_traversal (Node root, void(visitFct)(Node *, int, int))

template<class Node >
void	Aleph::forest_preorder_traversal (Node root, void(visitFct)(Node *, int, int))

template<class Node >
void	Aleph::tree_postorder_traversal (Node root, void(visitFct)(Node *, int, int))

template<class Node >
void	Aleph::forest_postorder_traversal (Node root, void(visitFct)(Node *, int, int))

template<class Node >
void	Aleph::destroy_tree (Node *root)

template<class Node >
void	Aleph::destroy_forest (Node *root)

template<class Node >
size_t	Aleph::compute_height (Node *root)

template<class Node >
Node *	Aleph::deway_search (Node *root, int path[], const size_t &size)

template<class Node , class Equal = Aleph::equal_to<typename Node::key_type>>
Node *	Aleph::search_deway (Node *root, const typename Node::key_type &key, int deway[], const size_t &size, size_t &n)

template<class TNode , class BNode >
BNode *	Aleph::forest_to_bin (TNode *root)

template<class TNode , class BNode >
TNode *	Aleph::bin_to_forest (BNode *broot)

Descripción detallada

Árboles con raíz

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

Aleph maneja dos tipos básicos de árboles con raíz: #- Árboles generales: bajo el tipo Tree_Node. #- Á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 Rabindranath León (lrleon en ula punto ve)

Documentación de los 'defines'

#define COUNT ( p ) ((p)->getCount())

Retorna la cardinalidad del árbol con raíz p en un árbol con rangos.

Parámetros

p	puntero a un nodo con rangos.

Referenciado por Aleph::set< Node * >::empty(), Aleph::multiset< T, Compare, Tree >::empty(), Aleph::find_position(), GenTdSplayTreeRk< BinNodeXtVtl, Key, Compare >::find_position(), Aleph::BinTreeXt_Operation< Node, Cmp >::find_position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::get_current_position(), Aleph::DynSetTree< Key, Tree, Compare >::Iterator::get_current_position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::has_current(), Aleph::inorder_position(), Aleph::BinTreeXt_Operation< Node, Cmp >::inorder_position(), GenTdSplayTreeRk< BinNodeXtVtl, Key, Compare >::insert(), Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::insert(), Aleph::insert_by_key_xt(), Aleph::insert_by_pos_xt(), Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::insert_dup(), Aleph::insert_dup_by_key_xt(), Aleph::BinTreeXt_Operation< Node, Cmp >::insert_dup_root(), Aleph::insert_dup_root_xt(), Aleph::BinTreeXt_Operation< Node, Cmp >::insert_root(), Aleph::insert_root_xt(), Aleph::DynSetTree< GT::Arc *, Tree, Compare >::join(), Aleph::DynSetTree< GT::Arc *, Tree, Compare >::join_dup(), Aleph::join_exclusive_xt(), GenTdSplayTreeRk< BinNodeXtVtl, Key, Compare >::position(), Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::random_join_exclusive(), Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::random_remove(), Aleph::Gen_Treap_Rk< Treap_Rk_Node, Key, Compare >::remove(), Aleph::remove_by_key_xt(), Aleph::remove_by_pos_xt(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::reset_last(), Aleph::rotate_to_left_xt(), Aleph::rotate_to_right_xt(), Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::search_or_insert(), Aleph::select(), Aleph::select_gotoup_root(), Aleph::select_rec(), GenTdSplayTreeRk< BinNodeXtVtl, Key, Compare >::size(), Aleph::set< Node * >::size(), Aleph::map< Key, Elem, Compare, Tree >::size(), Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::size(), Aleph::Gen_Treap_Rk< Treap_Rk_Node, Key, Compare >::size(), GenTdSplayTreeRk< BinNodeXtVtl, Key, Compare >::splay(), Aleph::DynSetTree< GT::Arc *, Tree, Compare >::split_key(), Aleph::DynSetTree< GT::Arc *, Tree, Compare >::split_key_dup(), Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_dup_rec(), Aleph::split_key_dup_rec_xt(), Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_rec(), Aleph::split_key_rec_xt(), Aleph::DynSetTree< GT::Arc *, Tree, Compare >::split_pos() 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

Declara nodos binarios de nombre Name<Key>.

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:

NullPtr: es la dirección del nodo que se considera como el árbol binario vacío.
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

#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

Declara nodos binarios de nombre Name<Key> con nodos centinelas.

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:

NullPtr: es la dirección del nodo que se considera como el árbol binario vacío.
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

#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.

Documentación de las funciones

template<class TNode , class BNode >

TNode* Aleph::bin_to_forest ( BNode * broot )

inline

Convierte un árbol binario a su arborescencia equivalente.

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:

TNode: tipo de árbol basado en Tree_Node.
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()

Hace referencia a KEY.

template<class Node >

Node* Aleph::bits_to_tree	(	BitArray &	array,
		int	idx = `0`
	)

inline

Construye un árbol binario a partir de un código prefijo almacenado en un arreglo de bits.

bits_to_tree(array, idx) toma un arreglo de bits array, en cuyo índice idx comienza un código prefijo de un árbol binario, y construye el árbol binario original.

Parámetros

[in]	array	arreglo de bits contentivo del código prefijo del árbol binario a ser construido.
[in]	idx	índice del bit en array donde comienza el código prefijo.

Devuelve: puntero a la raíz del árbol binario correspondiente a la palabra prefija almacenada en el arreglo de bits.

Excepciones

std::bad_Alloc si no hay suficiente memoria para el construir el árbol. En ese caso, el árbol queda en un estado incoherente.

Ver también: tree_to_bits() BitArray save_tree_keys_in_prefix() load_tree_keys_in_prefix()

template<class Node , typename Key >

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

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.

template<template< class > class Node, typename Key >

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

Reconstruye un árbol binario a partir de sus recorridos prefijo e infijo.

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.

Hace referencia a LLINK y RLINK.

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

bool Aleph::check_binary_search_tree ( Node * p )

inline

Verifica consistencia de un árbol binario de búsqueda.

check_binary_search_tree(p) 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] p raíz del árbol binario a verificar.

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

Hace referencia a KEY, LLINK y RLINK.

template<class Node >

size_t Aleph::compute_cardinality_rec ( Node * node )

inline

Cuenta la cantidad de nodos de un árbol binario.

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.

Hace referencia a LLINK y RLINK.

template<class Node >

size_t Aleph::compute_height ( Node * root )

Calcula la altura del árbol root.

Parámetros

[in] root raíz del árbol.

Devuelve: altura del árbol en raíz root.

template<class Node >

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

inline

Calcula la cantidad de nodos que tiene un nivel.

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.

template<class Node >

size_t Aleph::computeHeightRec ( Node * node )

inline

Calcula la altura de un árbol binario.

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.

Hace referencia a LLINK y RLINK.

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::height().

Gráfico de llamadas a esta función:

template<class Node >

Node* Aleph::copyRec	(	Node *	src_root	)
throw	(	std::exception,
		std::bad_alloc
	)

inline

Copia recursiva de un árbol binario.

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.

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

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::DynSetTree(), Aleph::map< Key, Elem, Compare, Tree >::map(), Aleph::multimap< Key, T, Compare, KTree, TTree >::multimap(), Aleph::DynSetTree< GT::Arc *, Tree, Compare >::operator=(), Aleph::map< Key, Elem, Compare, Tree >::operator=(), Aleph::set< Node * >::operator=(), Aleph::multimap< Key, T, Compare, KTree, TTree >::operator=() y Aleph::set< Node * >::set().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<class Node >

void Aleph::destroy_forest ( Node * root )

inline

Destruye (libera memoria) la arborescencia cuya primer árbol es root.

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.

Hace referencia a Aleph::destroy_tree().

Gráfico de llamadas para esta función:

template<class Node >

void Aleph::destroy_tree ( Node * root )

inline

Destruye (libera memoria) el árbol cuya raíz es root.

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.

Referenciado por Aleph::destroy_forest().

Gráfico de llamadas a esta función:

template<class Node >

void Aleph::destroyRec ( Node *& root )

inline

Destrucción de un árbol binario.

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.

Hace referencia a LLINK y RLINK.

Referenciado por Aleph::multimap< Key, T, Compare, KTree, TTree >::clear(), Aleph::map< Key, Elem, Compare, Tree >::clear(), Aleph::set< Node * >::clear(), Aleph::multiset< T, Compare, Tree >::clear(), Aleph::copyRec(), Aleph::DynSetTree< GT::Arc *, Tree, Compare >::empty(), Aleph::map< Key, Elem, Compare, Tree >::erase(), Aleph::set< Node * >::erase(), Aleph::Huffman_Encoder_Engine::load_tree(), Aleph::map< Key, Elem, Compare, Tree >::operator=(), Aleph::set< Node * >::operator=(), Aleph::multiset< T, Compare, Tree >::operator=(), Aleph::multimap< Key, T, Compare, KTree, TTree >::operator=(), Aleph::DynSetTree< GT::Arc *, Tree, Compare >::~DynSetTree(), Aleph::map< Key, Elem, Compare, Tree >::~map(), Aleph::multiset< T, Compare, Tree >::~multiset() y Aleph::set< Node * >::~set().

Gráfico de llamadas a esta función:

template<class Node >

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

inline

Retorna un nodo de una arborescencia dado su número de Deway.

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,

template<class Node >

Node* Aleph::find_max ( Node * root )

inline

Encuentra el máximo elemento en un árbol binario de búsqueda.

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

Hace referencia a RLINK.

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::max().

Gráfico de llamadas a esta función:

template<class Node >

Node* Aleph::find_min ( Node * root )

inline

Encuentra el mínimo elemento en un árbol binario de búsqueda.

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

Hace referencia a LLINK.

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::min().

Gráfico de llamadas a esta función:

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

long Aleph::find_position	(	Node *	r,
		const typename Node::key_type &	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 >

Node* Aleph::find_predecessor	(	Node *	p,
		Node *&	pp
	)

inline

Encuentra el nodo predecesor infijo de p.

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

Hace referencia a LLINK y RLINK.

template<class Node >

Node* Aleph::find_successor	(	Node *	p,
		Node *&	pp
	)

inline

Encuentra el nodo sucesor infijo de p.

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

Hace referencia a LLINK y RLINK.

template<class Node >

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

inline

Recorre en sufijo una arborescencia.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p en el árbol.
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.

template<class Node >

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

inline

Recorre en prefijo una arborescencia.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p en el árbol.
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()

template<class TNode , class BNode >

BNode* Aleph::forest_to_bin ( TNode * root )

Convierte una arborescencia a su árbol binario equivalente.

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:

TNode: tipo de árbol basado en Tree_Node.
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()

Hace referencia a LLINK y RLINK.

template<typename Node , class Write >

void Aleph::generate_btree	(	Node *	root,
		std::ostream &	out
	)

Genera una entrada para el programa de dibujado de árboles binarios btrepic.

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

template<typename Node , class Write = Dft_Write<Node>>

void Aleph::generate_forest	(	Node *	root,
		std::ostream &	out
	)

Genera una entrada para el programa de dibujado de árboles ntreepic.

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

template<typename Node , class Write = Dft_Write<Node>>

void Aleph::generate_tree	(	Node *	root,
		std::ostream &	out,
		const int &	tree_number = `0`
	)

Genera una entrada para el programa de dibujado de árboles ntrepic.

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

void huffman_to_btreepic	(	Freq_Node *	p,
		const bool	with_level_adjust = `false`
	)

Genera una especificación para btreepic de un árbol de Huffman.

Hace referencia a Aleph::inOrderRec(), Aleph::levelOrder() y Aleph::preOrderRec().

Gráfico de llamadas para esta función:

template<class Node >

DynList<Node*> Aleph::infix ( Node * root )

Retorna una lista con el recorrido infijo de un árbol binario.

Parámetros

[in] root la raíz del árbol

Devuelve: una lista de punteros a nodo correspondiente al recorrido infijo

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

long Aleph::inorder_position	(	Node *	r,
		const typename Node::key_type &	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.

Referenciado por Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::position(), Aleph::Gen_Treap_Rk< Treap_Rk_Node, Key, Compare >::position() y Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::reset_to_key().

Gráfico de llamadas a esta función:

template<class Node >

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

inline

Recorre recursivamente en infijo un árbol binario.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p dentro de todo el árbol.
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()

Referenciado por huffman_to_btreepic().

Gráfico de llamadas a esta función:

template<class Node >

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

inline

Recorre en infijo un árbol binario.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p dentro de todo el árbol.
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.

Hace referencia a Aleph::count(), Aleph::ArrayStack< T >::is_empty(), LLINK, Aleph::ArrayStack< T >::pop(), Aleph::ArrayStack< T >::push(), RLINK y Aleph::ArrayStack< T >::size().

Gráfico de llamadas para esta función:

template<class Node >

void Aleph::inOrderThreaded	(	Node *	root,
		void()(Node )	visitFct
	)

inline

Recorre en infijo un árbol binario sin usar recursión o pila explícita.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p dentro de todo el árbol.
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.

Hace referencia a LLINK y RLINK.

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

Node* Aleph::insert_by_key_xt	(	Node *&	r,
		Node *	p
	)

inline

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

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

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.

Hace referencia a COUNT, KEY, LLINK y RLINK.

template<class Node >

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

inline

Inserta un nodo en un árbol binario con rangos.

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.

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

Gráfico de llamadas para esta función:

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

Node* Aleph::insert_dup_by_key_xt	(	Node *&	r,
		Node *	p
	)

inline

Inserta un nodo en un árbol binario de búsqueda con rangos por substitución de un nodo externo y con posibilidad de duplicación.

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

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

Hace referencia a COUNT, KEY, LLINK y RLINK.

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

Node* Aleph::insert_dup_in_binary_search_tree	(	Node *&	root,
		Node *	p
	)

inline

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

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

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 Compare = Aleph::less<typename Node::key_type>>

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

Ver también: insert_root_rec()

Hace referencia a KEY, LLINK y RLINK.

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

Node* Aleph::insert_dup_root_xt	(	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_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)

Hace referencia a COUNT, KEY, LLINK y RLINK.

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

Node* Aleph::insert_in_binary_search_tree	(	Node *&	root,
		Node *	p
	)

inline

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

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

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 Compare = Aleph::less<typename Node::key_type>>

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

Ver también: insert_root_rec()

Hace referencia a KEY, LLINK y RLINK.

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

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

Ver también: insert_root()

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 Compare = Aleph::less<typename Node::key_type>>

Node* Aleph::insert_root_xt	(	Node *&	root,
		Node *	p
	)

inline

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

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.

Hace referencia a COUNT, KEY, LLINK y RLINK.

template<class Node >

size_t Aleph::internal_path_length ( Node * p )

inline

Calcula la longitud del camino interno de un árbol binario.

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.

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::internal_path_length().

Gráfico de llamadas a esta función:

template<typename Key, template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

DynSetTree& Aleph::DynSetTree< Key, Tree, Compare >::join	(	DynSetTree< Key, Tree, Compare > &	t,
		DynSetTree< Key, Tree, Compare > &	dup
	)

inline

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

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

Parámetros

[in]	t	árbol binario de búsqueda que se quiere unir a this.
[out]	dup	árbol binario de búsqueda con las claves duplicadas de t.

Nota: Luego de las llamadas el árbol t deviene vacíos y this deviene la unión de ambos árboles; sin embargo los valores de t1 y t2 no se modifican.

Devuelve: this

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::join().

Gráfico de llamadas a esta función:

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

Node* Aleph::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 KEY, LLINK, Aleph::remove_from_search_binary_tree() y RLINK.

Referenciado por Relation_T< T, Compare >::join().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<typename Key, template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

DynSetTree& Aleph::DynSetTree< Key, Tree, Compare >::join_dup ( DynSetTree< Key, Tree, Compare > & t )

inline

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

join_dup(t) construye un árbol binario de búsqueda correspondiente a la unión de this con t en la cual pueden haber claves duplicadas.

Parámetros

[in] t árbol binario de búsqueda que se quiere unir a this.

Nota: Luego de las llamadas el árbol t deviene vacíos y this deviene la unión de ambos árboles;

Devuelve: this

template<class Node >

Node* Aleph::join_exclusive	(	Node *&	ts,
		Node *&	tg
	)

inline

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

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

Hace referencia a LLINK y RLINK.

Referenciado por Aleph::BinTree_Operation< Node, Cmp >::remove() y Aleph::remove_from_search_binary_tree().

Gráfico de llamadas a esta función:

template<class Node >

Node* Aleph::join_exclusive_xt	(	Node *&	ts,
		Node *&	tg
	)

inline

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

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

Hace referencia a COUNT, LLINK y RLINK.

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

Gráfico de llamadas a esta función:

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

Node* Aleph::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 LLINK y RLINK.

template<class Node , class Operation >

bool Aleph::level_traverse	(	Node *	root,
		Operation &	operation
	)

inline

Recorre por niveles un árbol binario.

levelOrder(root, op) realiza un recorrido por niveles
sobre el árbol binario con raíz root. 

La función op tiene la siguiente especificación:

bool op(Node* p)

Donde p es puntero al nodo actualmente visitado. Si la función
retorna true, el recorrido prosigue. De lo contrario el
recorrido se detiene

@param[in] root raíz del árbol a visitar.
@param[in] op operación a ejecutar sobre cada nodo
@return true si todos los nodos son recorridos; false de lo
contrario

Hace referencia a Aleph::DynListQueue< T >::get(), LLINK, Aleph::DynListQueue< T >::put() y RLINK.

Gráfico de llamadas para esta función:

template<class Node >

void Aleph::levelOrder	(	Node *	root,
		void()(Node , int, bool)	visitFct,
		size_t	queue_size
	)

inline

Recorre por niveles un árbol binario.

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:

p: puntero al nodo actualmente visitado.
pos: el ordinal de visita.
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.

Hace referencia a Aleph::ArrayQueue< T >::get(), LLINK, Aleph::ArrayQueue< T >::put() y RLINK.

Referenciado por huffman_to_btreepic().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<class Node , class Load_Key >

Node* Aleph::load_tree ( ifstream & input )

inline

Carga y construye un árbol binario desde un archivo.

load_tree(input) lee el archivo referenciado por input, el cual contiene un árbol binario previamente guardado con save_tree(), y lo restaura en memoria.

Parámetros

[in] input referencia al archivo donde se encuentra guardado el árbol binario.

Devuelve: la raíz del árbol binario leído del archivo y construido en memoria.

Excepciones

std::bad_alloc sin no hay suficiente para construir arreglo de bits intermedio o para construir el árbol binario.

Ver también: save_tree()

Hace referencia a Aleph::BitArray::load() y Aleph::prefix().

Gráfico de llamadas para esta función:

template<class Node , class Load_Key >

Node* Aleph::load_tree_from_array	(	const unsigned char	bits[],
		const size_t &	num_bits,
		const char *	keys[]
	)

inline

Lee un árbol binario de dos arreglos constantes generados.

load_tree_from_array(bits, num_bits, keys) toma un arreglo bits, de dimensión num_bits, cuyos valores de tipo unsigned char contienen los bits del código prefijo de un árbol binario. El arreglo de bits es leído y el árbol binario es construido. Luego el árbol se recorre en prefijo y, por cada nodo recorrido, el operador Load_Key()(p, str) es invocado sobre el nodo actual y una entrada del arreglo de claves keys. La función de Load_Key() es tomar la clave keys[i] y eventualmente, según como haya sido guardado el árbol, cargar la clave en el nodo. Si la clave es cargada en el nodo, entonces Load_Key() debe retornar true para indicar a la función que se debe leer la siguiente clave keys[i+1] en el arreglo. Por el contrario, si el valor retornado es false, entonces el recorrido prefijo avanza al siguiente nodo con el mismo valor de keys[i].

Load_Key() debe ser cuidadosamente especificada bajo la siguiente interfaz:

bool Load_Key::operator () (Node * p, const char * str) const

p es el nodo actual dentro del recorrido prefijo del árbol recuperado según el código de bits. str es el valor actual en keys[i] que se está leyendo. Si la operación retorna true, entonces se asume que la clave fue cargada y se avanza a la siguiente; de lo contrario, la clave str se mantiene disponible para el siguiente nodo en el recorrido prefijo.

Parámetros

[in]	bits	arreglo de unsigned char donde están almacenados los bits. Este arreglo debe haber sido generado mediante BitArray::save_in_array_of_chars() (luego de haber obtenido el código prefijo en bits del árbol binario).
[in]	num_bits	cantidad de bits del arreglo.
[in]	keys	arreglo de claves que contiene el árbol binario en orden prefijo.

Devuelve: la raíz del árbol binario leído.

Excepciones

std::bad_alloc si no hay suficiente memoria para construir el árbol.

El sentido de esta rutina es el incorporar a un programa un árbol binario que alguna forma u otra fue generado por otro programa mediante save_tree_in_array_of_chars().

Ver también: save_tree_in_array_of_chars() BitArray

Hace referencia a Aleph::BitArray::load_from_array_of_chars() y Aleph::prefix().

Gráfico de llamadas para esta función:

template<class Node , class Load_Key >

void Aleph::load_tree_keys_in_prefix	(	Node *	root,
		ifstream &	input
	)

inline

Carga desde un archivo a un árbol binario una secuencia de claves en prefijo.

load_tree_keys_in_prefix(root, input) recorre recursivamente en prefijo el árbol binario de raíz root. Por cada nodo recorrido, se invoca a la clase Load_Key()(root, input); donde input es stream contentivo de la secuencia de claves en prefijo. El rol de Load_Key es leer del stream la clave, previamente guardada por save_tree_keys_in_prefix(), y almacenar su valor en el nodo actual root.

Al terminar la llamada el árbol contiene las claves leídas de input.

Parámetros

[in]	root	raíz del árbol binario sobre el cual cargar las claves.
[in]	input	archivo donde se encuentran las claves en secuencia prefija.

Hace referencia a LLINK y RLINK.

template<class Node >

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

inline

Recorre recursivamente en sufijo un árbol binario.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p dentro de todo el árbol.
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()

template<class Node >

size_t Aleph::postOrderStack	(	Node *	root,
		void()(Node , int, int)	visitFct
	)

inline

Recorre en sufijo un árbol binario sin recursión

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:
-# p: puntero al nodo actualmente visitado.
-# level: el nivel de p dentro de todo el árbol.
-# 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.

@param[in] node raíz del árbol a visitar.
@param[in] visitFct puntero a la función de visita.
@return el número de nodos visitados.

Hace referencia a Aleph::count(), Aleph::ArrayStack< T >::is_empty(), LLINK, Aleph::ArrayStack< T >::pop(), Aleph::ArrayStack< T >::push(), RLINK y Aleph::ArrayStack< T >::size().

Gráfico de llamadas para esta función:

template<class Node >

DynList<Node*> Aleph::prefix ( Node * root )

Retorna una lista con el recorrido prefijo de un árbol binario.

Parámetros

[in] root la raíz del árbol

Devuelve: una lista de punteros a nodo correspondiente al recorrido prefijo

Referenciado por Aleph::load_tree(), Aleph::load_tree_from_array(), Aleph::save_tree() y Aleph::save_tree_in_array_of_chars().

Gráfico de llamadas a esta función:

template<class Node >

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

inline

Reconstruye un árbol binario de búsqueda a partir de su recorrido prefijo.

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.

Hace referencia a LLINK y RLINK.

template<class Node >

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

inline

Recorre recursivamente en prefijo un árbol binario.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p dentro de todo el árbol.
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()

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::for_each_in_preorder(), huffman_to_btreepic() y HtdRbTree< Key >::verifyRedBlack().

Gráfico de llamadas a esta función:

template<class Node >

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

inline

Recorre en prefijo un árbol binario.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p dentro de todo el árbol.
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()

Hace referencia a Aleph::count(), Aleph::ArrayStack< T >::is_empty(), LLINK, Aleph::ArrayStack< T >::pop(), Aleph::ArrayStack< T >::push(), RLINK y Aleph::ArrayStack< T >::size().

Gráfico de llamadas para esta función:

template<class Node >

void Aleph::preOrderThreaded	(	Node *	node,
		void()(Node )	visitFct
	)

inline

Recorre en prefijo un árbol binario sin usar recursión o pila explícita.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p dentro de todo el árbol.
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.

Hace referencia a LLINK y RLINK.

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

Node* Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join_exclusive	(	Node *	tl,
		Node *	tr
	)

inline

Unión exclusiva aleatoria de dos árboles binarios de búsqueda, exclusivos, con rangos.

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

Referenciado por Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::random_join_exclusive() y Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::random_remove().

Gráfico de llamadas a esta función:

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

Node* Aleph::remove_by_key_xt	(	Node *&	root,
		const typename Node::key_type &	key
	)

inline

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

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

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

Gráfico de llamadas para esta función:

template<class Node >

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

inline

Elimina un nodo de un árbol binario de búsqueda con rangos en la posición pos.

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

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

Gráfico de llamadas para esta función:

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

Node* Aleph::remove_from_search_binary_tree	(	Node *&	root,
		const typename Node::key_type &	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.

Referenciado por Aleph::join().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

template<class Node >

Node* Aleph::rotate_to_left ( Node * p )

inline

Rota hacia la izquierda el árbol binario con raíz p.

Hace referencia a LLINK y RLINK.

Referenciado por Aleph::BinTree_Operation< Node, Cmp >::insert_root_rec(), Aleph::Gen_Treap< TreapNode, Key, Compare >::remove(), Aleph::BinTree_Operation< Node, Cmp >::search_or_insert_root_rec() y GenTdSplayTree< BinNodeVtl, Key, Compare >::splay().

Gráfico de llamadas a esta función:

template<class Node >

Node* Aleph::rotate_to_left	(	Node *	p,
		Node *	pp
	)

inline

Rotación a la izquierda con actualización del padre.

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.

Hace referencia a LLINK y RLINK.

Referenciado por Aleph::insert_root_rec() y Aleph::search_or_insert_root_rec().

Gráfico de llamadas a esta función:

template<class Node >

Node* Aleph::rotate_to_left_xt ( Node * p )

inline

Rota hacia la izquierda el árbol binario con rangos de raíz p.

Hace referencia a COUNT, LLINK y RLINK.

Referenciado por Aleph::select_gotoup_root() y GenTdSplayTreeRk< BinNodeXtVtl, Key, Compare >::splay().

Gráfico de llamadas a esta función:

template<class Node >

Node* Aleph::rotate_to_right ( Node * p )

inline

Rota hacia la derecha el árbol binario con raíz p.

Hace referencia a LLINK y RLINK.

Referenciado por Aleph::BinTree_Operation< Node, Cmp >::insert_root_rec(), Aleph::insert_root_rec(), Aleph::Gen_Treap< TreapNode, Key, Compare >::remove(), Aleph::BinTree_Operation< Node, Cmp >::search_or_insert_root_rec(), Aleph::search_or_insert_root_rec() y GenTdSplayTree< BinNodeVtl, Key, Compare >::splay().

Gráfico de llamadas a esta función:

template<class Node >

Node* Aleph::rotate_to_right_xt ( Node * p )

inline

Rota hacia la derecha el árbol binario con rangos de raíz p.

Hace referencia a COUNT, LLINK y RLINK.

Referenciado por Aleph::select_gotoup_root() y GenTdSplayTreeRk< BinNodeXtVtl, Key, Compare >::splay().

Gráfico de llamadas a esta función:

template<class Node , class Get_Key >

void Aleph::save_tree	(	Node *	root,
		ofstream &	output
	)

inline

Guarda un árbol binario en archivo.

save_tree(root, output) almacena el árbol binario de raíz root en el archivo indicado por output. El árbol puede ser recuperado mediante load_tree().

La clase Get_Key()(root) se encarga de extraer la clave de un nodo y retornarla en tipo string; este valor de retorno es lo que se guarda en el archivo.

El método de almacenamiento consiste en almacenar el código prefijo del árbol en bits, llamada palabra de Lukasiewicz, Seguidamente se guarda la secuencia prefija de claves obtenida por las llamadas a Get_Key()(root) sobre cada nodo en prefijo. Esta técnica se considera una de las más compactas y puede reducirse por compresión

Parámetros

[in]	root	raíz del árbol binario a guardar.
[out]	output	referencia al manejador de archivo; debe estar adecuadamente abierto.

Excepciones

std::bad_alloc si no hay suficiente memoria para construir arreglo de bits intermedio.

Ver también: load_tree()

Hace referencia a Aleph::prefix(), Aleph::BitArray::save() y Aleph::tree_to_bits().

Gráfico de llamadas para esta función:

template<class Node , class Get_Key >

void Aleph::save_tree_in_array_of_chars	(	Node *	root,
		const string &	array_name,
		ofstream &	output
	)

inline

Genera declaraciones de arreglos de bits y de claves para un árbol binario.

save_tree_in_array_of_chars(root, array_name, output) genera declaraciones para dos arreglos con los que se puede definir un árbol binario. Las declaraciones son escritas en un archivo texto, ya abierto, direccionado por el stream output. La declaración resultante tiene la forma genérica siguiente:

const unsigned char array_name_cdp[n] = { lista de unsigned char };

const char * array_name_k[] = { lista de claves en prefijo };

El primer arreglo es de bits y guarda la topología del árbol bajo un código prefijo de bits (una palabra de Lukasiewicz). El segundo arreglo, guarda los contenidos de los nodos y está ordenado en la secuencia prefija. Los valores de las claves son dados por la clase Get_Key()(root, str) el cual debe retornar una constante char* que represente el contenido del nodo.

La clase Get_Key()(), observadora del contenido del nodo, debe ser muy cuidadosamente programada. Su estructura general es la siguiente:

string operator() (Node * p) const;

Donde p es el nodo actual dentro del recorrido prefijo del árbol binario. El resultado de esta llamada es colocado como valor constante del arreglo array_name.

El valor de esta rutina es el de incorporar árboles binarios ya definidos en otros programas. La declaración resultante se incluye en el programa de interés y se carga con la rutina contraparte load_tree_from_array().

Parámetros

[in]	root	La raíz del árbol binario.
[in]	array_name	El nombre del arreglo de contenidos de los nodos del árbol
[out]	output	stream abierto donde se escriben las declaraciones de los arreglos, así como sus valores.

Ver también: load_tree_from_array() BitArray

Hace referencia a Aleph::prefix(), Aleph::BitArray::save_in_array_of_chars() y Aleph::tree_to_bits().

Gráfico de llamadas para esta función:

template<class Node , class Get_Key >

void Aleph::save_tree_keys_in_prefix	(	Node *	root,
		ofstream &	output
	)

inline

Guarda en un archivo las claves en orden prefijo de un árbol binario.

save_tree_keys_in_prefix(root, output) recorre recursivamente en prefijo el árbol de raíz root. Por cada clave recorrida, se invoca a la clase Get_Key()(root, output) cuya función es extraer del nodo la clave a guardar y retornarla en un string. La secuencia de claves es almacenada en el stream output.

Parámetros

[in]	root	raíz del árbol binario cuya secuencia prefija desea guardarse en archivo.
[out]	output	un stream del archivo con la secuencia prefija almacenada.

Ver también: load_tree_keys_in_prefix()

Hace referencia a LLINK y RLINK.

template<class Node , class Equal = Aleph::equal_to<typename Node::key_type>>

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

inline

Busca key en arborescencia y calcula el número de Deway del nodo contentivo de la clave key.

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

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.

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

Node* Aleph::search_or_insert_in_binary_search_tree	(	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_in_binary_search_tree(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 Key , class Compare = Aleph::less<typename Node::key_type>>

Node* Aleph::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 Compare = Aleph::less<typename Node::key_type>>

Node* Aleph::search_parent	(	Node *	root,
		const typename Node::key_type &	key,
		Node *&	parent,
		Compare &&	cmp = `Compare()`
	)

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.

La rutina utiliza como criterio de comparación Compare()().

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).
[in]	cmp	operación de comparación.

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

Hace referencia a KEY, LLINK y RLINK.

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

Node* Aleph::search_rank_parent	(	Node *	root,
		const typename Node::key_type &	key,
		Compare &&	cmp = `Compare()`
	)

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.
[in]	cmp	operación de comparación.

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.

Hace referencia a KEY, LLINK y RLINK.

Referenciado por Aleph::set< Node * >::lower_bound() y Aleph::set< Node * >::upper_bound().

Gráfico de llamadas a esta función:

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

Node* Aleph::searchInBinTree	(	Node *	root,
		const typename Node::key_type &	key,
		Compare &	cmp
	)

inline

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

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

Parámetros

[in]	root	raíz del árbol binario.
[in]	key	clave a buscar.
[in]	cmp	operaciónd de comparación.

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

Hace referencia a KEY, LLINK y RLINK.

Referenciado por HtdRbTree< Key >::search().

Gráfico de llamadas a esta función:

template<class Node >

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

inline

Selecciona un nodo de un árbol binario según su posición infija.

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

Hace referencia a COUNT, LLINK y RLINK.

Referenciado por GenTdSplayTreeRk< BinNodeXtVtl, Key, Compare >::select(), Aleph::Gen_Rand_Tree< RandNode, std::pair< Key, Type >, Dft_Pair_Cmp< Key, Type, Compare > >::select() y Aleph::Gen_Treap_Rk< Treap_Rk_Node, Key, Compare >::select().

Gráfico de llamadas a esta función:

template<class Node >

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

inline

Selecciona un nodo de un árbol binario según su posición infija y lo convierte en su raíz.

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

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

Gráfico de llamadas para esta función:

template<class Node >

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

inline

Selecciona un nodo de un árbol binario según su posición infija.

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

Hace referencia a COUNT, LLINK y RLINK.

template<class Node >

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

inline

Recorre en prefijo un árbol binario.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p dentro de todo el árbol.
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()

Hace referencia a Aleph::count(), Aleph::ArrayStack< T >::is_empty(), LLINK, Aleph::ArrayStack< T >::pop(), Aleph::ArrayStack< T >::push(), RLINK y Aleph::ArrayStack< T >::size().

Gráfico de llamadas para esta función:

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

void Aleph::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.

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.

Hace referencia a KEY, LLINK y RLINK.

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

void Aleph::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.

Ver también: split_key()

Hace referencia a KEY, LLINK y RLINK.

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

Gráfico de llamadas a esta función:

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

void Aleph::split_key_dup_rec_xt	(	Node *	root,
		const typename Node::key_type &	key,
		Node *&	l,
		Node *&	r
	)

inline

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

split_dup_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 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 o iguales que key.

Hace referencia a COUNT, KEY, LLINK y RLINK.

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

bool Aleph::split_key_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_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()

Hace referencia a KEY, LLINK y RLINK.

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

Gráfico de llamadas a esta función:

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

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

inline

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

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.

Hace referencia a COUNT, KEY, LLINK y RLINK.

template<class Node >

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

inline

Particiona un árbol binario con rangos en la posición i.

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

Hace referencia a COUNT, LLINK y RLINK.

Referenciado por Aleph::insert_by_pos_xt(), Aleph::Gen_Treap_Rk< Treap_Rk_Node, Key, Compare >::remove() y Aleph::DynSetTree< GT::Arc *, Tree, Compare >::split_pos().

Gráfico de llamadas a esta función:

template<class Node >

DynList<Node*> Aleph::suffix ( Node * root )

Retorna una lista con el recorrido sufijo de un árbol binario.

Parámetros

[in] root la raíz del árbol

Devuelve: una lista de punteros a nodo correspondiente al recorrido sufijo

template<class Node >

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

inline

Intercambia a nivel de enlaces un nodo con su predecesor.

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

Hace referencia a LLINK y RLINK.

template<class Node >

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

inline

Intercambia a nivel de enlaces un nodo con su sucesor.

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

Hace referencia a LLINK y RLINK.

template<class Node >

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

inline

Recorre en sufijo un árbol.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p en el árbol.
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()

template<class Node >

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

inline

Recorre en prefijo un árbol.

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:

p: puntero al nodo actualmente visitado.
level: el nivel de p en el árbol.
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.

template<class Node >

void Aleph::tree_to_bits	(	Node *	root,
		BitArray &	array
	)

inline

Guarda la estructura de un árbol binario en un arreglo de bits.

tree_to_bits(root, array) toma un árbol binario de raíz root, genera el su código prefijo en bits (palabra Lukasiewicz) y lo guarda en el arreglo de bits array.

La secuencia prefija es concatenada al arreglo de bits. De este modo, es posible almacenar varios árboles en un mismo arreglo.

Parámetros

[in]	root	la raíz del árbol a guardar.
[out]	array	arreglo de bits donde se guarda el código prefijo del árbol binario.

Excepciones

std::bad_Alloc si no hay suficiente memoria para el arreglo dinámico de bits.

Ver también: bits_to_tree() BitArray save_tree_keys_in_prefix() load_tree_keys_in_prefix()

Hace referencia a LLINK, Aleph::BitArray::push(), RLINK y Aleph::tree_to_bits().

Gráfico de llamadas para esta función:

template<class Node >

BitArray Aleph::tree_to_bits ( Node * root )

inline

Retorna un arreglo de bits correspondiente al código del árbol.

 tree_to_bits(root) toma un árbol binario de raíz root,
 genera el su código prefijo en bits (palabra Lukasiewicz) y lo
 retorna en un arreglo de bits.

 @param[in] root la raíz del árbol a guardar.
 @return array arreglo de bits donde se guarda el código
 prefijo del árbol binario.
 @throw std::bad_Alloc si no hay suficiente memoria para el
 arreglo dinámico de bits.

 @see bits_to_tree() BitArray save_tree_keys_in_prefix() load_tree_keys_in_prefix()

Referenciado por Aleph::save_tree(), Aleph::save_tree_in_array_of_chars() y Aleph::tree_to_bits().

Gráfico de llamadas a esta función:

Clases

'defines'

Funciones

Descripción detallada

Documentación de los 'defines'

Documentación de las funciones