Classes
class	Aleph::Huffman_Encoder_Engine

class	Aleph::Huffman_Decoder_Engine

class	Aleph::ArrayHeap< T, Compare >

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

struct	Aleph::BinHeap< Key, Compare >

struct	Aleph::BinHeapVtl< Key, Compare >

class	Aleph::BinNodePrefixIterator< Node >

class	Aleph::BinNodeInfixIterator< Node >

struct	Aleph::GenBinTree< NodeType, Key, Compare >::Iterator

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

struct	Aleph::BinTree< Key, Compare >

struct	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 >

struct	Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::Iterator

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

struct	Aleph::Rand_Tree< Key, Compare >

struct	Aleph::Rand_Tree_Vtl< Key, Compare >

struct	Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::Iterator

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

struct	Aleph::Rb_Tree< Key, Compare >

struct	Aleph::Rb_Tree_Vtl< Key, Compare >

struct	GenTdSplayTree< NodeType, Key, Compare >::Iterator

class	Aleph::Tree_Iterator< Tree_Type >

struct	Aleph::Gen_Treap< NodeType, Key, Compare >::Iterator

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

struct	Aleph::Treap< Key, Compare >

struct	Aleph::Treap_Vtl< Key, Compare >

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

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

struct	Aleph::Treap_Rk< Key, Compare >

struct	Aleph::Treap_Rk_Vtl< Key, Compare >

class	Aleph::Tree_Node< T >

class	BinNode
	Node for binary search tree. More...

class	BinNodeXt
	Node for extended binary search tree. More...

Macros
#define	DECLARE_BINNODE(Name, height, Control_Data)

#define	DECLARE_BINNODE_SENTINEL(Name, height, Control_Data)

Functions
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 size_t n)

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

template<class Node >
Node *&	Aleph::LLINK (Node *p) noexcept

template<class Node >
Node *&	Aleph::RLINK (Node *p) noexcept

template<class Node >
Node::Key_Type &	Aleph::KEY (Node *p) noexcept

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 , class Op >
void	Aleph::for_each_in_order (Node *root, Op &&op) noexcept(noexcept(op))

template<class Node , class Op >
void	Aleph::for_each_preorder (Node *root, Op &&op)

template<class Node , class Op >
void	Aleph::for_each_postorder (Node *root, Op &&op)

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 *root) noexcept

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

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

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

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

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 (const DynArray< Key > &preorder, long l_p, long r_p, const DynArray< Key > &inorder, long l_i, long r_i)

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

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

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 (const BitArray &array, int idx=0)

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

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

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

template<class Node >
Node *	Aleph::load_tree (istream &input)

template<class Node , class Get_Key >
void	Aleph::save_tree_in_array_of_chars (Node *root, const string &array_name, ostream &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_bst (Node *p, Compare cmp=Compare())

template<class Node >
Node *	Aleph::preorder_to_bst (DynArray< typename Node::key_type > &preorder, int l, 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=Compare()) noexcept

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

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

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

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

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

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

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

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

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

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, Compare cmp=Compare()) noexcept

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, Compare cmp=Compare()) noexcept

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

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

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

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

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

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

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

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

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

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

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, Compare cmp=Compare()) noexcept

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

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

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

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

template<class Node , class Op >
bool	Aleph::prefix_traverse (Node *root, Op op) noexcept(noexcept(op))

template<class Node , class Op >
bool	Aleph::infix_traverse (Node *root, Op op) noexcept(noexcept(op))

template<class Node >
auto &	Aleph::COUNT (Node *p) noexcept

template<class Node >
Node *	Aleph::select_rec (Node *r, const size_t i)

template<class Node >
Node *	Aleph::select_ne (Node *r, const size_t pos) noexcept

template<class Node >
Node *	Aleph::select (Node *r, const size_t pos)

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

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

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, Compare &cmp) noexcept

template<class Node , class Compare >
Node *	Aleph::insert_by_key_xt (Node &r, Node p, Compare &cmp) noexcept

template<class Node , class Compare >
Node *	Aleph::insert_dup_by_key_xt (Node &r, Node p, Compare &cmp) noexcept

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

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

template<class Node , class Compare >
Node *	Aleph::insert_root_xt (Node &root, Node p, Compare &cmp) noexcept

template<class Node , class Compare >
Node *	Aleph::insert_dup_root_xt (Node &root, Node p, Compare &cmp) noexcept

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, size_t pos)

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

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, Compare &cmp) noexcept

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

template<class Node >
bool	Aleph::check_rank_tree (Node *root) noexcept

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

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

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

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

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

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

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

std::pair< long, Node * >	Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::position (const Key &key) noexcept

std::pair< int, Node * >	Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::position (const Key &key) const noexcept

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 , class Eq >
bool	Aleph::are_tree_equal (Node t1, Node t2, Eq &eq) noexcept(noexcept(eq(t1->get_key(), t2->get_key())))

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)

template<class Node >
unsigned long &	Aleph::PRIO (Node *p) noexcept

Detailed Description

Aleph-w ( $\aleph_\omega$ ) mamages several types of trees.

General Trees and Forests

General rooted trees and forests can be specified through the class Tree_Node<T>, which defines nodes containing a generic key of type T.

Tree_Node<T> is relativelly simple but very powerful and useful for modeling problems based in general trees and resident in the memory.

Binary search trees

Aleph-w ( $\aleph_\omega$ ) support an extense variety of binary search tre types designed for managing operation on sets in $O(\lg n)$ complexity.

The main types are Avl_Tree, Splay_Tree, Rand_Tree, Treap, Treap_Rk, Rb_Tree and others.

These classes operate in function of "nodes" not of the data contained in the nodes, which allows a more powerful and functional interface, although certainly more complicated for using because the memory management is delegated to the user.

Containers classes

Managing of sets and maps based on the binary search trees metioned above could be implemented with memory management through of two general classes

DynSetTree: implement sets
DynMapTree: implement maps

For both classes you could specify the binary search tree type as template parameter and decide its performance characteristics.

Heaps

Heaps are indispensable for the good performance of many algorithms. Aleph-w ( $\aleph_\omega$ ) supports several types of heaps, whose usage is according the algorithms needs.

BinHeap: a binary heap oriented to nodes containing data. The heap type is ideal for application managing dynamic data that can belong to several heaps. The great advantage of this type is its scalability.
DynBinHeap: a version of above heap where the memory management is already done.
ArrayHeap: a heap based on a contiguous array representation. This is the fastest heap, but once decided the array size, the scale is limited.
DynArrayHeap: similar to above but uses DynArray, what gives a good trade of between performance and memory consumption.

Author: Leandro Rabindranath León (lrleon en ula punto ve)

General convention for binary trees

In Aleph-w ( $\aleph_\omega$ ) the binary trees are managed by nodes, not by the keys that these contain. Many tree operations, concretlly those modifiying them, take as parameters nodes. For example, ig you have a binary search tree of intergers and you want to insert 10, then you must first allocate the node, put it the key and then insert into the tree. Some such as:

