Files
file	avlNode.H
	AVL tree node with balance factor.

file	avlNodeRk.H
	AVL tree node with rank (subtree count).

file	btreepic_avl.H
	AVL tree visualization utilities.

file	generate_tree.H
	Tree visualization and output generation.

file	opBinTree.H
	Optimal Binary Search Tree construction using dynamic programming.

file	prefix-tree.H
	Trie (prefix tree) implementation.

file	random_tree.H
	Random tree generation using GSL random number generator.

file	rbNode.H
	Red-Black tree node definition and validation utilities.

file	rbNodeRk.H
	Red-Black tree node with rank (subtree count).

file	tpl_arrayHeap.H
	Fixed-capacity binary heap and heapsort algorithms.

file	tpl_avl.H
	AVL tree implementation (height-balanced BST).

file	tpl_avlRk.H
	AVL tree with rank (order statistics).

file	tpl_balanceXt.H
	Tree balancing with extended nodes.

file	tpl_binHeap.H
	Binary heap implementation using tree structure.

file	tpl_binNode.H
	Basic binary tree node definitions.

file	tpl_binNodeAux.H
	Binary tree node base definitions and declaration macros.

file	tpl_binNodeUtils.H
	Utility functions for binary tree operations.

file	tpl_binNodeXt.H
	Extended binary node with subtree count.

file	tpl_binTree.H
	Generic unbalanced binary search tree.

file	tpl_binTreeOps.H
	Binary tree operations (split, join, rotate).

file	tpl_dynArrayHeap.H
	Array-based dynamic binary heap.

file	tpl_dynBinHeap.H
	Dynamic binary heap with node-based storage.

file	tpl_dynMapTree.H
	Dynamic key-value map based on balanced binary search trees.

file	tpl_dynSetTree.H
	Dynamic set implementations based on balanced binary search trees.

file	tpl_dynSkipList.H
	Dynamic ordered set implemented with a Skip List.

file	tpl_dynTreap.H
	Dynamic treap alias.

file	tpl_nodePool.H
	Tree node memory pool allocator.

file	tpl_rand_tree.H
	Randomized binary search tree.

file	tpl_randNode.H
	Randomized tree node.

file	tpl_rb_tree.H
	Red-Black tree implementation (bottom-up balancing).

file	tpl_rbNode.H
	Red-Black node type alias.

file	tpl_rbRk.H
	Red-Black tree with rank (order statistics).

file	tpl_skipList.H
	Skip list: probabilistic sorted linked structure.

file	tpl_splay_tree.H
	Top-down splay tree implementation (without rank support).

file	tpl_splay_treeRk.H
	Top-down splay tree with rank support.

file	tpl_tdRbTree.H
	Top-down Red-Black tree implementation.

file	tpl_tdRbTreeRk.H
	Top-down Red-Black tree with rank support.

file	tpl_treap.H
	Treap: randomized BST combining tree and heap properties.

file	tpl_treapRk.H
	Treap with rank (order statistics).

file	tpl_tree_node.H
	General tree (n-ary tree) node.

file	tpl_union.H
	Union-Find (Disjoint Set Union) data structure.

file	treapNode.H
	Treap node definition with BST key and heap priority.

Classes
class	AvlNode_Data
	Data portion of an AVL tree node. More...

class	Aleph::Huffman_Encoder_Engine
	Huffman encoder. More...

struct	Aleph::Huffman_Encoder_Engine::Get_Key

struct	Aleph::Huffman_Encoder_Engine::Load_Key

class	Aleph::Huffman_Decoder_Engine
	Huffman decoder. More...

class	Aleph::Cnode
	Prefix tree (Trie) node for storing character sequences. More...

class	RandTree< T >
	Generator for uniformly random trees. More...

class	RbNode_Data
	Data portion of a Red-Black tree node. More...

class	Aleph::ArrayHeap< T, Compare >
	Fixed-capacity binary heap backed by a raw array. More...

struct	Aleph::ArrayHeap< T, Compare >::Iterator

class	Aleph::Gen_Avl_Tree< NodeType, Key, Compare >
	AVL balanced binary search tree. More...

struct	Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::Iterator
	Iterator over the nodes. More...

struct	Aleph::Avl_Tree< Key, Compare >
	AVL binary search tree with nodes without virtual destructor. More...

struct	Aleph::Avl_Tree_Vtl< Key, Compare >
	AVL binary search tree with virtual destructor in its nodes. More...

class	Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >
	AVL balanced binary search tree with rank (order statistics). More...

class	Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::Iterator
	Iterator over the nodes. More...

struct	Aleph::Avl_Tree_Rk< Key, Compare >
	AVL binary search tree with nodes without virtual destructor and with subtree counters for select/position operations. More...

struct	Aleph::Avl_Tree_Rk_Vtl< Key, Compare >
	AVL binary search tree with virtual destructor in its nodes and with subtree counters for select/position operations. More...

class	Aleph::GenBinHeap< NodeType, Key, Compare >
	Heap genérico de nodos. More...

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

struct	Aleph::BinHeap< Key, Compare >
	Node heap without virtual destructor. More...

struct	Aleph::BinHeapVtl< Key, Compare >
	Heap of nodes with virtual destroyer. More...

class	Aleph::For_Each_In_Order< Node >
	Generic inorder traversal of a binary tree. More...

class	Aleph::For_Each_Preorder< Node >
	Generic preorder traversal of a binary tree. More...

class	Aleph::For_Each_Postorder< Node >
	Generic postorder traversal of a binary tree. More...

class	Aleph::BinNodePrefixIterator< Node >
	Preorder iterator on the nodes of a binary tree. More...

class	Aleph::BinNodeInfixIterator< Node >
	Inorder iterator on the nodes of a binary tree. More...

class	Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >
	Base iterator template for ranked binary search trees. More...

class	Aleph::GenBinTree< NodeType, Key, Compare >
	Simple (unbalanced) binary search tree. More...

struct	Aleph::GenBinTree< NodeType, Key, Compare >::Iterator
	Iterator on nodes of the tree. More...

struct	Aleph::BinTree< Key, Compare >
	Binary search tree with nodes without virtual destructors,. More...

struct	Aleph::BinTreeVtl< Key, Compare >
	Binary search tree with nodes with virtual destructors,. More...

class	Aleph::BinTree_Operation< Node, Cmp >
	Functor encompassing basic operation for binary search trees. More...

class	Aleph::BinTreeXt_Operation< Node, Cmp >
	Functor encompassing basic operation for extended binary search trees. More...

class	Aleph::DynArrayHeap< T, Compare >
	Dynamic heap (priority queue) backed by `DynArray`. More...

struct	Aleph::DynArrayHeap< T, Compare >::Iterator

class	Aleph::DynBinHeap< T, Compare >
	Dynamic heap of elements of type `T` ordered by a comparison functor. More...

struct	Aleph::DynBinHeap< T, Compare >::Iterator

class	Aleph::DynMapTree< Key, Data, Tree, Compare >
	Generic key-value map implemented on top of a binary search tree. More...

class	Aleph::DynMapBinTree< Key, Type, Compare >
	Dynamic map implemented with a classic binary search tree. More...

class	Aleph::DynMapAvlTree< Key, Type, Compare >
	Dynamic map implemented with an AVL tree. More...

class	Aleph::DynMapRbTree< Key, Type, Compare >
	Dynamic map implemented with a red-black tree. More...

class	Aleph::DynMapRandTree< Key, Type, Compare >
	Dynamic map implemented with a randomized BST. More...

class	Aleph::DynMapTreap< Key, Type, Compare >
	Dynamic map implemented with a treap. More...

class	Aleph::DynMapTreapRk< Key, Type, Compare >
	Dynamic map implemented with a ranked treap. More...

class	Aleph::DynMapSplayTree< Key, Type, Compare >
	Dynamic map implemented with a splay tree. More...

class	Aleph::DynSetTree< Key, Tree, Compare >
	Dynamic set backed by balanced binary search trees with automatic memory management. More...

struct	Aleph::DynSetTree< Key, Tree, Compare >::Has_Range_Methods< T >

struct	Aleph::DynSetTree< Key, Tree, Compare >::Node_Op< Key_Op >

struct	Aleph::DynSetTree< Key, Tree, Compare >::Iterator

class	Aleph::DynSetBinTree< Key, Compare >
	Dynamic set implemented using binary search trees of type BinTree<Key>. More...

class	Aleph::DynSetAvlTree< Key, Compare >
	Dynamic set implemented using AVL binary search trees of type Avl_Tree<Key>. More...

class	Aleph::DynSetSplayTree< Key, Compare >
	Dynamic set implemented using splay binary search trees of type Splay_Tree<Key>. More...