Bintree<int>::Node * p = new Bintree<int>::Node(10);
tree.insert(p);

This usage is some complicated and tedious most of the time. However, it simplifies enormously the tree algorithms, since these do not neet to worry by memory management. Eventually, it could also simplificate the user's life and definitively improve the performance. Suppose for example that you have two trees and you need to remove a key from one and insert it into the another. In this case you could do as follows:

auto ptr = tree.remove(10); // remove node with 10 and return ptr
tree2.insert(ptr);

If the tree managed the memory, then the removal from tree1 would perform a delete. Afterward, in order to insert 10 into tree2 it would be need to allocate the node, copy it the 10 and insert it into the tree. As you see

If this sound some complicated, do not worry. Aleph-w ( $\aleph_\omega$ ) exports other interfaces that wrappes and automatize the memory management.

Extension by inheritance

Another advantage of Aleph-w ( $\aleph_\omega$ ) approach for binary trees is that it allows to extend the data contained in the nodes by inheritance. Suppose that you search by a integer value, but that you have several types of data. Consider for example Student and Professor classes, then you could do:

Professor_Node : public BinTree<int>::Node { ... };
Student_Node : public BinTree<int>::Node { ... };

Since that tree operations are by BinTree<int>::Node, you could then insert student and professors nodes, and eventually other derived types, without need of change your insertion code. Of course, specific code related to a specific class will need to cast from BinTree<int>::Node to the correspondent derived class for some operations.

Virtual Destructors

If you use the technique explained above and the derivated class is enough complex, then perhaps you need to call to the destructor of derived class when you perform delete on a node pointer. In this case, you need that the destructor of BinTree<int>::Node is virtual. In this situation you must use BinTreeVtl<int> in order to indicate that the node destructor is virtual.

The same approach is used for the remainder of binary trees: Avl, Splay, ...

This separation is desirable because if you know that do not need to call to the derived destructor, the you can save memory by using nodes with simple destructors.

Macro Definition Documentation

◆ DECLARE_BINNODE

#define DECLARE_BINNODE	(	Name,
		height,
		Control_Data
	)

Value:

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

Specify tree node for a binary tree.

DECLARE_BINNODE(Name, height, Control_Data) generates two classes of binary nodes called Name and NameVtl, respectevely. The only difference is expressed by the fact that for NameVtl its destructor is virtual.

Each node has an attribute called key, accessible through KEY(p) or p->get_key(), where p is a pointer to the node.

A binary node has two static attributes:

NullPtr which represents to the empty tree
MaxHeight: an estimated value of maximun height of tree. This value is used as helper for recursive and stack based algorithms for allocate enough stack space.

Parameters

Name	the name of class defining the node.
height	maximun height that could have the tree
Control_Data	control data according to tree type

See also: DECLARE_BINNODE_SENTINEL

◆ DECLARE_BINNODE_SENTINEL

#define DECLARE_BINNODE_SENTINEL	(	Name,
		height,
		Control_Data
	)

Value:

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

Specify tree node for a binary tree.

DECLARE_BINNODE_SENTINEL(Name, height, Control_Data) generates two classes of binary nodes called Name and NameVtl, respectevely. The only difference is expressed by the fact that for NameVtl its destructor is virtual.

In this version, a special static member called sentinel_node is declared. In this context, a sentinel node is a node representing the empty tree whose state is initialized by the call to Control_Data(sentinelCtor).

Each node has an attribute called key, accessible through KEY(p) or p->get_key(), where p is a pointer to the node.

A binary node has two static attributes:

NullPtr which represents to the empty tree
MaxHeight: an estimated value of maximun height of tree. This value is used as helper for recursive and stack based algorithms for allocate enough stack space.

Parameters

Name	the name of class defining the node.
height	maximun height that could have the tree
Control_Data	control data according to tree type

See also: DECLARE_BINNODE

Function Documentation

◆ are_tree_equal()

template<class Node , class Eq >

bool Aleph::are_tree_equal	(	Node *	t1,
		Node *	t2,
		Eq &	eq
	)

inlinenoexcept

Retorna true si t1 es igual a t2

◆ bin_to_forest()

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.

Parameters

[in] broot raÃz del Ã¡rbol binario a convertir.

Returns: raÃz del primer Ã¡rbol equivalente a Ã¡rbol binario dado.

Exceptions

bad_alloc si no hay suficiente memoria.

See also: forest_to_bin()

Here is the call graph for this function:

◆ bits_to_tree()

template<class Node >

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

inline

Build a binary tree given its bits code.

bits_to_tree(array, idx) takes a bit array array and from the starting index idx builds the corresponding tree.

Parameters

[in]	array	bits array
[in]	idx	starting index

Returns: the root of equivalent binary tree

Exceptions

bad_alloc if there is no enough memory

See also: tree_to_bits() BitArray save_tree_keys_in_prefix() load_tree_keys_in_prefix()

◆ build_optimal_tree()

template<class Node , typename Key >

Node* Aleph::build_optimal_tree	(	Key	keys[],
		double	p[],
		const size_t	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[].

Parameters

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

Returns: la raÃz del Ã¡rbol binario de bÃºsqueda Ã³ptimo.

Exceptions

bad_alloc si no hay suficiente memoria.

◆ build_tree()

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

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

inline

Build a binary tree form its preorder and inorder traversals

build_tree() takes two dynamic arrays with the preorder and inorder traversal of keys and builds the correspondent tree.

Parameters

[in]	preorder	array with the preorder traversal
[in]	l_p	first index in `preorder`
[in]	r_p	last index in `preorder`
[in]	inorder	array with the preorder traversal
[in]	l_i	first index in `inorder`
[in]	r_i	last index in `inorder`

Returns: the root of built tree

Exceptions

bad_alloc if there is no enough memory

Here is the call graph for this function:

◆ check_bst()

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

bool Aleph::check_bst	(	Node *	p,
		Compare	cmp = `Compare()`
	)

inline

Return true if p is a binary search tree

Parameters

[in]	p	root of the tree
[in]	cmp	comparison criteria

Returns: true if p is a binary search tree according to Compare criteria.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ check_rank_tree()

template<class Node >

bool Aleph::check_rank_tree ( Node * root )

inlinenoexcept

Return true if root is a valid extended binary tree.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compute_cardinality_rec()

template<class Node >

size_t Aleph::compute_cardinality_rec ( Node * root )

inlinenoexcept

Count the number of nodes of a binary tree

Parameters

[in] root of tree

Returns: the number of nodes

Here is the call graph for this function:

◆ compute_height()

template<class Node >

size_t Aleph::compute_height ( Node * root )

Calcula la altura del Ã¡rbol root.

Parameters

[in] root raÃz del Ã¡rbol.

Returns: altura del Ã¡rbol en raÃz root.

◆ compute_nodes_in_level()

template<class Node >

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

inline

Count the number of nodes in a specific tree level

Parameters

[in]	root	of tre
[in]	level	desired to be counted

Returns: a list with all the nodes of level

Exceptions

bad_alloc if there is no enough memory

◆ computeHeightRec()

template<class Node >

size_t Aleph::computeHeightRec ( Node * root )

inlinenoexcept

Compute recursively the height of root

Parameters

[in] root of tree

Returns: the height

Here is the call graph for this function:

Here is the caller graph for this function:

◆ copyRec()

template<class Node >

Node* Aleph::copyRec ( Node * root )

inline

Copy recursively a tree

Parameters

[in] root of tre to be copied

Returns: a copy of tree with root

Exceptions

bad_alloc if there is no enough memory

Here is the call graph for this function:

Here is the caller graph for this function:

◆ COUNT()

template<class Node >

auto& Aleph::COUNT ( Node * p )

inlinenoexcept

Return the number of nodes of the tree fron p is root.

Parameters

p	pointer to root

Here is the call graph for this function:

Here is the caller graph for this function:

◆ destroy_forest()

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.

Parameters

[in] root raÃz del primer Ã¡rbol de la arborescencia que se desea destruir.

Exceptions

domain_error si root no es nodo raÃz del Ã¡rbol mÃ¡s a la izquierda de la arborescencia.

Here is the call graph for this function:

◆ destroy_tree()

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.

Parameters

[in] root raÃz del Ã¡rbol que se desea liberar.

Here is the caller graph for this function:

◆ destroyRec()

template<class Node >

void Aleph::destroyRec ( Node *& root )

inlinenoexcept

Free recursively all the memory occuped by the tree root

Note: It is assumed that the nodes were allocated with new operator.

Parameters

[in] root of tree to free

Here is the call graph for this function:

Here is the caller graph for this function:

◆ deway_search()

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.

Parameters

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

Returns: puntero al nodo correspondiente al nÃºmero de Deway dado; nullptr si no existe,

◆ find_max()

template<class Node >

Node* Aleph::find_max ( Node * root )

inlinenoexcept

Return the maximum key contained in a binary search tree

Parameters

[in] root of tree

Returns: pointer to node containing maximum key

Note: It is not verified if tree is empty

See also: find_max()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_min()

template<class Node >

Node* Aleph::find_min ( Node * root )

inlinenoexcept

Return the minimum key contained in a binary search tree

Parameters

[in] root of tree

Returns: pointer to node containing minimum key

Note: It is not verified if tree is empty

See also: find_max()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_position()

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,
		Compare &	cmp
	)

inlinenoexcept

Find the inorder position of a key in an extended binary search tree.

find_position(r, key, p, cmp) searches key in the tree with root r. If key is found then its inorder position is returned and a pointer to the node containing the key is written in output parameter p. Otherwise, the function returns the position that would have key if this was in the tree. At this regard, there are three cases:

if key is lesser than the minimum key of tree, then -1 is returned and p is the node with the smallest key.
If key is greater than the maximum key in the tree, then the number of keys is returned and p is the node with the maximum key in the tree.
For any other case, the returned value is the position that would have key if this was in the tree and p is the node whose key is inmediataly greater than key.

Parameters

[in]	r	root of tree
[in]	key	to be searched
[out]	p	reference to pointer to node
[in]	cmp	comparison criteria

Returns: the positions of key in the tree

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_predecessor()

template<class Node >

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

inlinenoexcept

Find the inorder predecessor of p

Parameters

[in]	p	a node pointer
[out]	pp	p's parent

Returns: predecessor of p

See also: find_successor()

Here is the call graph for this function:

◆ find_successor()

template<class Node >

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

inlinenoexcept

Find the inorder successor of p

Parameters

[in]	p	a node pointer
[out]	pp	p's parent

Returns: successor of p

See also: find_predecessor()

Here is the call graph for this function:

◆ for_each_in_order()

template<class Node , class Op >

void Aleph::for_each_in_order	(	Node *	root,
		Op &&	op
	)

inlinenoexcept

Execute an operation in order sense for each node of tree.

Parameters

[in]	root	of tree
[in]	op	operation to be executed on each node

◆ for_each_postorder()

template<class Node , class Op >

void Aleph::for_each_postorder	(	Node *	root,
		Op &&	op
	)

Execute an operation in postorder sense for each node of tree.

Parameters

[in]	root	of tree
[in]	op	operation to be executed on each node

Here is the call graph for this function:

◆ for_each_preorder()

template<class Node , class Op >

void Aleph::for_each_preorder	(	Node *	root,
		Op &&	op
	)

Execute an operation in preorder sense for each node of tree.

Parameters

[in]	root	of tree
[in]	op	operation to be executed on each node

◆ forest_postorder_traversal()

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.

Parameters

[in]	root	raÃz del Ã¡rbol a visitar.
[in]	visitFct	puntero a la funciÃ³n de visita.

See also: forest_preorder_traversal() tree_preorder_traversal(); tree_postorder_traversal()

Exceptions

domain_error si root no es nodo raÃz del Ã¡rbol mÃ¡s a la izquierda de la arborescencia.

◆ forest_preorder_traversal()

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.

Parameters

[in]	root	raÃz del Ã¡rbol primer Ã¡rbol en la arborescencia.
[in]	visitFct	puntero a la funciÃ³n de visita.

Exceptions

domain_error si root no es un nodo raÃz de un Ã¡rbol.

See also: tree_preorder_traversal() tree_postorder_traversal(); forest_postorder_traversal()

◆ forest_to_bin()

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.

Parameters

[in] root raÃz del primer Ã¡rbol perteneciente a la arborescencia a convertir.

Returns: raÃz del Ã¡rbol binario equivalente a la arborescencia dada.

Exceptions

bad_alloc si no hay suficiente memoria.

See also: bin_to_forest()

Here is the call graph for this function:

◆ generate_btree()

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.

Parameters

[in]	root	raÃz del Ã¡rbol a dibujar.
[out]	out	archivo asociado donde se desea escribir la especificaciÃ³n de dibujado.

See also: generate_tree()

◆ generate_forest()

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.

Parameters

[in]	root	raÃz del Ã¡rbol a dibujar.
[out]	out	archivo asociado donde se desea escribir la especificaciÃ³n de dibujado.

See also: generate_tree()

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

Parameters

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

See also: generate_forest()

◆ huffman_to_btreepic()

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

Genera una especificaciÃ³n para btreepic de un Ã¡rbol de Huffman.

Here is the call graph for this function:

◆ infix()

template<class Node >

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

Return a list with inorder traversal of a tree

Parameters

[in] root of tree

Returns: a list of nodes sorted by inorder traversal

Exceptions

bad_alloc if there is no enough memory

Here is the caller graph for this function:

◆ infix_traverse()

template<class Node , class Op >

bool Aleph::infix_traverse	(	Node *	root,
		Op	op
	)

noexcept

Traverse a tree in preorder via its iterator and performs a conditioned operation on each item.

prefix_traverse(root, operation) instantiates the internal iterator of the class and traverses each item performing operation(p), where p is a node pointer.