class	Aleph::DynSetSplayRkTree< Key, Compare >
	Dynamic set implemented using splay trees with rank support of type Splay_Tree_Rk<Key>. More...

class	Aleph::DynSetSplayRkTree< Key, Compare >::Iterator

class	Aleph::DynSetRandTree< Key, Compare >
	Dynamic set implemented using randomized binary search trees of type Rand_Tree<Key>. More...

class	Aleph::DynSetRandTree< Key, Compare >::Iterator

class	Aleph::DynSetTreap< Key, Compare >
	Dynamic set implemented using randomized treap binary search trees of type Treap<Key>. More...

class	Aleph::DynSetTreapRk< Key, Compare >
	Dynamic set implemented using extended treap binary search trees with rank support of type Treap_Rk<Key>. More...

class	Aleph::DynSetTreapRk< Key, Compare >::Iterator

class	Aleph::DynSetAvlRkTree< Key, Compare >
	Dynamic set implemented using extended AVL binary search trees with rank support of type Avl_Tree_Rk<Key>. More...

class	Aleph::DynSetAvlRkTree< Key, Compare >::Iterator

class	Aleph::DynSetRbTree< Key, Compare >
	Dynamic set implemented using Red-Black binary search trees of type Rb_Tree<Key> (bottom-up implementation). More...

class	Aleph::DynSetTdRbTree< Key, Compare >
	Dynamic set implemented using Top-Down Red-Black binary search trees of type TdRbTree<Key>. More...

class	Aleph::DynSetRbRkTree< Key, Compare >
	Dynamic set implemented using extended Red-Black binary search trees with rank support of type Rb_Tree_Rk<Key> (bottom-up implementation). More...

class	Aleph::DynSetRbRkTree< Key, Compare >::Iterator

class	Aleph::DynSetTdRbRkTree< Key, Compare >
	Dynamic set implemented using Top-Down Red-Black binary search trees with rank support of type TdRbTreeRk<Key>. More...

class	Aleph::DynSetTdRbRkTree< Key, Compare >::Iterator

class	Aleph::DynSetHtdRbTree< Key, Compare >
	Dynamic set implemented using Hybrid Top-Down/Bottom-Up Red-Black trees of type HtdRbTree<Key>. More...

class	Aleph::DynSetHtdRbTree< Key, Compare >::Iterator

class	Aleph::DynSetHtdRbRkTree< Key, Compare >
	Dynamic set implemented using Hybrid Red-Black trees with rank support of type HtdRbTreeRk<Key>. More...

class	Aleph::DynSetHtdRbRkTree< Key, Compare >::Iterator

class	Aleph::HtdRbTree< Key, Compare >
	Hybrid top-down/bottom-up red-black tree. More...

struct	Aleph::HtdRbTree< Key, Compare >::Iterator
	In-order iterator. More...

class	Aleph::HtdRbTreeRk< Key, Compare >
	Hybrid top-down/bottom-up red-black tree with rank support. More...

struct	Aleph::HtdRbTreeRk< Key, Compare >::Iterator
	In-order iterator. More...

class	Aleph::Gen_Rand_Tree< NodeType, Key, Compare >
	Randomized binary search tree with rank support. More...

struct	Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::Iterator
	Iterator on nodes of the tree. More...

struct	Aleph::Rand_Tree< Key, Compare >
	Randomized binary search tree. More...

struct	Aleph::Rand_Tree_Vtl< Key, Compare >
	Randomized binary search tree. More...

class	Aleph::Gen_Rb_Tree< NodeType, Key, Compare >
	Red-black binary search tree implementation (bottom-up). More...

struct	Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::Iterator
	Iterator over tree nodes in sorted order. More...

struct	Aleph::Rb_Tree< Key, Compare >
	Red-black tree with nodes without virtual destructor. More...

struct	Aleph::Rb_Tree_Vtl< Key, Compare >
	Red-black tree with virtual destructor in nodes. More...

class	Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >
	Red-black tree with rank support (select/position operations). More...

class	Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::Iterator
	Iterator on nodes of the tree. More...

struct	Aleph::Rb_Tree_Rk< Key, Compare >
	Red-Black binary search tree with nodes without virtual destructor and with subtree counters for select/position operations. More...

struct	Aleph::Rb_Tree_Rk_Vtl< Key, Compare >
	Red-Black binary search tree with virtual destructor in its nodes and with subtree counters for select/position operations. More...

class	GenTdSplayTree< NodeType, Key, Compare >
	Top-down splay tree - Self-adjusting BST with amortized O(log n) operations. More...

struct	GenTdSplayTree< NodeType, Key, Compare >::Iterator
	Iterator over the nodes. More...

class	GenTdSplayTreeRk< NodeType, Key, Compare >
	Top-down splay tree with rank support. More...

class	GenTdSplayTreeRk< NodeType, Key, Compare >::Iterator
	Inorder iterator over the extended splay tree. More...

class	Aleph::GenTdRbTree< NodeType, Key, Compare >
	Top-down red-black binary search tree implementation. More...

struct	Aleph::GenTdRbTree< NodeType, Key, Compare >::Iterator
	Iterator over tree nodes in sorted order. More...

class	Aleph::GenTdRbTreeRk< NodeType, Key, Compare >
	Top-down red-black tree with rank support (select/position). More...

struct	Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::Iterator
	Iterator. More...

class	Aleph::Gen_Treap< NodeType, Key, Compare >
	Treap - A randomized binary search tree using heap-ordered priorities. More...

struct	Aleph::Gen_Treap< NodeType, Key, Compare >::Iterator
	Iterator on nodes of the tree. More...

struct	Aleph::Treap< Key, Compare >
	Treap (a special type of randomized binary search tree) using nodes without virtual destructor. More...

struct	Aleph::Treap_Vtl< Key, Compare >
	Treap (a special type of randomized binary search tree) using nodes with virtual destructors. More...

class	Aleph::Gen_Treap_Rk< NodeType, Key, Compare >
	Extended Treap with rank support for O(log n) indexed access. More...

class	Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator
	Iterator on nodes of the tree. More...

struct	Aleph::Treap_Rk< Key, Compare >
	Extended treap (a special type of randomized binary search tree) which manages selection and splitting for inorder position. More...

struct	Aleph::Treap_Rk_Vtl< Key, Compare >
	Extended treap (a special type of randomized binary search tree) which manages selection and splitting for inorder position. More...

class	Aleph::Tree_Node< T >
	Generic m-ary trees. More...

class	Aleph::TreapNode_Data
	Data portion of a treap node. More...

class	Aleph::BinNode< Key >
	Node for binary search tree. More...

class	Aleph::BinNodeXt< Key >
	Node for extended binary search tree. More...

Macros
#define	DECLARE_BINNODE(Name, height, Control_Data)
	Specify tree node for a binary tree.

#define	DECLARE_BINNODE_SENTINEL(Name, height, Control_Data)
	Specify tree node for a binary tree.

Functions
template<typename Node , class Write = Dft_Write<Node>>
void	Aleph::generate_tree (Node *root, std::ostream &out, const int &tree_number=0)
	Generate a tree specification for the ntreepic drawing tool.

template<typename Node , class Write = Dft_Write<Node>>
void	Aleph::generate_forest (Node *root, std::ostream &out)
	Generate a forest specification for the ntreepic drawing tool.

template<typename Node , class Write >
void	Aleph::generate_btree (Node *root, std::ostream &out)
	Generate a binary tree specification for the btreepic drawing tool.

template<class Node , typename Key >
Node *	Aleph::build_optimal_tree (Key keys[], double p[], const size_t n)
	Build an optimal binary search tree based on access probabilities.

template<class Node >
Node *	Aleph::select_gotoup_root (Node *root, const size_t &i)
	Selecciona un nodo de un árbol binario según su posición infija y lo convierte en su raíz.

template<class Node >
constexpr Node *&	Aleph::LLINK (Node *p) noexcept
	Return a pointer to left subtree.

template<class Node >
constexpr Node *&	Aleph::RLINK (Node *p) noexcept
	Return the right tree of p.

template<class Node >
constexpr Node::Key_Type &	Aleph::KEY (Node *p) noexcept
	Return a modifiable reference to the key stored in the node.

template<class Node >
int	Aleph::inOrderRec (Node root, void(visitFct)(Node *, int, int))
	Traverse recursively inorder a binary tree.

template<class Node >
int	Aleph::preOrderRec (Node root, void(visitFct)(Node *, int, int))
	Traverse recursively in preorder a binary tree.

template<class Node >
int	Aleph::postOrderRec (Node root, void(visitFct)(Node *, int, int))
	Traverse recursively in postorder a binary tree.