operation must have the following signature:

bool operation(Node * p)

If operation(p) returns true then the iterator is advanced and the next item processed. Otherwise. the traversal stops.

Parameters

[in] operation to be performed on each item

Returns: true if all the nodes were visited (operation on each one always returned true) or false if the traversal was stopped because there was a false result on an item.

Exceptions

anything that could throw operation

Here is the call graph for this function:

◆ inorder_position() [1/2]

template<class Node , class Compare >

long Aleph::inorder_position	(	Node *	r,
		const typename Node::key_type &	key,
		Node *&	p,
		Compare &	cmp
	)

inlinenoexcept

Compute the inorder position of a key

Parameters

[in]	r	root of tree
[in]	key	to be searched
[out]	p	pointer to the node containing `key`
[in]	cmp	comparison criteria

Returns: inorder position of key

Here is the call graph for this function:

Here is the caller graph for this function:

◆ inorder_position() [2/2]

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

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

inlinenoexcept

Compute the inorder position of a key

Parameters

[in]	r	root of tree
[in]	key	to be searched
[out]	p	pointer to the node containing `key`

Returns: inorder position of key if this is in the tree or -1 if key is not found

Here is the call graph for this function:

◆ inOrderRec()

template<class Node >

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

inline

Traverse recursively inorder a binary tree.

inOrderRec(root,visit) performs a inorder traversal of tree rooted by root and on each node exceutes a visit function with the following signature:

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

Where:

p: pointer to visted node.
level: level of node p.
pos: ordinal indicating the visitt order

Deprecated:: Probably this function will be removed in future versions. Use the functor For_Each_In_Order or traverse() instead

Parameters

[in]	root	pointer to tree's root
[in]	visitFct	pointer to visit function

Returns: the number of nodes of tree

See also: preOrderRec() postOrderRec() For_Each_In_Order traverse()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ inOrderThreaded()

template<class Node >

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

inline

Traverse inorder a binary tree without recursion and without stack.

inOrderThreaded(root,visit) traverses inorder the binary tree by building partial threads to succesor nodes. This implicates that during the traversal the links coulld be invalid.

The visit function has the following signature:

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

Where:

p: pointer to the currently visited node
level: the level of visited node
pos: ordinal position in the inorder traversal

Parameters

[in]	root	of tree
[in]	visitFct	pointer to visit function

Returns: the number of nodes of tree

See also: preOrderThreaded()

Here is the call graph for this function:

◆ insert_by_key_xt()

template<class Node , class Compare >

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

inlinenoexcept

Insert a node in an extended binary search tree.

insert_by_key_xt(root, p, cmp) inserts the nodepin the extended binary search tree with rootr`.

Parameters

[in,out]	r	the tree root
[in]	p	the node to insert
[in]	cmp	comparison criteria

Returns: if p->get_key() is not in the tree, then p is returned (is was inserted). Otherwise it returns Node::NullPtr

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert_by_pos_xt()

template<class Node >

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

inline

Insert a node in a specific inorder position in a binary tree.

insert_by_pos_xt(r, p, pos) inserts in the position pos the node p.

Warning: According the key contained in p, the isnertion could violate the required order for a binary search tree

Parameters

[in,out]	r	root of tree
[in]	p	node to insert
[in]	pos	position to insert the node

Here is the call graph for this function:

◆ insert_dup_by_key_xt()

template<class Node , class Compare >

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

inlinenoexcept

Insert a node in an extended binary search tree without testing for duplicity

Parameters

[in,out]	r	the tree root
[in]	p	pointer to the node to be inserted
[in]	cmp	comparison criteria

Returns: the pointer p

Here is the call graph for this function:

◆ insert_dup_in_bst()

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

Node* Aleph::insert_dup_in_bst	(	Node *&	root,
		Node *	p,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Insert a node p in a binary search tree

insert_dup_in_bst(root, p) inserts the node p in the binary search tree with root. The key contained in p can be already present in the tree.

Parameters

[in,out]	root	of tree
[in]	p	pointer to the node to be inserted
[in]	cmp	comparison criteria

Returns: the pointer p

Here is the call graph for this function:

◆ insert_dup_root()

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

Node* Aleph::insert_dup_root	(	Node *&	root,
		Node *	p,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Insert node p as root of a binary search tree. The key of p can be duplicated.

Parameters

[in,out]	root	of tree
[in]	p	node to insert as root
[in]	cmp	comparison criteria

Returns: the pointer p which has became the root of tree

See also: insert_root_rec()

Here is the call graph for this function:

◆ insert_dup_root_xt()

template<class Node , class Compare >

Node* Aleph::insert_dup_root_xt	(	Node *&	root,
		Node *	p,
		Compare &	cmp
	)

inlinenoexcept

Insert a node as root of an extended binary search tree.

insert_dup_root_xt(root, p, cmp) inserts the node p as the new root of the tree root.

This insertion allows duplicates.

Parameters

[in,out]	root	of tree
[in]	p	pointer to the to insert
[in]	cmp	comparison criteria

Returns: pointer to the inserted node p that has became root

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert_in_bst()

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

Node* Aleph::insert_in_bst	(	Node *&	r,
		Node *	p,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Insert a node p in a binary search tree

insert_in_bst(root, p) inserts the node p in the binary search tree with root

Parameters

[in,out]	root	of tree.
[in]	p	pointer to the node to be inserted.
[in]	cmp	comparison criteria.

Returns: p if this was inserted; that is if p->get_key() is not in the tree; otherwise, Node::NullPtr is returned

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert_root() [1/2]

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

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

inlinenoexcept

Insert a node p as root of an extended binary search tree.

insert_root_xt(root, p) inserts as root in the extended binary search tree root the node p. After insertion, if there is no duplicated key, p becomes the root of the tree.

Parameters

[in,out]	root	of tree
[in]	p	pointer to the node to insert

Returns: if the key contained in p is not in tree, then returns p, since this was inserted and has became the root. Otherwise, it returns Node::NullPtr

Here is the call graph for this function:

◆ insert_root() [2/2]

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

Node* Aleph::insert_root	(	Node *&	root,
		Node *	p,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Insert the node p as root of a binary search tree

insert_root(root, p, cmp) inserts in the tree root the node p. After insertion, p becomes the new root of tree.

Parameters

[in,out]	root	of binary search tree
[in]	p	pointer to node to insert
[in]	cmp	comparison criteria

Returns: a pointer to p if this was inserted; that is, if p->get_key() was not present in the tree. Otherwise, no insertion is done and Node::NullPtr is returned

See also: insert_root_rec()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert_root_rec()

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

Node* Aleph::insert_root_rec	(	Node *	root,
		Node *	p,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Insert a node as root in a binary search tree.

This version first insert p as a leaf of tree. Then p is rotated until the root.

Parameters

[in]	root	of tree
[in]	p	pointer to the node to insert
[in]	cmp	comparison criteria

Returns: pointer to p if p->get_key() is not in the tree. Otherwise the function returns Node::NullPtr

See also: insert_root()

Here is the call graph for this function:

◆ insert_root_xt()

template<class Node , class Compare >

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

inlinenoexcept

Insert a node p as root of an extended binary search tree.

insert_root_xt(root, p) inserts as root in the extended binary search tree root the node p. After insertion, if there is no duplicated key, p becomes the root of the tree.

Parameters

[in,out]	root	of tree
[in]	p	pointer to the node to insert
[in]	cmp	comparison criteria

Returns: if the key contained in p is not in tree, then returns p, since this was inserted and has became the root. Otherwise, it returns Node::NullPtr

Here is the call graph for this function:

Here is the caller graph for this function:

◆ internal_path_length()

template<class Node >

size_t Aleph::internal_path_length ( Node * p )

inlinenoexcept

Compute the internal path lenght

Parameters

[in] p root of tree

Returns: the internal path lenght

Here is the caller graph for this function:

◆ join() [1/2]

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.

Parameters

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

Note: 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.

Returns: this

Here is the caller graph for this function:

◆ join() [2/2]

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

Node* Aleph::join	(	Node *	t1,
		Node *	t2,
		Node *&	dup,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Fast union of two binary search trees

join(t1, t2, dup, cmp) joins the nodes of t1 with the nodes of t2. The duplicated keys of t2 are copied in the binary search tree dup.

Parameters

[in]	t1	root of first tree
[in]	t2	root of second tree
[out]	dup	tree where the duplicated keys of t2 are put
[in]	cmp	comparison criteria

Returns: pointer to the root of resulting join

See also: join_preorder()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ join_dup()

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.

Parameters

[in] t Ã¡rbol binario de bÃºsqueda que se quiere unir a this.

Note: Luego de las llamadas el Ã¡rbol t deviene vacÃos y this deviene la uniÃ³n de ambos Ã¡rboles;

Returns: this

Here is the caller graph for this function:

◆ join_exclusive()

template<class Node >

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

inlinenoexcept

Exclusive join of two biry trees

join_exclusive(ts, tg) joins ts and ts. The exclusive sense means that all the keys of ts are lesser that all the keys of tg

Parameters

[in]	ts	tree with keys lesser than `tg`
[in]	tg	tree with keys greater than `ts`

Returns: the root of resulting joined tree

Warning: No validation about the exlcusive ranges is done

See also: remove_from_bst()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ join_exclusive_xt()

template<class Node >

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

inlinenoexcept

Exclusive union of two extended binary search trees

join_exclusive_xt(ts, tg) joins ts with tg in a tree. The trees must be exclusive in the sense that the all the keys of ts must be lesser than all the keys of tg.

Parameters

[in]	ts	extended binary search tree with keys lesser than `tg`
[in]	tg	extended binary search tree with keys greater than `tg`

See also: remove_by_key_xt()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ join_preorder()

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

Node* Aleph::join_preorder	(	Node *	t1,
		Node *	t2,
		Node *&	dup,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Union of two binary search trees

Warning: This union is $O(n \lg m)$ where n and m are the sizes of t1 and t2respectively. Use join() which is much more faster

Parameters

[in]	t1	root of first tree
[in]	t2	root of second tree
[out]	dup	root of tree where the duplicated keys will be put
[in]	cmp	comparison criteria

Returns: a pointer to the resulting root of tree

See also: join()

Here is the call graph for this function:

◆ KEY()

template<class Node >

Node::Key_Type& Aleph::KEY ( Node * p )

inlinenoexcept

Return a modifiable reference to the key stored in the node.

◆ level_traverse()

template<class Node , class Operation >

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

inline

Level traverse a tree and execute an operation

operation() must have the following signature:

bool operation(Node* p)

if the result is true then the traversal continues; otherwise it stops.

Parameters

[in]	root	of tree
[in]	operation	to execute on each visited node

Returns: true if all the nodes were visited; false otherwise

Here is the call graph for this function:

Here is the caller graph for this function:

◆ levelOrder()

template<class Node >

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

inline

Traverse a binary tree by levels.

The visit function must have the following signature:

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

Donde:

p: pointer to currently visited node
pos: ordinal indicating the visit order
is_left: true if p is a left child; false otherwise

Parameters

[in]	root	of tree
[in]	visitFct	visit function

Returns: number of visited nodes

Exceptions

bad_alloc if there is no enough memory

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LLINK()

template<class Node >

Node*& Aleph::LLINK ( Node * p )

inlinenoexcept

Return a pointer to left subtree

◆ load_tree()

template<class Node >

Node* Aleph::load_tree ( istream & input )

inline

Load and build a binary tree from a stream

load_tree(input) reads the stream input and load a binary tree previously saved with save_tree().

Parameters

[in] input stream

Returns: the root of loaded and builded binary tree

Exceptions

bad_alloc if there is no enough memory

See also: save_tree()

Here is the call graph for this function:

◆ load_tree_from_array()

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

Build a binary tree from two arrays

load_tree_from_array(bits, num_bits, keys) takes a bit array bits of num_bits, whose values of unsigned char type contain the a tree code. The code is therefore read and the tree is built. Afterward, the array keys is read and the values set to the nodes keys in preorder.

The functor Load_Key is used in order to set the node key from a array entry. Its structure must be as follows:

bool load_key(Node * p, const char * str)

The functor must take the string str, perform any needed transformation and set the key of node p. If load_key() returns true then it is assumed that the key was already set and the process advances to the next key. Otherwise, str continues to be the current key and the process advances to the next node. para el siguiente nodo en el recorrido prefijo.

Parameters

[in]	bits	array where the tree code is stored
[in]	num_bits	number of bits to be read
[in]	keys	array where the keys in preorder are stored

Returns: the tree root

Exceptions

bad_alloc if there is no enough memory

See also: save_tree_in_array_of_chars() BitArray

Here is the call graph for this function:

◆ load_tree_keys_in_prefix()

template<class Node >

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

inline

Load the keys stored in preorder from a input stream.

load_tree_keys_in_prefix(root, input) traverses recursively the tree root. For each visited node a key is loaded from the stream

Parameters

[in]	root	of tree
[in]	input	stream where are the keys in preorder

Here is the call graph for this function:

Here is the caller graph for this function:

◆ position() [1/2]

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

std::pair<long, Node*> Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::position ( const Key & key )

inlinenoexcept

Compute the inorder position of a key

Parameters

[in] key to be searched

Returns: a tuple with the position of key and a pointer to the node containing it. If key is not in the tree, then first the first value is -1.

◆ position() [2/2]

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

std::pair<int, Node*> Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::position ( const Key & key ) const

inlinenoexcept

Compute the inorder position of a key

Parameters

[in]	r	root of tree
[in]	key	to be searched

Returns: inorder position of key if this is in the tree or -1 if key is not found

◆ postOrderRec()

template<class Node >

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

inline

Traverse recursively in postorder a binary tree.

postOrderRec(root,visit) performs a inorder traversal of tree rooted by root and on each node exceutes a visit function with the following signature:

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

Where:

p: pointer to visted node.
level: level of node p.
pos: ordinal indicating the visitt order

Deprecated:: Probably this function will be removed in future versions. Use the functor For_Each_Postorder instead

Parameters

[in]	root	pointer to tree's root
[in]	visitFct	pointer to visit function

Returns: the number of nodes of tree

See also: preOrderRec() postOrderRec()

◆ prefix()

template<class Node >

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

Return a list with preorder traversal of a tree

Parameters

[in] root of tree

Returns: a list of nodes sorted by preorder traversal

Exceptions

bad_alloc if there is no enough memory

Here is the caller graph for this function:

◆ prefix_traverse()

template<class Node , class Op >

bool Aleph::prefix_traverse	(	Node *	root,
		Op	op
	)

noexcept

Traverse a tree in preorder via its iterator and performs a conditioned operation on each item.

prefix_traverse(root, operation) instantiates the internal iterator of the class and traverses each item performing operation(p), where p is a node pointer.

operation must have the following signature:

bool operation(Node * p)

If operation(p) returns true then the iterator is advanced and the next item processed. Otherwise. the traversal stops.

Parameters

[in] operation to be performed on each item

Returns: true if all the nodes were visited (operation on each one always returned true) or false if the traversal was stopped because there was a false result on an item.

Exceptions

anything that could throw operation

Here is the call graph for this function:

◆ preorder_to_bst()

template<class Node >

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

inline

Build a binary search tree from its preorder traversal

Parameters

[in]	preorder	dynamic array where the preorder traversal is found
[in]	l	lower index
[in]	r	upper index

Returns: root of resulting tree

Exceptions

bad_alloc if there is no enough memory

Here is the call graph for this function:

◆ preOrderRec()

template<class Node >

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

inline

Traverse recursively in preorder a binary tree.

preOrderRec(root,visit) performs a inorder traversal of tree rooted by root and on each node exceutes a visit function with the following signature:

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

Where:

p: pointer to visted node.
level: level of node p.
pos: ordinal indicating the visit order

Deprecated:: Probably this function will be removed in future versions. Use the functor For_Each_Preorder instead

Parameters

[in]	root	pointer to tree's root
[in]	visitFct	pointer to visit function

Returns: the number of nodes of tree

See also: preOrderRec() postOrderRec()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ preOrderThreaded()

template<class Node >

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

inline

Traverse preorder a binary tree without recursion and without stack.

preOrderThreaded(root,visit) traverses preorder the binary tree by building partial threads to succesor nodes. This implicates that during the traversal the links coulld be invalid.

The visit function has the following signature:

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

Where:

p: pointer to the currently visited node
level: the level of visited node
pos: ordinal position in the inorder traversal

Parameters

[in]	root	of tree
[in]	visitFct	pointer to visit function

Returns: the number of nodes of tree

See also: inOrderThreaded()

Here is the call graph for this function:

◆ PRIO()

template<class Node >

unsigned long& Aleph::PRIO ( Node * p )

noexcept

Return the priority of node

Here is the call graph for this function:

Here is the caller graph for this function:

◆ remove_by_key_xt()

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,
		Compare &	cmp
	)

inlinenoexcept

Remove a key of extended binary tree

remove_by_key_xt(root, key, cmp) searches in the extended binary tree root the key. If key is found, then the node containing it is removed from the tree.

Parameters

[in,out]	root	of tree
[in]	key	to search and eventually to remove
[in]	cmp	comparison criteria

Returns: if key is found, then a pointer to the removed node is returned. Otherwise the function returns Node::NullPtr

See also: join_exclusive_xt()

Here is the call graph for this function:

◆ remove_by_pos_xt()

template<class Node >

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

inline

Remove from a extended binary tree the node whose inorder position is pos.

Parameters

[in,out]	root	of tree
[in]	pos	iorder position of node to be removed

Returns: pointer to the removed node

Exceptions

out_of_range if pos is greater than the number of nodes of tree

Here is the call graph for this function:

◆ remove_from_bst()

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

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

inlinenoexcept

Remove a key from a binary search tree

Parameters

[in,out]	root	of tree
[in]	key	to remove
[in]	cmp	comparison criteria

Returns: a valid pointer to the removed node if key was found in the tree, Node::NullPtr otherwise

See also: join_exclusive()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ RLINK()

template<class Node >

Node*& Aleph::RLINK ( Node * p )

inlinenoexcept

Return the right tree of p

◆ rotate_to_left() [1/2]

template<class Node >

Node* Aleph::rotate_to_left ( Node * p )

inlinenoexcept

Rotate to the left the tree with root p

Parameters

[in] p root to rotate

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rotate_to_left() [2/2]

template<class Node >

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

inlinenoexcept

Rotate to the left the tree with root p and update its parent

Parameters

[in] p root to rotate

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rotate_to_left_xt()

template<class Node >

Node* Aleph::rotate_to_left_xt ( Node * p )

inlinenoexcept

Rotate to left the extended bianry tree with root p.

Parameters

[in] p root to rotate.

Returns: pointer to the new root.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rotate_to_right() [1/2]

template<class Node >

Node* Aleph::rotate_to_right ( Node * p )

inlinenoexcept

Rotate to the right the tree with root p

Parameters

[in] p root to rotate

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rotate_to_right() [2/2]

template<class Node >

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

inlinenoexcept

Rotate to the right the tree with root p and update its parent

Parameters

[in] p root to rotate

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rotate_to_right_xt()

template<class Node >

Node* Aleph::rotate_to_right_xt ( Node * p )

inlinenoexcept

Rotate to right the extended bianry tree with root p

Parameters

[in] p root to rotate

Returns: pointer to the new root

Here is the call graph for this function:

Here is the caller graph for this function:

◆ save_tree()

template<class Node >

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

inline

Store a binary tree in a stream

save_tree(root, output) saves the binary tree with root in the stream output. The tree could be restored through load_tree().

The operator << must overloaded for the key of node.

Parameters

[in]	root	of tree
[out]	output	stream

Exceptions

bad_alloc if there is no enough memory

See also: load_tree()

Here is the call graph for this function:

◆ save_tree_in_array_of_chars()

template<class Node , class Get_Key >

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

inline

Generate C++ array declarations for a binary tree.

save_tree_in_array_of_chars(root, array_name, output) generates two array declarations that would allow to restore the orifinal binary tree. The generated declarations would have the following form:

const unsigned char array_name_cdp[n] = { unsigned char list };

const char * array_name_k[] = { key in prefix order };

The first array is a bit arrat containing the tree code (its Lukasiewicz word). The second array contains a strinficted version of the key values that were generated through the functor Get_Key, whose structure must be as follows:

string get_key(Node * p);

The goodness of this function is to embed binary trees in C++ source code.

Parameters

[in]	root	of tree
[in]	array_name	prefix name to be added to array variables.
[out]	output	stream where the arrays should be written

See also: load_tree_from_array() BitArray

Here is the call graph for this function:

◆ save_tree_keys_in_prefix()

template<class Node >

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

inline

Store in output stream the tree keys in preorder

save_tree_keys_in_prefix(root, output) traverses recursively the tree in preorder. For each node, it saves in the stream its key.

Each visit call to functor Get_Key whose function is to extract and return a stringficated version of the key. Its signature must be as follows:

string gk(Node * p)

Parameters

[in]	root	of tree
[out]	output	stream

See also: load_tree_keys_in_prefix()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ search_deway()

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

Parameters

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

Returns: puntero al nodo contentivo de la clave key; nullptr si no existe ningÃºn nodo con clave key,

Exceptions

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

◆ search_or_insert_in_bst()

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

Node* Aleph::search_or_insert_in_bst	(	Node *&	r,
		Node *	p,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Search or insert a node in a binary search tree.

search_or_insert_in_bst(root, p, cmp) searches in root a node containing p->get_key(). If found, then this node is returned. Otherwise p is inserted and returned.

Parameters

[in,out]	r	roor of tree
[in]	p	node to search or insert
[in]	cmp	comparison criteria

Returns: p if its key was not in the tree; otherwise, a pointer containing the tree is returned.

Here is the call graph for this function:

◆ search_or_insert_root_rec()

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

Node* Aleph::search_or_insert_root_rec	(	Node *	root,
		Node *	p,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Search and eventually insert p as root in a binary search tree

Parameters

[in]	root	of tree
[in]	p	pointer to the node to eventually insert
[in]	cmp	comparison criteria

Returns: if p is inserted, then it returns p; otherwise, it returns a pointer to the tree node containing to p->get_key()

Here is the call graph for this function:

◆ search_parent()

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

inlinenoexcept

Search a key and find its node and parent.

Parameters

[in]	root	of tree
[in]	key	to search
[out]	parent	pointer to parent node if key was found. Otherwise value is undetermined
[in]	cmp	comparison criteria

Returns: a valid pointer to a node containing key if this is found; otherwise, it returns a pointer to the last visited node

See also: searchInBinTree()

Here is the call graph for this function:

◆ search_rank_parent() [1/2]

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

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

inlinenoexcept

Rank search of a key in a binary search tree.

In a binary search tree the rank search of a key consists in determining the node that would be parent of key.

search_rank_parent(root, key) searches a node containing key. If key is found, then its node is returned. Otherwise, the last visited node, that would be the parent of key if this was inserted in the tree, is returned.

Parameters

[in]	root	of general tree
[in]	key	to search

Returns: pointer to a node containing key if this node exists or the last visited node otherwise

Note: It is not verified if the tree is empty

◆ search_rank_parent() [2/2]

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

inlinenoexcept

Rank search of a key in a binary search tree.

In a binary search tree the rank search of a key consists in determining the node that would be parent of key.

search_rank_parent(root, key, cmp) searches a node containing key. If key is found, then its node is returned. Otherwise, the last visited node, that would be the parent of key if this was inserted in the tree, is returned.

Parameters

[in]	root	of general tree
[in]	key	to search
[in]	cmp	comparison criteria

Returns: pointer to a node containing key if this node exists or the last visited node otherwise

Note: It is not verified if the tree is empty

Here is the call graph for this function:

Here is the caller graph for this function:

◆ searchInBinTree()

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

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

inlinenoexcept

Search a key in a binary search tree

Parameters

[in]	root	of tree
[in]	key	to search
[in]	cmp	key comparison criteria

Returns: a valid pointer to the node containing the searched key if this was found; Node::NullPtr otherwise

Here is the call graph for this function:

Here is the caller graph for this function:

◆ select() [1/2]

template<class Node >

Node* Aleph::select	(	Node *	r,
		const size_t	pos
	)

inline

Iterative selection of a node according to inorder psoition

Parameters

[in]	r	root of tree
[in]	pos	position inorder whose node wants to be located

Returns: a pointer to the node at the inorder position pos

Exceptions

out_of_range if pos is greater or equal than the number of nodes.

See also: select_rec()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ select() [2/2]

template<class Node >

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

inline

Iterative selection of a node according to inorder psoition and determination of parent of selected node

Parameters

[in]	r	root of tree
[in]	pos	position inorder whose node wants to be located
[out]	parent	of selected node

Returns: a pointer to the node at the inorder position pos

Exceptions

out_of_range if pos is greater or equal than the number of nodes.

See also: select_rec()

Here is the call graph for this function:

◆ select_gotoup_root()

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.

Este algoritmo de selecciÃ³n es recursivo.

Parameters

[in]	root	raÃz del Ã¡rbol binario con rangos.
[in]	i	posiciÃ³n infija que se desea acceder.

Returns: puntero al nodo en la posiciÃ³n infija i el cual luego de la llamada es raÃz del Ã¡rbol binario.

Exceptions

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

See also: select() select_rec()

Here is the call graph for this function:

◆ select_ne()

template<class Node >

Node* Aleph::select_ne	(	Node *	r,
		const size_t	pos
	)

inlinenoexcept

Iterative selection of a node according to inorder position without exception.

Parameters

[in]	r	root of tree
[in]	pos	position inorder whose node wants to be located

Returns: a pointer to the node at the inorder position pos

See also: select_rec()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ select_rec()

template<class Node >

Node* Aleph::select_rec	(	Node *	r,
		const size_t	i
	)

inline

Recursively select the i-th node inorder sense.

Parameters

[in]	r	root of tree
[in]	i	position inorder sense

Returns: pointer to the i-th node

Exceptions

out_of_range if i is greater or equal than the number of nodes of overall tree

See also: select()

Here is the call graph for this function:

◆ split_key()

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,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Split a binary search tree according to a key.

split_key(root, key, l, r, cmp) splits the tree root according to key. At the end, l contains all the keays lesser than key and r all the keys greater or equal than key.

Parameters

[in,out]	root	of tree to split
[in]	key	for splitting
[out]	l	tree with keys lesser than `key`
[out]	r	tree with keys greater or equal than `key`
[in]	cmp	comparison criteria

See also: split_key_rec()

Here is the call graph for this function:

◆ split_key_dup_rec()

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,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Split a tree according to a key value

split_key_dup_rec(root, key, ts, tg, cmp) splits according to key the tree withrootand build two trees.t1contains the keys lesser thankeyandt2the keys greater or equal thankey`.