template<class Node , class Op >
void	Aleph::for_each_in_order (Node *root, Op &&op)
	Execute an operation in order sense for each node of tree.

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.

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.

template<class Node >
DynList< Node * >	Aleph::prefix (Node *root)
	Return a list with preorder traversal of a tree.

template<class Node >
DynList< Node * >	Aleph::infix (Node *root)
	Return a list with inorder traversal of a tree.

template<class Node >
DynList< Node * >	Aleph::suffix (Node *root)
	Return a list with postorder traversal of a tree.

template<class Node >
size_t	Aleph::compute_cardinality_rec (Node *root) noexcept
	Count the number of nodes of a binary tree.

template<class Node >
size_t	Aleph::computeHeightRec (Node *root) noexcept
	Compute recursively the height of `root`

template<class Node >
void	Aleph::destroyRec (Node *&root) noexcept
	Free recursively all the memory occupied by the tree `root`

template<class Node >
Node *	Aleph::copyRec (Node *root)
	Copy recursively a tree.

template<class Node >
void	Aleph::levelOrder (Node root, void(visitFct)(Node *, int, bool))
	Traverse a binary tree by levels.

template<class Node , class Operation >
bool	Aleph::level_traverse (Node *root, Operation &operation)
	Level traverse a tree and execute an 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)
	Build a binary tree form its preorder and inorder traversals.

template<class Node >
DynDlist< Node * >	Aleph::compute_nodes_in_level (Node *root, const int &level)
	Count the number of nodes in a specific tree level.

template<class Node >
void	Aleph::inOrderThreaded (Node root, void(visitFct)(Node *))
	Traverse inorder a binary tree without recursion and without stack.

template<class Node >
void	Aleph::preOrderThreaded (Node node, void(visitFct)(Node *))
	Traverse preorder a binary tree without recursion and without stack.

template<class Node >
size_t	Aleph::internal_path_length (Node *p) noexcept
	Compute the internal path length.

template<class Node >
void	Aleph::tree_to_bits (Node *root, BitArray &array)
	Compute a bit code for the binary tree.

template<class Node >
BitArray	Aleph::tree_to_bits (Node *root)
	Compute a bit code for the binary tree.

template<class Node >
Node *	Aleph::bits_to_tree (const BitArray &array, int idx=0)
	Build a binary tree given its bits code.

template<class Node >
void	Aleph::save_tree_keys_in_prefix (Node *root, std::ostream &output)
	Store in output stream the tree keys in preorder.

template<class Node >
void	Aleph::load_tree_keys_in_prefix (Node *root, std::istream &input)
	Load the keys stored in preorder from an input stream.

template<class Node >
void	Aleph::save_tree (Node *root, std::ostream &output)
	Store a binary tree in a stream.

template<class Node >
Node *	Aleph::load_tree (std::istream &input)
	Load and build a binary tree from a stream.

template<class Node , class Get_Key >
void	Aleph::save_tree_in_array_of_chars (Node *root, const std::string &array_name, std::ostream &output)
	Generate C++ array declarations for a binary tree.

template<class Node , class Load_Key >
Node *	Aleph::load_tree_from_array (const unsigned char bits[], const size_t &num_bits, const char *keys[])
	Build a binary tree from two arrays.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
bool	Aleph::check_bst (Node *p, const Compare &cmp=Compare())
	Return `true` if `p` is a binary search tree.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::preorder_to_bst (DynArray< typename Node::key_type > &preorder, int l, int r, const Compare &cmp=Compare())
	Build a binary search tree from its preorder traversal.

template<typename T , class Compare = Aleph::less<T>>
ThreeWayCmp	Aleph::three_way_compare (const T &a, const T &b, const Compare &cmp=Compare()) noexcept
	Three-way comparison using a binary comparator.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::searchInBinTree (Node *root, const typename Node::key_type &key, const Compare &cmp=Compare()) noexcept
	Search a key in a binary search tree.

template<class Node >
Node *	Aleph::find_min (Node *root) noexcept
	Return the minimum key contained in a binary search tree.

template<class Node >
Node *	Aleph::find_max (Node *root) noexcept
	Return the maximum key contained in a binary search tree.

template<class Node >
Node *	Aleph::find_successor (Node p, Node &pp) noexcept
	Find the inorder successor of `p`

template<class Node >
Node *	Aleph::find_predecessor (Node p, Node &pp) noexcept
	Find the inorder predecessor of `p`

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, const Compare &cmp=Compare()) noexcept
	Search a key and find its node and parent.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_rank_parent (Node *root, const typename Node::key_type &key, const Compare &cmp=Compare()) noexcept
	Rank search of a key in a binary search tree.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_in_bst (Node &r, Node p, const Compare &cmp=Compare()) noexcept
	Insert a node `p` in a binary search tree.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_dup_in_bst (Node &root, Node p, const Compare &cmp=Compare()) noexcept
	Insert a node `p` in a binary search tree.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_or_insert_in_bst (Node &r, Node p, const Compare &cmp=Compare()) noexcept
	Search or insert a node in a binary search tree.

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, const Compare &cmp=Compare()) noexcept
	Split recursively according to a key.

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, const Compare &cmp=Compare()) noexcept
	Split a tree according to a key value.

template<class Node >
Node *	Aleph::join_exclusive (Node &ts, Node &tg) noexcept
	Exclusive join of two binary trees.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::remove_from_bst (Node *&root, const typename Node::key_type &key, const Compare &cmp=Compare()) noexcept
	Remove a key from a binary search tree.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_root (Node &root, Node p, const Compare &cmp=Compare()) noexcept
	Insert the node `p` as root of a binary search tree.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_dup_root (Node &root, Node p, const Compare &cmp=Compare()) noexcept
	Insert node `p` as root of a binary search tree.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::join_preorder (Node t1, Node t2, Node *&dup, const Compare &cmp=Compare()) noexcept
	Union of two binary search trees.

template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::join (Node t1, Node t2, Node *&dup, const Compare &cmp=Compare()) noexcept
	Fast union of two binary search trees.

template<class Node >
Node *	Aleph::rotate_to_right (Node *p) noexcept
	Rotate to the right the tree with root `p`

template<class Node >
Node *	Aleph::rotate_to_right (Node p, Node pp) noexcept
	Rotate to the right the tree with root `p` and update its parent.

template<class Node >
Node *	Aleph::rotate_to_left (Node *p) noexcept
	Rotate to the left the tree with root `p`

template<class Node >
Node *	Aleph::rotate_to_left (Node p, Node pp) noexcept
	Rotate to the left the tree with root `p` and update its parent.

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, const Compare &cmp=Compare()) noexcept
	Split a binary search tree according to a key.

template<class Node >
void	Aleph::swap_node_with_successor (Node p, Node &pp, Node q, Node &pq) noexcept
	Swap a node with its successor inorder.

template<class Node >
void	Aleph::swap_node_with_predecessor (Node p, Node &pp, Node q, Node &pq) noexcept
	Swap a node with its predecessor inorder.

template<class Node , class Key = typename Node::key_type, class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_root_rec (Node root, Node p, const Compare &cmp=Compare()) noexcept
	Insert a node as root in a binary search tree.

template<class Node , class Key = typename Node::key_type, class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_or_insert_root_rec (Node root, Node p, const Compare &cmp=Compare()) noexcept
	Search and eventually insert `p` as root in a binary search tree.

template<class Node , class Op >
bool	Aleph::prefix_traverse (Node *root, Op op)
	Traverse a tree in preorder via its iterator and performs a conditioned operation on each item.

template<class Node , class Op >
bool	Aleph::infix_traverse (Node *root, Op op)
	Traverse a tree in inorder via its iterator and performs a conditioned operation on each item.

template<class Node >
auto &	Aleph::COUNT (Node *p) noexcept
	Return the number of nodes of the tree fron `p` is root.

template<class Node >
Node *	Aleph::select_rec (Node *r, const size_t i)
	Recursively select the i-th node inorder sense.

template<class Node >
Node *	Aleph::select_ne (Node *r, const size_t pos) noexcept
	Iterative selection of a node according to inorder position without exception.

template<class Node >
Node *	Aleph::select (Node *r, const size_t pos)
	Iterative selection of a node according to inorder position.

template<class Node , class Compare >
long	Aleph::inorder_position (Node r, const typename Node::key_type &key, Node &p, Compare &cmp) noexcept
	Compute the inorder position of a key.

template<class Node , class Compare >
Node *	Aleph::insert_by_key_xt (Node &r, Node p, Compare &cmp) noexcept
	Insert a node in an extended binary search tree.