Parameters

[in,out]	root	of tre to be split
[in]	key	for splitting
[out]	ts	tree with the keys lesser than `key`
[out]	tg	tree with the keys greater or equal than `key`
[in]	cmp	comparison criteria

See also: split_key()

Here is the caller graph for this function:

◆ split_key_dup_rec_xt()

template<class Node , class Compare >

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

inlinenoexcept

Split an extended binary search tree accoding to a key which can be in the tree.

split_key__dup_rec_xt(root, key, l, r, cmp) splits a tree according a key. The key can be in the tree.

Parameters

[in,out]	root	pointer to tree root
[in]	key	for splitting
[out]	l	tree with keys lesser than `key`
[out]	r	tree with keys greater than `key`
[in]	cmp	comparison criteria

Here is the caller graph for this function:

◆ split_key_rec()

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,
		Compare	cmp = `Compare()`
	)

inlinenoexcept

Split recursively according to a key.

split_key_rec(root, key, ts, tg, cmp) splits the tree with root in two trees t1 which contain the keys lesser than key and t2 which contains the keys greater than key.

The split only is performed if key is not in the tree.

Parameters

[in,out]	root	of tree
[in]	key	for slitting
[out]	ts	tree with keys lesser than `key`
[out]	tg	tree with keys greater than `key`
[in]	cmp	comparison criteria

Returns: true if the tree wa split; that if key was not in the tree. Otherwise the split is not performed and it return false

See also: split_key()

Here is the call graph for this function:

Here is the caller graph for this function:

◆ split_key_rec_xt()

template<class Node , class Compare >

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

inlinenoexcept

Split an extended binary search tree accoding to a key

split_key_rec_xt(root, key, l, r, cmp) splits a tree according a non existing key

Parameters

[in,out]	root	pointer to tree root
[in]	key	for splitting
[out]	l	tree with keys lesser than `key`
[out]	r	tree with keys greater than `key`

Returns: true if tree was split; that is if key is not in the tree. Otherwise, if key is in the tree, false is returned

Here is the call graph for this function:

Here is the caller graph for this function:

◆ split_pos_rec()

template<class Node >

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

inline

Split a extended binary tree according to a position

split_pos_rec(r, i, ts, tg) splits the tree with root r en two trees ts and tg according to a position i. ts contains the keys from 0 to i - 1 inorder sense and tg the keys from i to n - 1. After completion the original tree r becames empty.

Parameters

[in,out]	r	pointer to the root of tree
[in]	i	position for splitting
[out]	ts	tree where the rank of keys will be put
[out]	tg	tree where the rank of keys will be put

Here is the call graph for this function:

Here is the caller graph for this function:

◆ suffix()

template<class Node >

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

Return a list with postorder traversal of a tree

Parameters

[in] root of tree

Returns: a list of nodes sorted by postorder traversal

Exceptions

bad_alloc if there is no enough memory

Here is the caller graph for this function:

◆ swap_node_with_predecessor()

template<class Node >

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

inlinenoexcept

Swap a node with its predecessor inorder

Parameters

[in]	p	pointer to node to swap with predecessor
[in,out]	pp	parent of `p`
[in]	q	predecessor of `p`
[in,out]	pq	parent of `q`

See also: swap_node_with_successor()

Here is the call graph for this function:

◆ swap_node_with_successor()

template<class Node >

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

inlinenoexcept

Swap a node with its successor inorder

Parameters

[in]	p	pointer to node to swap with successor
[in,out]	pp	parent of `p`
[in]	q	successor of `p`
[in,out]	pq	parent of `q`

See also: swap_node_with_predecessor()

Here is the call graph for this function:

◆ tree_postorder_traversal()

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.

Parameters

[in]	root	raÃz del Ã¡rbol a visitar.
[in]	visitFct	puntero a la funciÃ³n de visita.

See also: forest_preorder_traversal() tree_preorder_traversal(); forest_postorder_traversal()

◆ tree_preorder_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.

Parameters

[in]	root	raÃz del Ã¡rbol a visitar.
[in]	visitFct	puntero a la funciÃ³n de visita.

See also: forest_preorder_traversal() tree_postorder_traversal(); forest_postorder_traversal()

Exceptions

domain_error si root no es un nodo raÃz de un Ã¡rbol.

◆ tree_to_bits() [1/2]

template<class Node >

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

inline

Compute a bit code for the binary tree

tree_to_bits(root, array) takes the binary tree with root and computes its prefix code (Lukasiewiczs word) in a bitarray`.

Parameters

[in]	root	the root
[out]	array	bit array where the code will be stored

Exceptions

bad_alloc if there is no enough memory

See also: bits_to_tree() BitArray save_tree_keys_in_prefix() load_tree_keys_in_prefix()

Here is the call graph for this function:

◆ tree_to_bits() [2/2]

template<class Node >

BitArray Aleph::tree_to_bits ( Node * root )

inline

Compute a bit code for the binary tree

tree_to_bits(root) takes the binary tree with root and computes its prefix code (Lukasiewicz`s word) in a bit array

Parameters

[in] root the root

Returns: array bit array with the tree code

Exceptions

bad_alloc if there is no enough memory

See also: bits_to_tree() BitArray save_tree_keys_in_prefix() load_tree_keys_in_prefix()

Here is the call graph for this function:

Here is the caller graph for this function:

Classes

Macros

Functions

Detailed Description

General Trees and Forests

Binary search trees

Containers classes

Heaps

General convention for binary trees

Extension by inheritance

Virtual Destructors

Macro Definition Documentation

◆ DECLARE_BINNODE

◆ DECLARE_BINNODE_SENTINEL

Function Documentation

◆ are_tree_equal()

◆ bin_to_forest()

◆ bits_to_tree()

◆ build_optimal_tree()

◆ build_tree()

◆ check_bst()

◆ check_rank_tree()

◆ compute_cardinality_rec()

◆ compute_height()

◆ compute_nodes_in_level()

◆ computeHeightRec()

◆ copyRec()

◆ COUNT()

◆ destroy_forest()

◆ destroy_tree()

◆ destroyRec()

◆ deway_search()

◆ find_max()

◆ find_min()

◆ find_position()

◆ find_predecessor()

◆ find_successor()

◆ for_each_in_order()

◆ for_each_postorder()

◆ for_each_preorder()

◆ forest_postorder_traversal()

◆ forest_preorder_traversal()

◆ forest_to_bin()

◆ generate_btree()

◆ generate_forest()

◆ generate_tree()

◆ huffman_to_btreepic()

◆ infix()

◆ infix_traverse()

◆ inorder_position() [1/2]

◆ inorder_position() [2/2]

◆ inOrderRec()

◆ inOrderThreaded()

◆ insert_by_key_xt()

◆ insert_by_pos_xt()

◆ insert_dup_by_key_xt()

◆ insert_dup_in_bst()

◆ insert_dup_root()

◆ insert_dup_root_xt()

◆ insert_in_bst()

◆ insert_root() [1/2]

◆ insert_root() [2/2]

◆ insert_root_rec()

◆ insert_root_xt()

◆ internal_path_length()

◆ join() [1/2]

◆ join() [2/2]

◆ join_dup()

◆ join_exclusive()

◆ join_exclusive_xt()

◆ join_preorder()

◆ KEY()

◆ level_traverse()

◆ levelOrder()

◆ LLINK()

◆ load_tree()

◆ load_tree_from_array()

◆ load_tree_keys_in_prefix()

◆ position() [1/2]

◆ position() [2/2]