template<class Node , class Compare >
Node *	Aleph::insert_dup_by_key_xt (Node &r, Node p, Compare &cmp) noexcept
	Insert a node in an extended binary search tree without testing for duplicity.

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
	Split an extended binary search tree according to a key.

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
	Split an extended binary search tree according to a key which can be in the tree.

template<class Node , class Compare >
Node *	Aleph::insert_root_xt (Node &root, Node p, Compare &cmp) noexcept
	Insert a node `p` as root of an extended binary search tree.

template<class Node , class Compare >
Node *	Aleph::insert_dup_root_xt (Node &root, Node p, Compare &cmp) noexcept
	Insert a node as root of an extended binary search tree.

template<class Node >
void	Aleph::split_pos_rec (Node &r, const size_t i, Node &ts, Node *&tg)
	Split a extended binary tree according to a position.

template<class Node >
void	Aleph::insert_by_pos_xt (Node &r, Node p, size_t pos)
	Insert a node in a specific inorder position in a binary tree.

template<class Node >
Node *	Aleph::join_exclusive_xt (Node &ts, Node &tg) noexcept
	Exclusive union of two extended binary search trees.

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
	Remove a key of extended binary tree.

template<class Node >
Node *	Aleph::remove_by_pos_xt (Node *&root, size_t pos)
	Remove from a extended binary tree the node whose inorder position is `pos`.

template<class Node >
bool	Aleph::check_rank_tree (Node *root) noexcept
	Return `true` if `root` is a valid extended binary tree.

template<class Node >
Node *	Aleph::rotate_to_right_xt (Node *p) noexcept
	Rotate to right the extended bianry tree with root `p`

template<class Node >
Node *	Aleph::rotate_to_left_xt (Node *p) noexcept
	Rotate to left the extended binary tree with root `p`.

Node *	Aleph::BinTree_Operation< Node, Cmp >::search_rank_parent (Node *root, const Key &key) noexcept
	Rank search of a key in a binary search tree.

long	Aleph::BinTreeXt_Operation< Node, Cmp >::inorder_position (Node r, const Key &key, Node &p) noexcept
	Compute the inorder position of a key.

Node *	Aleph::BinTreeXt_Operation< Node, Cmp >::insert_root (Node &root, Node p) noexcept
	Insert a node `p` as root of an extended binary search tree.

DynSetTree &	Aleph::DynSetTree< Key, Tree, Compare >::join (DynSetTree &t, DynSetTree &dup)
	Union of two binary search trees.

DynSetTree &	Aleph::DynSetTree< Key, Tree, Compare >::join_dup (DynSetTree &t)
	Union of two binary search trees.

std::pair< long, Node * >	Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::position (const Key &key) const noexcept
	Compute the inorder position of a key.

std::pair< int, Node * >	Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::position (const Key &key) const noexcept
	Compute the inorder position of a key.

template<class Node >
void	Aleph::tree_preorder_traversal (Node root, void(visitFct)(Node *, int, int))
	Preorder traversal of a tree.

template<class Node >
void	Aleph::forest_preorder_traversal (Node root, void(visitFct)(Node *, int, int))
	Preorder traversal of a forest.

template<class Node >
void	Aleph::tree_postorder_traversal (Node root, void(visitFct)(Node *, int, int))
	Postorder traversal of a tree.

template<class Node >
void	Aleph::forest_postorder_traversal (Node root, void(visitFct)(Node *, int, int))
	Postorder traversal of a forest.

template<class Node , class Eq >
bool	Aleph::are_tree_equal (Node t1, Node t2, Eq &eq)
	Returns true if t1 is equal to t2.

template<class Node >
void	Aleph::destroy_tree (Node *root)
	Destroys (frees memory) the tree whose root is root.

template<class Node >
void	Aleph::destroy_forest (Node *root)
	Destroys (frees memory) the forest whose first tree is root.

template<class Node >
size_t	Aleph::compute_height (Node *root)
	Computes the height of the tree root.

template<class Node >
Node *	Aleph::deway_search (Node *root, int path[], const size_t &size)
	Returns a node of a forest given its Dewey number.

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)
	Searches key in a forest and computes the Dewey number of the node containing the key.

template<class TNode , class BNode >
BNode *	Aleph::forest_to_bin (TNode *root)
	Converts a forest to its equivalent binary tree.

template<class TNode , class BNode >
TNode *	Aleph::bin_to_forest (BNode *broot)
	Converts a binary tree to its equivalent forest.

template<class Node >
unsigned long &	Aleph::PRIO (Node *p) noexcept
	Access the priority of a treap node.

Detailed Description

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, concretely those modifying them, take as parameters nodes. For example, ig you have a binary search tree of integers, 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 need 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 wrappers 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 derived 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, then 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 maximum 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	maximum height that could have the tree
Control_Data	control data according to tree type

See also: DECLARE_BINNODE_SENTINEL

Definition at line 255 of file tpl_binNode.H.

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

Definition at line 295 of file tpl_binNode.H.

Function Documentation

◆ are_tree_equal()

template<class Node , class Eq >

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

inline

Returns true if t1 is equal to t2.

Definition at line 962 of file tpl_tree_node.H.

References Aleph::all(), Aleph::are_tree_equal(), Aleph::eq(), Aleph::maps(), and Aleph::zipEq().

Referenced by Aleph::are_tree_equal(), and TEST().

◆ bin_to_forest()

template<class TNode , class BNode >

TNode * Aleph::bin_to_forest ( BNode * broot )

inline

Converts a binary tree to its equivalent forest.

bin_to_forest(root) takes a binary tree derived from BinNode and converts it to its equivalent forest.

The routine takes two type parameters:

TNode: tree type based on Tree_Node.
BNode: binary tree type based on BinNode.

The procedure assumes that both types share the same key type.

Parameters

[in] broot root of the binary tree to convert.

Returns: root of the first tree equivalent to the given binary tree.

Exceptions

bad_alloc if there is not enough memory.

See also: forest_to_bin()

Definition at line 1286 of file tpl_tree_node.H.

References Aleph::bin_to_tree(), KEY, and Aleph::maps().

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

Definition at line 1126 of file tpl_binNodeUtils.H.

References Aleph::maps().

Referenced by TEST().

◆ build_optimal_tree()

template<class Node , typename Key >

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

Build an optimal binary search tree based on access probabilities.

Constructs a binary search tree that minimizes the expected search cost given the access probabilities for each key. Uses dynamic programming with Knuth's optimization for O(n²) time and O(n²) space complexity.

The algorithm computes the optimal root for each subproblem [i,j] using the monotonicity property: root[i,j-1] ≤ root[i,j] ≤ root[i+1,j]

Template Parameters

Node	Binary tree node type. Must provide: `NullPtr` static member for null pointer Constructor taking a Key `LLINK(node)` and `RLINK(node)` macros for child access
Key	Key type stored in the tree nodes.

Parameters

[in]	keys	Array of n keys in sorted order (0-indexed).
[in]	p	Array of n access probabilities (0-indexed), parallel to keys. Should sum to 1.0 for proper interpretation as probabilities.
[in]	n	Number of keys.

Returns: Root of the optimal binary search tree.

Exceptions

std::bad_alloc If memory allocation fails.

Note: Keys must be in sorted order for the resulting tree to be a valid BST.; The caller is responsible for deleting the returned tree.

Author: Leandro Rabindranath León

Definition at line 191 of file opBinTree.H.

References Aleph::compute_optimal_costs(), and Aleph::maps().

◆ 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

Definition at line 763 of file tpl_binNodeUtils.H.

References ah_domain_error_if, inorder(), Aleph::LLINK(), Aleph::maps(), preorder(), Aleph::RLINK(), and root().

◆ check_bst()

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

bool Aleph::check_bst	(	Node *	p,
		const 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.

Definition at line 1402 of file tpl_binNodeUtils.H.

References cmp(), and Aleph::maps().

Referenced by Aleph::is_red_black_bst_rk(), main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), Aleph::DynSetTree< Key, Tree, Compare >::verify(), GenTdSplayTree< NodeType, Key, Compare >::verify(), and GenTdSplayTreeRk< NodeType, Key, Compare >::verify().

◆ check_rank_tree()

template<class Node >

bool Aleph::check_rank_tree ( Node * root )

inlinenoexcept

Return true if root is a valid extended binary tree.

Definition at line 907 of file tpl_binNodeXt.H.

References Aleph::check_rank_tree(), Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

Referenced by Aleph::check_rank_tree(), main(), TEST(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::verify(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::verify(), GenTdSplayTreeRk< NodeType, Key, Compare >::verify(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::verify(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::verify().

◆ compute_cardinality_rec()

template<class Node >

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

Definition at line 479 of file tpl_binNodeUtils.H.

References Aleph::compute_cardinality_rec(), Aleph::LLINK(), Aleph::RLINK(), and root().

Referenced by Aleph::compute_cardinality_rec(), Aleph::DynSetTree< Key, Tree, Compare >::join(), Aleph::DynSetTree< Key, Tree, Compare >::join_dup(), Aleph::size(), Aleph::DynSetTree< Key, Tree, Compare >::split_key(), Aleph::DynSetTree< Key, Tree, Compare >::split_key_dup(), and Aleph::DynSetTree< Key, Tree, Compare >::split_pos().

◆ compute_height()

template<class Node >

size_t Aleph::compute_height ( Node * root )

Computes the height of the tree root.

Parameters

[in] root tree root.

Returns: height of the tree rooted at root.

Definition at line 1062 of file tpl_tree_node.H.

References Aleph::compute_height(), Aleph::maps(), and root().

Referenced by Aleph::compute_height().

◆ 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

Definition at line 860 of file tpl_binNodeUtils.H.

References Aleph::compute_nodes_in_level_helper(), and root().

Referenced by south_offset(), and TEST().

◆ 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

Definition at line 503 of file tpl_binNodeUtils.H.

References Aleph::computeHeightRec(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

Referenced by benchmark_set(), compute_picture_size(), Aleph::computeHeightRec(), demonstrate_tree_types(), Aleph::DynSetTree< Key, Tree, Compare >::height(), is_avl(), Aleph::is_avl_rk(), main(), sample_tree(), set_picture_size(), write_avl(), write_bin(), write_rand(), write_rb(), write_splay(), and write_treap().

◆ 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

Definition at line 571 of file tpl_binNodeUtils.H.

References Aleph::destroyRec(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree(), and Aleph::DynSetTree< Key, Tree, Compare >::operator=().

◆ 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

Definition at line 81 of file tpl_binNodeXt.H.

◆ destroy_forest()

template<class Node >

void Aleph::destroy_forest ( Node * root )

inline

Destroys (frees memory) the forest whose first tree is root.

destroy_forest(root) frees all the memory occupied by the forest whose first tree has root as its root.

Parameters

[in] root root of the first tree of the forest to be destroyed.

Exceptions

domain_error if root is not the root node of the leftmost tree of the forest.

Definition at line 1037 of file tpl_tree_node.H.

References ah_domain_error_if, Aleph::destroy_tree(), Aleph::maps(), root(), and SIBLING_LIST.

Referenced by main(), TEST_F(), and TEST_F().

◆ destroy_tree()

template<class Node >

void Aleph::destroy_tree ( Node * root )

inline

Destroys (frees memory) the tree whose root is root.

destroy_tree(root) frees all the memory occupied by the tree whose root is root.

Parameters

[in] root root of the tree to be freed.

Definition at line 1003 of file tpl_tree_node.H.

References CHILD_LIST, Aleph::destroy_tree(), IS_UNIQUE_SIBLING, Aleph::maps(), root(), and SIBLING_LIST.

Referenced by Simple_Tree::~Simple_Tree(), Three_Trees::~Three_Trees(), Aleph::Cnode::destroy(), Aleph::destroy_forest(), Aleph::destroy_tree(), main(), read_input_and_build_tree(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ destroyRec()

template<class Node >

void Aleph::destroyRec ( Node *& root )

inlinenoexcept

Free recursively all the memory occupied by the tree root

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

Parameters

[in] root of tree to free

Definition at line 524 of file tpl_binNodeUtils.H.

References Aleph::destroyRec(), Aleph::LLINK(), Aleph::RLINK(), and root().

Referenced by Aleph::bits_to_tree_helper(), Aleph::copyRec(), Aleph::destroyRec(), Aleph::DynSetTree< Key, Tree, Compare >::empty(), Aleph::Huffman_Encoder_Engine::load_tree(), Aleph::load_tree(), main(), main(), RandTree< T >::operator()(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::operator=(), test(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), write_avl(), write_bin(), write_rand(), write_rb(), write_splay(), and write_treap().

◆ deway_search()

template<class Node >

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

inline

Returns a node of a forest given its Dewey number.

deway_search(root,path,size) takes the Dewey number stored in path, of length size, and searches in the forest whose first tree is root for the node that corresponds to the given Dewey number.

Parameters

[in]	root	root of the first tree of the forest.
[in]	path	array containing the Dewey number.
[in]	size	length of the Dewey number.

Returns: pointer to the node corresponding to the given Dewey number; nullptr if it does not exist,

Definition at line 1110 of file tpl_tree_node.H.

References Aleph::__deway_search(), root(), and Aleph::size().

Referenced by parse_deway_number().

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

Definition at line 1548 of file tpl_binNodeUtils.H.

References Aleph::maps(), Aleph::RLINK(), and root().

Referenced by east_offset(), Aleph::DynSetTree< Key, Tree, Compare >::max(), and TEST().

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

Definition at line 1529 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), and root().

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::min(), TEST(), and west_offset().

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

Definition at line 1593 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by TEST().

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

Definition at line 1567 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by TEST().

◆ for_each_in_order()

template<class Node , class Op >

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

inline

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

Definition at line 256 of file tpl_binNodeUtils.H.

References Aleph::maps(), root(), and GenericTraverse< Container >::traverse().

◆ 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

Definition at line 386 of file tpl_binNodeUtils.H.

References Aleph::maps(), root(), and GenericTraverse< Container >::traverse().

◆ 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

Definition at line 321 of file tpl_binNodeUtils.H.

References Aleph::maps(), root(), and GenericTraverse< Container >::traverse().

◆ forest_postorder_traversal()

template<class Node >

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

inline

Postorder traversal of a forest.

forest_postorder_traversal((root,visit) performs a postorder traversal over the forest whose first tree is root. If visitFct is specified, then for each visited node the function is invoked.

The visit function has the following specification:

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

Where:

p: pointer to the currently visited node.
level: the level of p in the tree.
child_index: index of p among its siblings.

Parameters

[in]	root	root of the tree to traverse.
[in]	visitFct	pointer to the visit function.

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

Exceptions

domain_error if root is not the root node of the leftmost tree of the forest.

Definition at line 944 of file tpl_tree_node.H.

References Aleph::__tree_postorder_traversal(), ah_domain_error_if, Aleph::maps(), and root().

Referenced by main().

◆ forest_preorder_traversal()

template<class Node >

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

inline

Preorder traversal of a forest.

forest_preorder_traversal((root,visit) performs a preorder traversal over the forest whose first tree is root. If visitFct is specified, then for each visited node the function is invoked.

The visit function has the following specification:

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

Where:

p: pointer to the currently visited node.
level: the level of p in the tree.
child_index: index of p among its siblings.

Parameters

[in]	root	root of the first tree in the forest.
[in]	visitFct	pointer to the visit function.

Exceptions

domain_error if root is not a root node of a tree.

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

Definition at line 867 of file tpl_tree_node.H.

References Aleph::__tree_preorder_traversal(), ah_domain_error_if, Aleph::maps(), and root().

Referenced by main().

◆ forest_to_bin()

template<class TNode , class BNode >

BNode * Aleph::forest_to_bin ( TNode * root )

Converts a forest to its equivalent binary tree.

forest_to_bin(root) takes a forest derived from Tree_Node and converts it to its equivalent binary tree.

The routine takes two type parameters:

TNode: tree type based on Tree_Node.
BNode: binary tree type based on BinNode.

The procedure assumes that both types share the same key type.

Parameters

[in] root root of the first tree belonging to the forest to convert.

Returns: root of the binary tree equivalent to the given forest.

Exceptions

bad_alloc if there is not enough memory.

See also: bin_to_forest()

Definition at line 1219 of file tpl_tree_node.H.

References Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

◆ generate_btree()

template<typename Node , class Write >

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

Generate a binary tree specification for the btreepic drawing tool.

Produces a text specification for drawing binary trees using the btreepic program. The output contains both prefix and infix traversal sequences.

Output format:

start-prefix <prefix traversal>

start_infix <infix traversal>

Aleph::maps

DynList< T > maps(const C &c, Op op)

Classic map operation.

Definition ahFunctional.H:693

Template Parameters

Node	Binary tree node type
Write	Functor that writes node content to output stream. Invoked as: `Write()(node)` during traversals

Parameters

root	Root of the binary tree to draw
out	Output stream for the drawing specification

See also: generate_tree() For general (non-binary) trees

Definition at line 207 of file generate_tree.H.

References Aleph::maps(), and root().

◆ generate_forest()

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

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

Generate a forest specification for the ntreepic drawing tool.

Produces a text specification for drawing a forest (collection of trees linked as siblings). Each tree is numbered starting from 0.

The forest is represented as siblings of the first root node:

First tree: root
Second tree: root->get_right_sibling()
And so on...

Template Parameters

Node	Tree node type (must be Tree_Node or compatible)
Write	Functor that converts node key to string for display. Must provide: `std::string operator()(Node*)`

Parameters

root	Root of the first tree in the forest
out	Output stream for the drawing specification

See also: generate_tree() For drawing a single tree

Definition at line 174 of file generate_tree.H.

References Aleph::maps(), and root().

Referenced by TEST().

◆ generate_tree()

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

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

Generate a tree specification for the ntreepic drawing tool.

Produces a text specification that can be used with the ntreepic program to generate visual representations of tree structures.

The output format uses Dewey decimal notation to identify nodes:

Root is at position 0
First child of root is 0.0, second is 0.1, etc.
Children are numbered left-to-right

Template Parameters

Node	Tree node type (must be Tree_Node or compatible)
Write	Functor that converts node key to string for display. Must provide: `std::string operator()(Node*)`

Parameters

root	Root of the tree to draw
out	Output stream for the drawing specification
tree_number	Internal use - tree index in a forest (default: 0)

See also: generate_forest() For drawing multiple trees; Dft_Write Default writer using to_str()

Definition at line 128 of file generate_tree.H.

References deway(), Aleph::maps(), Aleph::Max_Tree_Node_Depth, root(), and tree_number.

Referenced by TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ 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

Definition at line 448 of file tpl_binNodeUtils.H.

References Aleph::infix(), Aleph::maps(), and root().

◆ infix_traverse()

template<class Node , class Op >

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

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

infix_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

	root
[in]	op	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

Definition at line 2866 of file tpl_binNodeUtils.H.

References Aleph::BinNodeInfixIterator< Node >::has_curr(), Aleph::maps(), and root().

Referenced by Aleph::traverse().

◆ inorder_position() [1/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

Definition at line 616 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, Aleph::COUNT(), Aleph::BinTreeXt_Operation< Node, Cmp >::inorder_position(), KEY, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

◆ inorder_position() [2/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

Definition at line 219 of file tpl_binNodeXt.H.

References cmp(), Aleph::COUNT(), Aleph::inorder_position(), KEY, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::inorder_position(), Aleph::inorder_position(), Aleph::inorder_position(), Aleph::inorder_position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::HtdRbTreeRk< Key, Compare >::position(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::position(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::position(), TEST(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::update_pos(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::update_pos().

◆ 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 an inorder traversal of tree rooted by root and on each node executes a visit function with the following signature:

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

Where:

p: pointer to visited node.
level: level of node p.
pos: ordinal indicating the visited 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()

Definition at line 97 of file tpl_binNodeUtils.H.

References Aleph::inorder_rec_helper(), Aleph::maps(), and root().

Referenced by build_tree(), huffman_to_btreepic(), main(), and write_rb().

◆ 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

See also: preOrderThreaded()

Definition at line 889 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

Referenced by TEST().

◆ insert_by_key_xt()

template<class Node , class Compare >

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

Definition at line 353 of file tpl_binNodeXt.H.

References cmp(), Aleph::COUNT(), Aleph::insert_by_key_xt(), KEY, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::insert_by_key_xt(), Aleph::insert_by_key_xt(), main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ 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 to the key contained in p, the insertion 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

Definition at line 756 of file tpl_binNodeXt.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and Aleph::split_pos_rec().

Referenced by TEST().

◆ insert_dup_by_key_xt()

template<class Node , class Compare >

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

Definition at line 398 of file tpl_binNodeXt.H.

References cmp(), Aleph::COUNT(), Aleph::insert_dup_by_key_xt(), KEY, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::insert_dup_by_key_xt(), Aleph::insert_dup_by_key_xt(), TEST(), and TEST().

◆ 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,
		const 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

Definition at line 1746 of file tpl_binNodeUtils.H.

References cmp(), Aleph::insert_dup_in_bst(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

Referenced by Aleph::insert_dup_in_bst(), and TEST().

◆ insert_dup_root()

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

Node * Aleph::insert_dup_root	(	Node *&	root,
		Node *	p,
		const 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()

Definition at line 2018 of file tpl_binNodeUtils.H.

References cmp(), KEY, Aleph::LLINK(), Aleph::RLINK(), root(), and Aleph::split_key_dup_rec().

Referenced by TEST().

◆ insert_dup_root_xt()

template<class Node , class Compare >

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

Definition at line 657 of file tpl_binNodeXt.H.

References cmp(), Aleph::COUNT(), KEY, Aleph::LLINK(), Aleph::RLINK(), root(), and Aleph::split_key_dup_rec_xt().

Referenced by Aleph::insert_dup_root_xt(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), and TEST().

◆ insert_in_bst()

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

Node * Aleph::insert_in_bst	(	Node *&	r,
		Node *	p,
		const 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]	r	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

Definition at line 1715 of file tpl_binNodeUtils.H.

References cmp(), KEY, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::join(), Aleph::join_preorder(), main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ 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

Definition at line 798 of file tpl_binTreeOps.H.

References Aleph::COUNT(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), and Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_rec().

Referenced by Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert().

◆ insert_root() [2/2]

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

Node * Aleph::insert_root	(	Node *&	root,
		Node *	p,
		const 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()

Definition at line 1991 of file tpl_binNodeUtils.H.

References cmp(), KEY, l, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), and Aleph::split_key_rec().

Referenced by Aleph::join(), main(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_search_or_insert(), and TEST().

◆ insert_root_rec()

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

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

inlinenoexcept

Insert a node as root in a binary search tree.

This version first inserts p as a leaf of a 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()

Definition at line 2391 of file tpl_binNodeUtils.H.

References cmp(), Aleph::insert_root_rec(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), Aleph::rotate_to_left(), and Aleph::rotate_to_right().

Referenced by Aleph::insert_root_rec(), TEST(), and TEST().

◆ insert_root_xt()

template<class Node , class Compare >

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 become the root. Otherwise, it returns Node::NullPtr

Definition at line 616 of file tpl_binNodeXt.H.

References cmp(), Aleph::COUNT(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), and Aleph::split_key_rec_xt().

Referenced by Aleph::insert_root_xt(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), and TEST().

◆ internal_path_length()

template<class Node >

size_t Aleph::internal_path_length ( Node * p )

inlinenoexcept

Compute the internal path length.

Parameters

[in] p root of tree

Returns: the internal path length

Definition at line 1003 of file tpl_binNodeUtils.H.

References Aleph::internal_path_length_helper().

Referenced by benchmark_set(), Aleph::DynSetTree< Key, Tree, Compare >::internal_path_length(), sample_tree(), and TEST().

◆ 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

Union of two binary search trees.

join(t,dup) builds a binary search tree corresponding to the union of this with t. Duplicate keys are inserted in dup.

Parameters

[in]	t	binary search tree to join with this.
[out]	dup	binary search tree with duplicate keys from t.

Note: After the calls, tree t becomes empty and this becomes the union of both trees.

Returns: this

Definition at line 1319 of file tpl_dynSetTree.H.

References Aleph::compute_cardinality_rec(), Aleph::DynSetTree< Key, Tree, Compare >::join(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::join(), and Aleph::DynSetTree< Key, Tree, Compare >::join().

◆ join() [2/2]

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

Node * Aleph::join	(	Node *	t1,
		Node *	t2,
		Node *&	dup,
		const 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()

Definition at line 2078 of file tpl_binNodeUtils.H.

References cmp(), Aleph::insert_in_bst(), Aleph::insert_root(), Aleph::join(), KEY, l, Aleph::LLINK(), Aleph::maps(), Aleph::remove_from_bst(), Aleph::HTList::reset(), and Aleph::RLINK().

◆ 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

Union of two binary search trees.

join_dup(t) builds a binary search tree corresponding to the union of this with t in which there may be duplicate keys.

Parameters

[in] t binary search tree that you want to join to this.

Note: After the calls the t-tree becomes empty and this becomes the union of both trees;

Returns: this

Definition at line 1355 of file tpl_dynSetTree.H.

References Aleph::compute_cardinality_rec(), Aleph::DynSetTree< Key, Tree, Compare >::join_dup(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::join_dup().

◆ join_exclusive()

template<class Node >

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

inlinenoexcept

Exclusive join of two binary 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 exclusive ranges is done

See also: remove_from_bst()

Definition at line 1924 of file tpl_binNodeUtils.H.

References Aleph::join_exclusive(), Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::join_exclusive(), Aleph::BinTree_Operation< Node, Cmp >::remove(), and Aleph::remove_from_bst().

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

Definition at line 778 of file tpl_binNodeXt.H.

References Aleph::COUNT(), Aleph::join_exclusive_xt(), Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::__remove_by_pos_xt(), Aleph::join_exclusive_xt(), Aleph::remove_by_key_xt(), and TEST().

◆ join_preorder()

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

Node * Aleph::join_preorder	(	Node *	t1,
		Node *	t2,
		Node *&	dup,
		const 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()

Definition at line 2041 of file tpl_binNodeUtils.H.

References cmp(), Aleph::insert_in_bst(), Aleph::join_preorder(), l, Aleph::LLINK(), Aleph::maps(), Aleph::HTList::reset(), and Aleph::RLINK().

Referenced by Aleph::join_preorder(), and TEST().

◆ KEY()

template<class Node >

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

inlineconstexprnoexcept

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

Definition at line 355 of file tpl_binNode.H.

◆ 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

Definition at line 717 of file tpl_binNodeUtils.H.

References Aleph::DynListQueue< T >::get(), Aleph::DynListQueue< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::DynListQueue< T >::put(), Aleph::RLINK(), and root().

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

Where:

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

Exceptions

bad_alloc if there is no enough memory

Definition at line 676 of file tpl_binNodeUtils.H.

References Aleph::DynListQueue< T >::get(), Aleph::DynListQueue< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::DynListQueue< T >::put(), Aleph::RLINK(), and root().

Referenced by huffman_to_btreepic().

◆ LLINK()

template<class Node >

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

inlineconstexprnoexcept

Return a pointer to left subtree.

Definition at line 322 of file tpl_binNode.H.

◆ load_tree()

template<class Node >

Node * Aleph::load_tree ( std::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 built binary tree

Exceptions

bad_alloc if there is no enough memory

See also: save_tree()

Definition at line 1224 of file tpl_binNodeUtils.H.

References Aleph::destroyRec(), Aleph::BitArray::load(), Aleph::load_tree_keys_in_prefix(), Aleph::maps(), Aleph::prefix(), and root().

◆ 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 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. for the next node in the prefix path.

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

Definition at line 1357 of file tpl_binNodeUtils.H.

References Aleph::BitArray::load_from_array_of_chars(), Aleph::maps(), Aleph::prefix(), and root().

◆ load_tree_keys_in_prefix()

template<class Node >

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

inline

Load the keys stored in preorder from an 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

Exceptions

runtime_error if the input stream fails

Definition at line 1173 of file tpl_binNodeUtils.H.

References ah_runtime_error_if, Aleph::LLINK(), Aleph::load_tree_keys_in_prefix(), Aleph::maps(), Aleph::RLINK(), and root().

Referenced by Aleph::load_tree(), Aleph::load_tree_keys_in_prefix(), and TEST().

◆ 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 ) const

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.

Definition at line 537 of file tpl_rand_tree.H.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::cmp, Aleph::inorder_position(), Aleph::maps(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::tree_root.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ 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] key to be searched

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

Definition at line 578 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::cmp, Aleph::inorder_position(), Aleph::maps(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

◆ 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 an inorder traversal of tree rooted by root and on each node executes a visit function with the following signature:

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

Where:

p: pointer to visited 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_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()

Definition at line 189 of file tpl_binNodeUtils.H.

References Aleph::maps(), Aleph::postorder_rec_helper(), and root().

◆ 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

Definition at line 433 of file tpl_binNodeUtils.H.

References Aleph::maps(), Aleph::prefix(), and root().

◆ prefix_traverse()

template<class Node , class Op >

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

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

	root
[in]	op	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

Definition at line 2641 of file tpl_binNodeUtils.H.

References Aleph::BinNodePrefixIterator< Node >::has_curr(), Aleph::maps(), and root().

◆ preorder_to_bst()

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

Node * Aleph::preorder_to_bst	(	DynArray< typename Node::key_type > &	preorder,
		int	l,
		int	r,
		const Compare &	cmp = `Compare()`
	)

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
	cmp	comparison criteria

Returns: root of the resulting tree

Exceptions

bad_alloc if there is no enough memory

Definition at line 1422 of file tpl_binNodeUtils.H.

References cmp(), l, Aleph::LLINK(), Aleph::maps(), preorder(), Aleph::RLINK(), and root().

◆ 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 preorder traversal of tree rooted by root and on each node executes a visit function with the following signature:

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

Where:

p: pointer to visited 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()

Definition at line 143 of file tpl_binNodeUtils.H.

References Aleph::maps(), Aleph::preorder_rec_helper(), and root().

Referenced by build_tree(), Aleph::DynSetTree< Key, Tree, Compare >::for_each_in_preorder(), huffman_to_btreepic(), main(), main(), Aleph::HtdRbTree< Key, Compare >::verifyRedBlack(), write_avl(), write_bin(), write_rand(), write_rb(), write_splay(), and write_treap().

◆ 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 successor nodes. This implicates that during the traversal the links could 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]	node	of tree
[in]	visitFct	pointer to visit function

See also: inOrderThreaded()

Definition at line 947 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by TEST().

◆ PRIO()

template<class Node >

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

noexcept

Access the priority of a treap node.

Template Parameters

Node	Treap node type

Parameters

p	Pointer to node

Returns: Reference to the node's priority

Definition at line 120 of file treapNode.H.

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

Definition at line 817 of file tpl_binNodeXt.H.

References cmp(), Aleph::COUNT(), Aleph::join_exclusive_xt(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::remove_by_key_xt(), Aleph::HTList::reset(), Aleph::RLINK(), and root().

Referenced by Aleph::remove_by_key_xt(), Aleph::remove_by_key_xt(), TEST(), and TEST().

◆ 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

Definition at line 895 of file tpl_binNodeXt.H.

References Aleph::__remove_by_pos_xt(), ah_out_of_range_error_if, Aleph::COUNT(), and root().

Referenced by TEST(), and TEST().

◆ 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,
		const 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()

Definition at line 1955 of file tpl_binNodeUtils.H.

References cmp(), Aleph::join_exclusive(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::remove_from_bst(), Aleph::HTList::reset(), Aleph::RLINK(), and root().

Referenced by Aleph::join(), Aleph::remove_from_bst(), TEST(), and TEST().

◆ RLINK()

template<class Node >

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

inlineconstexprnoexcept

Return the right tree of p.

Definition at line 338 of file tpl_binNode.H.

◆ 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

Definition at line 2159 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

◆ 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
	pp	parent of `p`

Definition at line 2178 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

◆ rotate_to_left_xt()

template<class Node >

Node * Aleph::rotate_to_left_xt ( Node * p )

inlinenoexcept

Rotate to left the extended binary tree with root p.

Parameters

[in] p root to rotate.

Returns: pointer to the new root.

Definition at line 946 of file tpl_binNodeXt.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::search_or_insert_root_rec_xt(), Aleph::select_gotoup_root(), GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl(), GenTdSplayTreeRk< NodeType, Key, Compare >::splay_max(), and TEST().

◆ 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

Definition at line 2114 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

◆ 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
[in]	pp	parent of p

Returns: pointer to the new root after rotation

Definition at line 2134 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

◆ 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

Definition at line 925 of file tpl_binNodeXt.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::search_or_insert_root_rec_xt(), Aleph::select_gotoup_root(), GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl(), and TEST().

◆ save_tree()

template<class Node >

void Aleph::save_tree	(	Node *	root,
		std::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 overload 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()

Definition at line 1202 of file tpl_binNodeUtils.H.

References output, Aleph::prefix(), root(), Aleph::save_tree_keys_in_prefix(), and Aleph::tree_to_bits().

Referenced by TEST().

◆ save_tree_in_array_of_chars()

template<class Node , class Get_Key >

void Aleph::save_tree_in_array_of_chars	(	Node *	root,
		const std::string &	array_name,
		std::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 original 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 array 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:

std::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

Definition at line 1313 of file tpl_binNodeUtils.H.

References Aleph::maps(), output, Aleph::prefix(), root(), and Aleph::tree_to_bits().

◆ save_tree_keys_in_prefix()

template<class Node >

void Aleph::save_tree_keys_in_prefix	(	Node *	root,
		std::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:

std::string gk(Node * p)

Parameters

[in]	root	of tree
[out]	output	stream

See also: load_tree_keys_in_prefix()

Definition at line 1150 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), output, Aleph::RLINK(), root(), and Aleph::save_tree_keys_in_prefix().

Referenced by Aleph::save_tree(), and Aleph::save_tree_keys_in_prefix().

◆ 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

Searches key in a forest and computes the Dewey number of the node containing the key.

search_deway(root,key,deway,n) searches in the forest whose first tree is root a node containing the key. If the node is found, then the routine stores in deway[] the Dewey number of the found node.

The search is performed using the equality criterion Equal()().

Parameters

[in]	root	root of the first tree of the forest.
[in]	key	key to search.
[out]	deway	array that stores the Dewey number.
[in]	size	maximum length of the Dewey number.
[out]	n	length of the computed Dewey number (if the node is found).

Returns: pointer to the node containing key; nullptr if there is no node with key,

Exceptions

overflow_error if size is not sufficient to store the Dewey sequence.

Definition at line 1146 of file tpl_tree_node.H.

References ah_overflow_error_if, deway(), Aleph::maps(), root(), and Aleph::size().

Referenced by TEST_F().

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

Definition at line 1778 of file tpl_binNodeUtils.H.

References cmp(), KEY, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by TEST().

◆ search_or_insert_root_rec()

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

Node * Aleph::search_or_insert_root_rec	(	Node *	root,
		Node *	p,
		const 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()

Definition at line 2434 of file tpl_binNodeUtils.H.

References cmp(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), Aleph::rotate_to_left(), Aleph::rotate_to_right(), and Aleph::search_or_insert_root_rec().

Referenced by Aleph::search_or_insert_root_rec().

◆ 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,
		const 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()

Definition at line 1625 of file tpl_binNodeUtils.H.

References cmp(), Aleph::CmpGreater, Aleph::CmpLess, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), and Aleph::three_way_compare().

Referenced by TEST().

◆ 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

Definition at line 120 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, Aleph::maps(), and root().

◆ 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,
		const 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

Definition at line 1676 of file tpl_binNodeUtils.H.

References cmp(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

Referenced by TEST().

◆ searchInBinTree()

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

Node * Aleph::searchInBinTree	(	Node *	root,
		const typename Node::key_type &	key,
		const 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 Search a key in a binary search tree using optimistic search.

Uses single comparison per level with deferred duplicate detection, reducing comparisons from ~1.5h to h+1 for tree height h.

Definition at line 1492 of file tpl_binNodeUtils.H.

References cmp(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::next(), Aleph::RLINK(), and root().

Referenced by main(), Aleph::HtdRbTree< Key, Compare >::search(), Aleph::Gen_Treap< NodeType, Key, Compare >::search(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search(), Aleph::BinTree_Operation< Node, Cmp >::search(), and TEST().

◆ select()

template<class Node >

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

inline

Iterative selection of a node according to inorder position.

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

Definition at line 164 of file tpl_binNodeXt.H.

References ah_out_of_range_error_if, Aleph::COUNT(), and Aleph::select_ne().

Referenced by main(), GenTdSplayTreeRk< NodeType, Key, Compare >::select(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::select(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::select(), Aleph::HtdRbTreeRk< Key, Compare >::select(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::select(), TEST(), TEST(), TEST(), TEST(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::update_curr(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::update_curr().

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

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.

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

Definition at line 72 of file tpl_balanceXt.H.

References ah_out_of_range_error_if, Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), Aleph::rotate_to_left_xt(), Aleph::rotate_to_right_xt(), and Aleph::select_gotoup_root().

Referenced by Aleph::balance_tree(), and Aleph::select_gotoup_root().

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

Definition at line 132 of file tpl_binNodeXt.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::select(), and TEST().

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

Definition at line 114 of file tpl_binNodeXt.H.

References Aleph::__select_rec(), ah_out_of_range_error_if, and Aleph::COUNT().

Referenced by TEST(), and TEST().

◆ 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,
		const 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 keys 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()

Definition at line 2214 of file tpl_binNodeUtils.H.

References cmp(), KEY, l, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

Referenced by TEST().

◆ 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,
		const 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()

Definition at line 1901 of file tpl_binNodeUtils.H.

References cmp(), Aleph::maps(), root(), and Aleph::split_key_dup_rec_helper().

Referenced by Aleph::insert_dup_root(), Aleph::Gen_Treap< NodeType, Key, Compare >::split_key_dup(), and TEST().

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

Definition at line 583 of file tpl_binNodeXt.H.

References cmp(), l, Aleph::maps(), and root().

Referenced by Aleph::insert_dup_root_xt(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_key_dup(), Aleph::split_key_dup_rec_xt(), and TEST().

◆ 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,
		const 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()

Definition at line 1850 of file tpl_binNodeUtils.H.

References cmp(), Aleph::maps(), root(), and Aleph::split_key_rec_helper().

Referenced by Aleph::insert_root(), Aleph::GenBinTree< NodeType, Key, Compare >::split(), Aleph::Gen_Treap< NodeType, Key, Compare >::split_key(), and TEST().

◆ 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 according 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`
[in,out]	cmp	comparison function

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

Definition at line 523 of file tpl_binNodeXt.H.

References Aleph::__split_key_rec_xt(), cmp(), l, Aleph::maps(), and root().

Referenced by Aleph::insert_root_xt(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::split_key(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_key(), Aleph::split_key_rec_xt(), TEST(), and TEST().

◆ 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 \([0, i)\) will be put
[out]	tg	tree where the rank of keys \([i, n]\) will be put

Definition at line 725 of file tpl_binNodeXt.H.

References ah_out_of_range_error_if, Aleph::COUNT(), and Aleph::maps().

Referenced by Aleph::insert_by_pos_xt(), main(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::split_pos(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_pos(), TEST(), and TEST().

◆ 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

Definition at line 463 of file tpl_binNodeUtils.H.

References Aleph::maps(), root(), and Aleph::suffix().

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

Definition at line 2333 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

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

Definition at line 2279 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

◆ three_way_compare()

template<typename T , class Compare = Aleph::less<T>>

ThreeWayCmp Aleph::three_way_compare	(	const T &	a,
		const T &	b,
		const Compare &	cmp = `Compare()`
	)

inlinenoexcept

Three-way comparison using a binary comparator.

Returns CmpLess if a < b, CmpEqual if a == b, CmpGreater if a > b. This reduces two comparisons to one when the result is cached.

Parameters

[in]	a	first value to compare
[in]	b	second value to compare
[in]	cmp	binary less-than comparator

Returns: CmpLess, CmpEqual, or CmpGreater indicating the ordering

Definition at line 1465 of file tpl_binNodeUtils.H.

References cmp(), Aleph::CmpEqual, Aleph::CmpGreater, and Aleph::CmpLess.

Referenced by Aleph::search_parent().

◆ tree_postorder_traversal()

template<class Node >

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

inline

Postorder traversal of a tree.

tree_postorder_traversal((root,visit) performs a postorder traversal over the tree rooted at root. If visitFct is specified, then for each visited node the function is invoked.

The visit function has the following specification:

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

Where:

p: pointer to the currently visited node.
level: the level of p in the tree.
child_index: index of p among its siblings.

Parameters

[in]	root	root of the tree to traverse.
[in]	visitFct	pointer to the visit function.

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

Definition at line 915 of file tpl_tree_node.H.

References Aleph::__tree_postorder_traversal(), Aleph::maps(), and root().

Referenced by precompute_x_coordinates_for_tree().

◆ tree_preorder_traversal()

template<class Node >

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

inline

Preorder traversal of a tree.

tree_preorder_traversal((root,visit) performs a preorder traversal over the tree rooted at root. If visitFct is specified, then for each visited node the function is invoked.

The visit function has the following specification:

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

Where:

p: pointer to the currently visited node.
level: the level of p in the tree.
child_index: index of p among its siblings.

Parameters

[in]	root	root of the tree to traverse.
[in]	visitFct	pointer to the visit function.

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

Exceptions

domain_error if root is not a root node of a tree.

Definition at line 835 of file tpl_tree_node.H.

References Aleph::__tree_preorder_traversal(), ah_domain_error_if, Aleph::maps(), and root().

Referenced by compute_coordinates_for_forest_and_set_picture_size(), and compute_coordinates_for_tree().

◆ tree_to_bits() [1/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()

Definition at line 1051 of file tpl_binNodeUtils.H.

References Aleph::maps(), root(), and Aleph::tree_to_bits().

◆ tree_to_bits() [2/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()

Definition at line 1023 of file tpl_binNodeUtils.H.

References Aleph::LLINK(), Aleph::BitArray::push(), Aleph::RLINK(), root(), and Aleph::tree_to_bits().

Referenced by Aleph::code(), Aleph::save_tree(), Aleph::Huffman_Encoder_Engine::save_tree(), Aleph::save_tree_in_array_of_chars(), TEST(), TEST(), TEST(), TEST(), Aleph::tree_to_bits(), and Aleph::tree_to_bits().

Files

Classes

Macros

Functions

Detailed Description

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

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

◆ postOrderRec()

◆ prefix()

◆ prefix_traverse()

◆ preorder_to_bst()

◆ preOrderRec()