Trees

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_b_tree.H
	B-Tree implementation with configurable minimum degree.
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_binNodeGenerators.H
	Lazy (coroutine-based) traversals of binary trees.
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_bplus_tree.H
	B+ Tree implementation with linked leaves and configurable degree.
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_file_b_map.H
	Persistent key/value map built on top of Aleph::File_B_Tree.
file	tpl_file_b_tree.H
	Page-managed persistent B-Tree with file-backed storage.
file	tpl_file_bplus_map.H
	Persistent key/value map built on top of Aleph::File_BPlus_Tree.
file	tpl_file_bplus_tree.H
	Page-managed persistent B+ Tree with file-backed storage.
file	tpl_interval_tree.H
	Interval tree: augmented BST for overlap/stabbing queries.
file	tpl_link_cut_tree.H
	Link-Cut Tree: a dynamic forest with path queries.
file	tpl_link_cut_tree_with_edges.H
	Edge-weighted Link-Cut Tree using edge-as-node representation.
file	tpl_nodePool.H
	Tree node memory pool allocator.
file	tpl_paged_tree_durability.H
	Helpers for durable paged-tree files.
file	tpl_paged_value_codec.H
	Fixed-size portable codecs for paged persistent tree payloads.
file	tpl_patricia_trie.H
	PATRICIA/crit-bit set and map for fixed-width unsigned integer keys.
file	tpl_persistent_treap.H
	Immutable path-copying treap set and map.
file	tpl_radix_tree.H
	Compressed prefix tree (Aleph::RadixTree) mapping string keys to values.
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_tree_snapshot.H
	Internal helpers for snapshot-backed persistent tree wrappers.
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
	Low-level prefix tree node for storing character sequences. More...
class	Aleph::Cnode::Detached_Subtree_Guard
	Own a detached subtree until it is committed elsewhere. More...
class	Aleph::Cnode::Pending_Path_Guard
	Own standalone nodes until an insertion path is committed. More...
class	Aleph::Cnode::Clone_Target_Rollback
	Restore a clone target if appending cloned children fails. More...
class	Aleph::Prefix_Tree
	Owning prefix tree wrapper. More...
class	Aleph::Prefix_Tree_Map< T >
	Owning prefix tree map from strings to values. More...
class	Aleph::Prefix_Tree_Map< T >::Node
	Internal trie node storing one character and an optional value. More...
class	Aleph::Prefix_Tree_Map< T >::Node::Detached_Subtree_Guard
	Own a detached map subtree until it is committed. More...
class	Aleph::Prefix_Tree_Map< T >::Node::Pending_Path_Guard
	Own standalone insertion nodes until a new path is committed. 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 a virtual destructor. More...
struct	Aleph::Avl_Tree_Vtl< Key, Compare >
	AVL binary search tree with nodes with a virtual destructor. 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 >
	Ranked AVL tree with nodes without a virtual destructor. More...
struct	Aleph::Avl_Tree_Rk_Vtl< Key, Compare >
	Ranked AVL tree with nodes with a virtual destructor. More...
class	Aleph::GenBinHeap< NodeType, Key, Compare >
	Generic heap of nodes. 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...
struct	Aleph::Interval< T >
	Closed interval [low, high]. More...
struct	Aleph::Interval_Less< T, Compare >
	BST comparator for intervals: order by (low, then high). More...
struct	Aleph::interval_endpoint< Key >
	Trait to extract endpoint type from Interval<T>. More...
class	Aleph::Interval_Tree_Node_Data< T >
	Data portion of an interval tree node. More...
class	Aleph::Interval_Tree_Node< Key >
	Interval tree node with sentinel support. More...
class	Aleph::Interval_Tree_NodeVtl< Key >
	Interval tree node with virtual destructor. More...
class	Aleph::Gen_Interval_Tree< NodeType, T, Compare >
	Augmented treap storing intervals with overlap/stabbing queries. More...
struct	Aleph::Gen_Interval_Tree< NodeType, T, Compare >::Iterator
	Inorder iterator over nodes. More...
struct	Aleph::Interval_Tree< T, Compare >
	Interval tree using nodes without virtual destructor. More...
struct	Aleph::Interval_Tree_Vtl< T, Compare >
	Interval tree using nodes with virtual destructor. More...
class	Aleph::DynIntervalTree< T, Compare >
	High-level interval tree with automatic memory management. More...
class	Aleph::DynIntervalTree< T, Compare >::Iterator
	Inorder iterator yielding Interval<T> keys. More...
class	Aleph::Gen_Mo_On_Tree_Node< T, Policy >
	Offline subtree and path queries on N-ary trees (Tree_Node). 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 >
	Forward declaration used by CRTP helpers before the full node definition. More...
struct	Aleph::Tree_Node< T >::Flags
class	Aleph::Tree_Node< T >::Children_Iterator
	Iterator over the children of this. More...
struct	Aleph::Tree_Node< T >::Children_Set
	Adapter that exposes a node's children through an Iterator type. More...
struct	Aleph::Tree_Node< T >::Children_Set::Iterator
	Child iterator adapter used by generic iterator utilities. More...
class	Aleph::Tree_Node< T >::Iterator
	Preorder iterator over a tree rooted at a Tree_Node. More...
struct	Aleph::Tree_Node_Vtl< T >
	Tree_Node variant with a virtual destructor. 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.

Typedefs
template<typename T >
using	Aleph::Distinct_Count_Mo_On_Tree_Node = Gen_Mo_On_Tree_Node< T, Distinct_Count_Policy< T > >
	Mo on Tree_Node specialised for counting distinct values.
template<typename T >
using	Aleph::Powerful_Array_Mo_On_Tree_Node = Gen_Mo_On_Tree_Node< T, Powerful_Array_Policy< T > >
	Mo on Tree_Node specialised for the "powerful array" query.
template<typename T >
using	Aleph::Range_Mode_Mo_On_Tree_Node = Gen_Mo_On_Tree_Node< T, Range_Mode_Policy< T > >
	Mo on Tree_Node specialised for range mode queries.

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<typename Node , class Write = Dft_Write<Node>>
void	Aleph::generate_tree_graphviz (Node *root, std::ostream &out)
	Generate a Graphviz DOT specification for a 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.
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 >
Aleph::Generator< Node * >	Aleph::lazy_in_order (Node *root)
	Lazily traverse a binary tree in-order (left, node, right).
template<class Node >
Aleph::Generator< Node * >	Aleph::lazy_pre_order (Node *root)
	Lazily traverse a binary tree pre-order (node, left, right).
template<class Node >
Aleph::Generator< Node * >	Aleph::lazy_post_order (Node *root)
	Lazily traverse a binary tree post-order (left, right, node).
template<BinNodeLike Node>
void	Aleph::assert_valid_tree_root (const Node *root) noexcept
	Debug-only check that root is a valid tree for Node.
template<BinNodeLike Node>
int	Aleph::inOrderRec (Node *root, void(*visitFct)(Node *, int, int))
	Traverse recursively inorder a binary tree.
template<BinNodeLike Node>
int	Aleph::preOrderRec (Node *root, void(*visitFct)(Node *, int, int))
	Traverse recursively in preorder a binary tree.
template<BinNodeLike Node>
int	Aleph::postOrderRec (Node *root, void(*visitFct)(Node *, int, int))
	Traverse recursively in postorder a binary tree.
template<BinNodeLike 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<BinNodeLike Node, class Op >
void	Aleph::for_each_preorder (Node *root, Op &&op)
	Execute an operation in preorder sense for each node of tree.
template<BinNodeLike Node, class Op >
void	Aleph::for_each_postorder (Node *root, Op &&op)
	Execute an operation in postorder sense for each node of tree.
template<BinNodeLike Node>
DynList< Node * >	Aleph::prefix (Node *root)
	Return a list with preorder traversal of a tree.
template<BinNodeLike Node>
DynList< Node * >	Aleph::infix (Node *root)
	Return a list with inorder traversal of a tree.
template<BinNodeLike Node>
DynList< Node * >	Aleph::suffix (Node *root)
	Return a list with postorder traversal of a tree.
template<BinNodeLike Node>
size_t	Aleph::compute_cardinality_rec (Node *root) noexcept
	Count the number of nodes of a binary tree.
template<BinNodeLike Node>
size_t	Aleph::computeHeightRec (Node *root) noexcept
	Compute recursively the height of root
template<BinNodeLike Node>
void	Aleph::destroyRec (Node *&root) noexcept
	Free recursively all the memory occupied by the tree root
template<BinNodeLike Node>
Node *	Aleph::copyRec (Node *root)
	Copy recursively a tree.
template<BinNodeLike Node>
void	Aleph::levelOrder (Node *root, void(*visitFct)(Node *, int, bool))
	Traverse a binary tree by levels.
template<BinNodeLike 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<BinNodeLike Node>
DynDlist< Node * >	Aleph::compute_nodes_in_level (Node *root, const int &level)
	Count the number of nodes in a specific tree level.
template<BinNodeLike Node>
void	Aleph::inOrderThreaded (Node *root, void(*visitFct)(Node *))
	Traverse inorder a binary tree without recursion and without stack.
template<BinNodeLike Node>
void	Aleph::preOrderThreaded (Node *node, void(*visitFct)(Node *))
	Traverse preorder a binary tree without recursion and without stack.
template<BinNodeLike Node>
size_t	Aleph::internal_path_length (Node *p) noexcept
	Compute the internal path length.
template<BinNodeLike Node>
void	Aleph::tree_to_bits (Node *root, BitArray &array)
	Compute a bit code for the binary tree.
template<BinNodeLike Node>
BitArray	Aleph::tree_to_bits (Node *root)
	Compute a bit code for the binary tree.
template<BinNodeLike Node>
Node *	Aleph::bits_to_tree (const BitArray &array, int idx=0)
	Build a binary tree given its bits code.
template<BinNodeLike Node>
void	Aleph::save_tree_keys_in_prefix (Node *root, std::ostream &output)
	Store in output stream the tree keys in preorder.
template<BinNodeLike Node>
void	Aleph::load_tree_keys_in_prefix (Node *root, std::istream &input)
	Load the keys stored in preorder from an input stream.
template<BinNodeLike Node>
void	Aleph::save_tree (Node *root, std::ostream &output)
	Store a binary tree in a stream.
template<BinNodeLike Node>
Node *	Aleph::load_tree (std::istream &input)
	Load and build a binary tree from a stream.
template<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike Node>
Node *	Aleph::find_min (Node *root) noexcept
	Return the minimum key contained in a binary search tree.
template<BinNodeLike Node>
Node *	Aleph::find_max (Node *root) noexcept
	Return the maximum key contained in a binary search tree.
template<BinNodeLike Node>
Node *	Aleph::find_successor (Node *p, Node *&pp) noexcept
	Find the inorder successor of p
template<BinNodeLike Node>
Node *	Aleph::find_predecessor (Node *p, Node *&pp) noexcept
	Find the inorder predecessor of p
template<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike Node>
Node *	Aleph::join_exclusive (Node *&ts, Node *&tg) noexcept
	Exclusive join of two binary trees.
template<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike Node>
Node *	Aleph::rotate_to_right (Node *p) noexcept
	Rotate to the right the tree with root p
template<BinNodeLike 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<BinNodeLike Node>
Node *	Aleph::rotate_to_left (Node *p) noexcept
	Rotate to the left the tree with root p
template<BinNodeLike 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<BinNodeLike 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<BinNodeLike Node>
void	Aleph::swap_node_with_successor (Node *p, Node *&pp, Node *q, Node *&pq) noexcept
	Swap a node with its successor inorder.
template<BinNodeLike Node>
void	Aleph::swap_node_with_predecessor (Node *p, Node *&pp, Node *q, Node *&pq) noexcept
	Swap a node with its predecessor inorder.
template<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<BinNodeLike 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<RankedBinNodeLike Node>
auto &	Aleph::COUNT (Node *p) noexcept
	Return the number of nodes of the tree fron p is root.
template<RankedBinNodeLike Node>
Node *	Aleph::select_rec (Node *r, const size_t i)
	Recursively select the i-th node inorder sense.
template<RankedBinNodeLike Node>
Node *	Aleph::select_ne (Node *r, const size_t pos) noexcept
	Iterative selection of a node according to inorder position without exception.
template<RankedBinNodeLike Node>
Node *	Aleph::select (Node *r, const size_t pos)
	Iterative selection of a node according to inorder position.
template<RankedBinNodeLike 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<RankedBinNodeLike 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<RankedBinNodeLike 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<BinNodeLike 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<BinNodeLike 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<RankedBinNodeLike 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<RankedBinNodeLike 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<RankedBinNodeLike 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<RankedBinNodeLike 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<RankedBinNodeLike Node>
Node *	Aleph::join_exclusive_xt (Node *&ts, Node *&tg) noexcept
	Exclusive union of two extended binary search trees.
template<RankedBinNodeLike 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<RankedBinNodeLike 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<RankedBinNodeLike Node>
bool	Aleph::check_rank_tree (Node *root) noexcept
	Return true if root is a valid extended binary tree.
template<RankedBinNodeLike Node>
Node *	Aleph::rotate_to_right_xt (Node *p) noexcept
	Rotate to right the extended bianry tree with root p
template<RankedBinNodeLike 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:

1. NullPtr which represents to the empty tree
2. 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 258 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:

1. NullPtr which represents to the empty tree
2. 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 298 of file tpl_binNode.H.

Typedef Documentation

Distinct_Count_Mo_On_Tree_Node

template<typename T >

using Aleph::Distinct_Count_Mo_On_Tree_Node = typedef Gen_Mo_On_Tree_Node<T, Distinct_Count_Policy<T> >

Mo on Tree_Node specialised for counting distinct values.

Template Parameters

T	Value type stored in Tree_Node.

Definition at line 1243 of file tpl_mo_on_trees.H.

Powerful_Array_Mo_On_Tree_Node

template<typename T >

using Aleph::Powerful_Array_Mo_On_Tree_Node = typedef Gen_Mo_On_Tree_Node<T, Powerful_Array_Policy<T> >

Mo on Tree_Node specialised for the "powerful array" query.

Template Parameters

T	Value type stored in Tree_Node.

Definition at line 1251 of file tpl_mo_on_trees.H.

Range_Mode_Mo_On_Tree_Node

template<typename T >

using Aleph::Range_Mode_Mo_On_Tree_Node = typedef Gen_Mo_On_Tree_Node<T, Range_Mode_Policy<T> >

Mo on Tree_Node specialised for range mode queries.

Template Parameters

T	Value type stored in Tree_Node.

Definition at line 1259 of file tpl_mo_on_trees.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 1110 of file tpl_tree_node.H.

References Aleph::are_tree_equal(), Aleph::blossom_maximum_cardinality_matching(), Aleph::eq(), and Aleph::zipEq().

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

assert_valid_tree_root()

template<BinNodeLike Node>

void Aleph::assert_valid_tree_root ( const Node *  root )

inlinenoexcept

Debug-only check that root is a valid tree for Node.

Node types declared with a sentinel (DECLARE_BINNODE_SENTINEL: treaps, red-black and ranked trees, ...) represent the empty tree with Node::NullPtr, the address of a static sentinel node, not with nullptr. A nullptr stored in such a tree (e.g. tree.getRoot() = nullptr) corrupts it, and the next traversal dereferences it. In debug builds this check aborts with a message instead of a segmentation fault; with NDEBUG it compiles to nothing.

Parameters

[in]

root

root of the tree (or subtree) about to be walked

Note

For node types without a sentinel Node::NullPtr is nullptr, so the check always passes.

Definition at line 75 of file tpl_binNodeUtils.H.

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

Referenced by Aleph::callKeyDestructorsRec(), Aleph::check_bst(), Aleph::compute_cardinality_rec(), Aleph::computeHeightRec(), Aleph::copyRec(), Aleph::destroyRec(), Aleph::find_max(), Aleph::find_min(), Aleph::inOrderRec(), Aleph::insert_dup_in_bst(), Aleph::insert_dup_root(), Aleph::insert_in_bst(), Aleph::insert_root(), Aleph::insert_root_rec(), Aleph::internal_path_length(), Aleph::levelOrder(), Aleph::postOrderRec(), Aleph::preOrderRec(), Aleph::remove_from_bst(), Aleph::search_or_insert_in_bst(), Aleph::search_or_insert_root_rec(), Aleph::search_parent(), Aleph::search_rank_parent(), Aleph::searchInBinTree(), Aleph::split_key(), Aleph::split_key_dup_rec(), and Aleph::split_key_rec().

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:

1. TNode: tree type based on Tree_Node.
2. 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 1476 of file tpl_tree_node.H.

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

Referenced by main().

bits_to_tree()

template<BinNodeLike 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 1118 of file tpl_binNodeUtils.H.

References Aleph::blossom_maximum_cardinality_matching().

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::blossom_maximum_cardinality_matching(), Aleph::compute_optimal_costs(), and keys.

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 770 of file tpl_binNodeUtils.H.

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

check_bst()

template<BinNodeLike 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 1383 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), and cmp().

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(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::verify(), GenTdSplayTree< NodeType, Key, Compare >::verify(), and GenTdSplayTreeRk< NodeType, Key, Compare >::verify().

check_rank_tree()

template<RankedBinNodeLike Node>

bool Aleph::check_rank_tree ( Node *  root )

inlinenoexcept

Return true if root is a valid extended binary tree.

Definition at line 909 of file tpl_binNodeXt.H.

References Aleph::and, Aleph::check_rank_tree(), Aleph::COUNT(), LLINK, 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<BinNodeLike 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 494 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::compute_cardinality_rec(), LLINK, 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 1262 of file tpl_tree_node.H.

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

Referenced by Aleph::compute_height().

compute_nodes_in_level()

template<BinNodeLike 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 859 of file tpl_binNodeUtils.H.

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

Referenced by south_offset(), and TEST().

computeHeightRec()

template<BinNodeLike 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 517 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), Aleph::computeHeightRec(), LLINK, 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(), TEST(), write_avl(), write_bin(), write_rand(), write_rb(), write_splay(), and write_treap().

copyRec()

template<BinNodeLike 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 585 of file tpl_binNodeUtils.H.

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

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

COUNT()

template<RankedBinNodeLike 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 83 of file tpl_binNodeXt.H.

Referenced by GenTdSplayTreeRk< NodeType, Key, Compare >::__insert(), Aleph::__remove_by_pos_xt(), Aleph::__select_rec(), Aleph::__split_key_dup_rec_xt(), Aleph::__split_key_rec_xt(), Aleph::__split_pos_rec(), Aleph::balance_tree(), Aleph::check_rank_tree(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateLeft(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateRight(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_max(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::extract_max_rb(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_min(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::extract_min_rb(), GenTdSplayTreeRk< NodeType, Key, Compare >::find_position(), Aleph::BinTreeXt_Operation< Node, Cmp >::find_position(), Aleph::find_position(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::find_succ_and_swap(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findPredAndSwap(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findSuccAndSwap(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::get_current_position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::get_current_position(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::has_curr(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::has_curr(), Aleph::HtdRbTreeRk< Key, Compare >::init(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::init(), Aleph::BinTreeXt_Operation< Node, Cmp >::inorder_position(), Aleph::inorder_position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), GenTdSplayTreeRk< NodeType, Key, Compare >::insert(), Aleph::HtdRbTreeRk< Key, Compare >::insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::insert(), Aleph::insert_by_key_xt(), Aleph::insert_by_pos_xt(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::HtdRbTreeRk< Key, Compare >::insert_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert_dup(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::insert_dup(), Aleph::insert_dup_by_key_xt(), Aleph::BinTreeXt_Operation< Node, Cmp >::insert_dup_root(), Aleph::insert_dup_root_xt(), Aleph::BinTreeXt_Operation< Node, Cmp >::insert_root(), Aleph::insert_root_xt(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::is_container_empty(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::is_container_empty(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::join_exclusive_xt(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_left_rb(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_right_rb(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb(), GenTdSplayTreeRk< NodeType, Key, Compare >::position(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_insert_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join_exclusive(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_remove(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_search_or_insert(), GenTdSplayTreeRk< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::remove_by_key_xt(), Aleph::remove_by_pos_xt(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove_pos(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove_pos(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove_pos(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove_pos(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::reset_last(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::reset_last(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_left_simple(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_right_simple(), Aleph::HtdRbTreeRk< Key, Compare >::rotate_to_left_rk(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_to_left_rk(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::rotate_to_left_rk(), Aleph::rotate_to_left_xt(), Aleph::HtdRbTreeRk< Key, Compare >::rotate_to_right_rk(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_to_right_rk(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::rotate_to_right_rk(), Aleph::rotate_to_right_xt(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateLeft(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateRight(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::HtdRbTreeRk< Key, Compare >::search_or_insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search_or_insert(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::search_or_insert(), Aleph::search_or_insert_by_key_xt(), Aleph::search_or_insert_root_rec_xt(), Aleph::HtdRbTreeRk< Key, Compare >::searchFlipColorsAndInsert(), Aleph::HtdRbTreeRk< Key, Compare >::searchFlipColorsAndInsertDup(), Aleph::select(), Aleph::select(), Aleph::select_gotoup_root(), Aleph::select_ne(), Aleph::select_rec(), GenTdSplayTreeRk< NodeType, Key, Compare >::size(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size(), Aleph::HtdRbTreeRk< Key, Compare >::size(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::size(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::size(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::size(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::size(), GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl(), GenTdSplayTreeRk< NodeType, Key, Compare >::splay_max(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec(), Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_dup_rec(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec_rb(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec(), Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_rec(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_rec_rb(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos(), Aleph::split_pos_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos_rec_rb(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swapWithSuccessor(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::update_curr(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::update_curr(), Aleph::HtdRbTreeRk< Key, Compare >::updateCountRec(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::updateCountRec(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::updateCountsFromStack(), and Aleph::HtdRbTreeRk< Key, Compare >::verifyCountsRec().

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 1237 of file tpl_tree_node.H.

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

Referenced by main(), TEST(), 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 1150 of file tpl_tree_node.H.

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

Referenced by Aleph::Cnode::Clone_Target_Rollback::~Clone_Target_Rollback(), Simple_Tree::~Simple_Tree(), Three_Trees::~Three_Trees(), Aleph::Cnode::destroy(), Aleph::Prefix_Tree_Map< T >::Node::destroy(), Aleph::destroy_forest(), Aleph::destroy_tree(), filesystem_inodes(), main(), main(), read_input_and_build_tree(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), 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(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

destroyRec()

template<BinNodeLike 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 538 of file tpl_binNodeUtils.H.

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

Referenced by Aleph::bits_to_tree_helper(), Aleph::copyRec(), Aleph::DynIntervalTree< T, Compare >::destroy_tree(), 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=(), IntervalTreeRawTest::TearDown(), TEST(), test(), 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 1307 of file tpl_tree_node.H.

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

Referenced by main(), and parse_deway_number().

find_max()

template<BinNodeLike 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 1521 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), RLINK, and root().

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

find_min()

template<BinNodeLike 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 1502 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), LLINK, and root().

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

find_predecessor()

template<BinNodeLike 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 1565 of file tpl_binNodeUtils.H.

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

Referenced by TEST().

find_successor()

template<BinNodeLike 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 1540 of file tpl_binNodeUtils.H.

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

Referenced by TEST().

for_each_in_order()

template<BinNodeLike 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 275 of file tpl_binNodeUtils.H.

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

for_each_postorder()

template<BinNodeLike 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 404 of file tpl_binNodeUtils.H.

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

for_each_preorder()

template<BinNodeLike 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 340 of file tpl_binNodeUtils.H.

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

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:

1. p: pointer to the currently visited node.
2. level: the level of p in the tree.
3. 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 1092 of file tpl_tree_node.H.

References Aleph::__tree_postorder_traversal(), ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), 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:

1. p: pointer to the currently visited node.
2. level: the level of p in the tree.
3. 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 1018 of file tpl_tree_node.H.

References Aleph::__tree_preorder_traversal(), ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), 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:

1. TNode: tree type based on Tree_Node.
2. 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 1409 of file tpl_tree_node.H.

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

Referenced by main().

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>

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 238 of file generate_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), out, 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 205 of file generate_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), out, 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 159 of file generate_tree.H.

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

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

generate_tree_graphviz()

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

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

Generate a Graphviz DOT specification for a tree.

Produces a DOT specification that can be rendered using Graphviz tools (dot, neato, etc.) to visualize the tree structure.

Template Parameters

Node	Tree node type (e.g. Tree_Node)
Write	Functor that converts node key to string for the node label. Must provide: std::string operator()(Node*)

Parameters

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

See also

Dft_Write Default writer using to_str()

Definition at line 265 of file generate_tree.H.

References Aleph::escape_dot_label(), out, root(), and Aleph::traverse().

infix()

template<BinNodeLike 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 465 of file tpl_binNodeUtils.H.

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

infix_traverse()

template<BinNodeLike 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 2817 of file tpl_binNodeUtils.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::BinNodeInfixIterator< Node >::has_curr(), 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 618 of file tpl_binTreeOps.H.

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

inorder_position() [2/2]

template<RankedBinNodeLike 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 221 of file tpl_binNodeXt.H.

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

Referenced by Aleph::inorder_position(), Aleph::inorder_position(), Aleph::inorder_position(), Aleph::inorder_position(), main(), 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<BinNodeLike 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:

1. p: pointer to visited node.
2. level: level of node p.

3. 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 118 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), Aleph::inorder_rec_helper(), and root().

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

inOrderThreaded()

template<BinNodeLike 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:

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

Parameters

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

See also

preOrderThreaded()

Definition at line 887 of file tpl_binNodeUtils.H.

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

Referenced by TEST().

insert_by_key_xt()

template<RankedBinNodeLike 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 355 of file tpl_binNodeXt.H.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::COUNT(), Aleph::insert_by_key_xt(), KEY, LLINK, r, and 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(), TEST(), and TEST().

insert_by_pos_xt()

template<RankedBinNodeLike 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 758 of file tpl_binNodeXt.H.

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

Referenced by main(), and TEST().

insert_dup_by_key_xt()

template<RankedBinNodeLike 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 400 of file tpl_binNodeXt.H.

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

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

insert_dup_in_bst()

template<BinNodeLike 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 1713 of file tpl_binNodeUtils.H.

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

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

insert_dup_root()

template<BinNodeLike 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 1969 of file tpl_binNodeUtils.H.

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

Referenced by TEST().

insert_dup_root_xt()

template<RankedBinNodeLike 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 659 of file tpl_binNodeXt.H.

References cmp(), Aleph::COUNT(), KEY, LLINK, 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<BinNodeLike 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 1683 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), cmp(), KEY, LLINK, r, and 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 800 of file tpl_binTreeOps.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::COUNT(), KEY, LLINK, 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<BinNodeLike 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 1943 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), cmp(), KEY, l, LLINK, r, 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<BinNodeLike 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 2327 of file tpl_binNodeUtils.H.

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

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

insert_root_xt()

template<RankedBinNodeLike 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 618 of file tpl_binNodeXt.H.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::COUNT(), KEY, LLINK, 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<BinNodeLike 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 998 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), and Aleph::internal_path_length_helper().

Referenced by benchmark_set(), Aleph::DynSetTree< Key, Tree, Compare >::internal_path_length(), main(), 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 1265 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(), Aleph::DynSetTree< Key, Tree, Compare >::join(), TEST(), TEST(), and TEST().

join() [2/2]

template<BinNodeLike 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 2024 of file tpl_binNodeUtils.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::insert_in_bst(), Aleph::insert_root(), Aleph::join(), KEY, l, LLINK, r, Aleph::remove_from_bst(), and 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 1301 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(), and TEST().

join_exclusive()

template<BinNodeLike 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 1879 of file tpl_binNodeUtils.H.

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

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

join_exclusive_xt()

template<RankedBinNodeLike 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 780 of file tpl_binNodeXt.H.

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

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

join_preorder()

template<BinNodeLike 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 1990 of file tpl_binNodeUtils.H.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::insert_in_bst(), Aleph::join_preorder(), l, LLINK, r, and 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 358 of file tpl_binNode.H.

lazy_in_order()

template<class Node >

Aleph::Generator< Node * > Aleph::lazy_in_order

(

Node *

root

)

Lazily traverse a binary tree in-order (left, node, right).

Yields nodes in ascending key order for a valid BST.

Template Parameters

Node	Binary tree node type providing getL()/getR() and a NullPtr sentinel (any Aleph binary tree node, e.g. BinNode, Avl_Node, Rb_Tree_Node…).

Parameters

root	Root of the (sub)tree to traverse; Node::NullPtr yields an empty sequence.

Returns

A lazy sequence of Node *, one per visited node, in in-order.

Note

Complexity: O(1) amortized per yielded node; O(depth) explicit stack entries in the wrapped BinNodeInfixIterator.

Exception safety: basic guarantee. Constructing the wrapped BinNodeInfixIterator may throw std::bad_alloc; once construction succeeds, the traversal itself does not throw (it only follows existing getL()/getR() links).

Thread safety: read-only traversal via raw pointers, with no internal synchronization. Traversing different trees concurrently is safe; traversing or mutating the same tree from multiple threads (including mutating it from the loop body driving this generator) is not, and needs external synchronization.

Definition at line 110 of file tpl_binNodeGenerators.H.

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

Referenced by TEST().

lazy_post_order()

template<class Node >

Aleph::Generator< Node * > Aleph::lazy_post_order

(

Node *

root

)

Lazily traverse a binary tree post-order (left, right, node).

Template Parameters

Node	Binary tree node type (see lazy_in_order).

Parameters

root	Root of the (sub)tree to traverse; Node::NullPtr yields an empty sequence.

Returns

A lazy sequence of Node *, one per visited node, in post-order.

Note

Complexity: O(1) amortized per yielded node; O(depth) explicit ArrayStack<Node *> entries.

Exception safety: basic guarantee. Constructing the internal ArrayStack<Node *> may throw std::bad_alloc; once construction succeeds, the traversal itself does not throw.

Thread safety: same as lazy_in_order — read-only, no internal synchronization; safe across different trees, not safe on a shared or concurrently-mutated tree.

Explicit stack replacing the call stack a recursive post-order would use, sized to the tree's maximum height.

Definition at line 170 of file tpl_binNodeGenerators.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::ArrayStack< T >::is_empty(), LLINK, Aleph::ArrayStack< T >::pop(), Aleph::ArrayStack< T >::push(), RLINK, root(), and Aleph::ArrayStack< T >::top().

lazy_pre_order()

template<class Node >

Aleph::Generator< Node * > Aleph::lazy_pre_order

(

Node *

root

)

Lazily traverse a binary tree pre-order (node, left, right).

Template Parameters

Node	Binary tree node type (see lazy_in_order).

Parameters

root	Root of the (sub)tree to traverse; Node::NullPtr yields an empty sequence.

Returns

A lazy sequence of Node *, one per visited node, in pre-order.

Note

Complexity: O(1) amortized per yielded node; O(depth) explicit stack entries in the wrapped BinNodePrefixIterator.

Exception safety: basic guarantee. Constructing the wrapped BinNodePrefixIterator may throw std::bad_alloc; once construction succeeds, the traversal itself does not throw.

Thread safety: same as lazy_in_order — read-only, no internal synchronization; safe across different trees, not safe on a shared or concurrently-mutated tree.

Definition at line 140 of file tpl_binNodeGenerators.H.

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

level_traverse()

template<BinNodeLike 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 726 of file tpl_binNodeUtils.H.

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

Referenced by main().

levelOrder()

template<BinNodeLike 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:

1. p: pointer to currently visited node
2. pos: ordinal indicating the visit order
3. 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 686 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), Aleph::DynListQueue< T >::get(), Aleph::DynListQueue< T >::is_empty(), LLINK, Aleph::DynListQueue< T >::put(), 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 325 of file tpl_binNode.H.

load_tree()

template<BinNodeLike 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 1210 of file tpl_binNodeUtils.H.

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

load_tree_from_array()

template<BinNodeLike 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 1345 of file tpl_binNodeUtils.H.

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

load_tree_keys_in_prefix()

template<BinNodeLike 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 1163 of file tpl_binNodeUtils.H.

References ah_runtime_error_if, Aleph::blossom_maximum_cardinality_matching(), LLINK, Aleph::load_tree_keys_in_prefix(), 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 539 of file tpl_rand_tree.H.

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

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 580 of file tpl_treapRk.H.

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

Referenced by main().

postOrderRec()

template<BinNodeLike 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:

1. p: pointer to visited node.
2. level: level of node p.

3. 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 208 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), Aleph::postorder_rec_helper(), and root().

Referenced by main().

prefix()

template<BinNodeLike 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 450 of file tpl_binNodeUtils.H.

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

prefix_traverse()

template<BinNodeLike 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 2579 of file tpl_binNodeUtils.H.

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

preorder_to_bst()

template<BinNodeLike 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 1401 of file tpl_binNodeUtils.H.

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

preOrderRec()

template<BinNodeLike 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:

1. p: pointer to visited node.
2. level: level of node p.

3. 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 163 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), Aleph::preorder_rec_helper(), and root().

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

preOrderThreaded()

template<BinNodeLike 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:

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

Parameters

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

See also

inOrderThreaded()

Definition at line 944 of file tpl_binNodeUtils.H.

References Aleph::and, LLINK, r, and RLINK.

Referenced by main(), and 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.

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::init(), Aleph::Gen_Treap< NodeType, Key, Compare >::init(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::init(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), Aleph::is_treap(), Aleph::Gen_Treap< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::join_exclusive(), main(), Aleph::Gen_Treap< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert(), and TEST_F().

remove_by_key_xt()

template<RankedBinNodeLike 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 819 of file tpl_binNodeXt.H.

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

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

remove_by_pos_xt()

template<RankedBinNodeLike 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 897 of file tpl_binNodeXt.H.

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

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

remove_from_bst()

template<BinNodeLike 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 1908 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::join_exclusive(), KEY, LLINK, Aleph::remove_from_bst(), RLINK, and root().

Referenced by Aleph::join(), main(), 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 341 of file tpl_binNode.H.

rotate_to_left() [1/2]

template<BinNodeLike 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 2101 of file tpl_binNodeUtils.H.

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

Referenced by Aleph::HtdRbTree< Key, Compare >::balanceDownAndColor(), Aleph::HtdRbTree< Key, Compare >::doubleRotateNephewAndColor(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::fix_black_condition(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::fix_red_condition(), Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoLeftAndColorRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoRightAndColorRed(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), Aleph::BinTree_Operation< Node, Cmp >::insert_root_rec(), Aleph::insert_root_rec(), Aleph::Gen_Treap< NodeType, Key, Compare >::remove(), Aleph::HtdRbTree< Key, Compare >::restoreRedCondition(), Aleph::GenTdRbTree< NodeType, Key, Compare >::restoreRedCondition(), Aleph::HtdRbTree< Key, Compare >::rotateNephewAndColor(), Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert(), Aleph::BinTree_Operation< Node, Cmp >::search_or_insert_root_rec(), Aleph::search_or_insert_root_rec(), GenTdSplayTree< NodeType, Key, Compare >::splay_impl(), and TEST().

rotate_to_left() [2/2]

template<BinNodeLike 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 2119 of file tpl_binNodeUtils.H.

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

rotate_to_left_xt()

template<RankedBinNodeLike 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 948 of file tpl_binNodeXt.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::COUNT(), LLINK, and 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<BinNodeLike 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 2058 of file tpl_binNodeUtils.H.

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

Referenced by Aleph::HtdRbTree< Key, Compare >::balanceDownAndColor(), Aleph::HtdRbTree< Key, Compare >::doubleRotateNephewAndColor(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::fix_black_condition(), Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::fix_red_condition(), Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoLeftAndColorRed(), Aleph::GenTdRbTree< NodeType, Key, Compare >::gotoRightAndColorRed(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap< NodeType, Key, Compare >::insert_dup(), Aleph::BinTree_Operation< Node, Cmp >::insert_root_rec(), Aleph::insert_root_rec(), Aleph::Gen_Treap< NodeType, Key, Compare >::remove(), Aleph::HtdRbTree< Key, Compare >::restoreRedCondition(), Aleph::GenTdRbTree< NodeType, Key, Compare >::restoreRedCondition(), Aleph::HtdRbTree< Key, Compare >::rotateNephewAndColor(), Aleph::Gen_Treap< NodeType, Key, Compare >::search_or_insert(), Aleph::BinTree_Operation< Node, Cmp >::search_or_insert_root_rec(), Aleph::search_or_insert_root_rec(), GenTdSplayTree< NodeType, Key, Compare >::splay_impl(), and TEST().

rotate_to_right() [2/2]

template<BinNodeLike 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 2077 of file tpl_binNodeUtils.H.

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

rotate_to_right_xt()

template<RankedBinNodeLike 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 927 of file tpl_binNodeXt.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::COUNT(), LLINK, and 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<BinNodeLike 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 1190 of file tpl_binNodeUtils.H.

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

Referenced by main(), and TEST().

save_tree_in_array_of_chars()

template<BinNodeLike 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 1304 of file tpl_binNodeUtils.H.

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

save_tree_keys_in_prefix()

template<BinNodeLike 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 1141 of file tpl_binNodeUtils.H.

References LLINK, output, 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 1342 of file tpl_tree_node.H.

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

Referenced by TEST_F().

search_or_insert_in_bst()

template<BinNodeLike 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 1743 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), cmp(), KEY, LLINK, r, and RLINK.

Referenced by TEST().

search_or_insert_root_rec()

template<BinNodeLike 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 2369 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), cmp(), KEY, LLINK, 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<BinNodeLike 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 1595 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::CmpGreater, Aleph::CmpLess, KEY, LLINK, 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 122 of file tpl_binTreeOps.H.

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

search_rank_parent() [2/2]

template<BinNodeLike 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 1645 of file tpl_binNodeUtils.H.

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

Referenced by TEST().

searchInBinTree()

template<BinNodeLike 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 1466 of file tpl_binNodeUtils.H.

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

Referenced by main(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::search(), 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(), TEST(), TEST(), and TEST().

select()

template<RankedBinNodeLike 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 166 of file tpl_binNodeXt.H.

References ah_out_of_range_error_if, Aleph::COUNT(), r, 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(), 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::blossom_maximum_cardinality_matching(), Aleph::COUNT(), LLINK, 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<RankedBinNodeLike 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 134 of file tpl_binNodeXt.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::COUNT(), LLINK, r, and RLINK.

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

select_rec()

template<RankedBinNodeLike 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 116 of file tpl_binNodeXt.H.

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

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

split_key()

template<BinNodeLike 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 2153 of file tpl_binNodeUtils.H.

References Aleph::and, Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), cmp(), KEY, l, LLINK, r, RLINK, and root().

Referenced by main(), and TEST().

split_key_dup_rec()

template<BinNodeLike 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 1857 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), cmp(), 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<BinNodeLike 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 585 of file tpl_binNodeXt.H.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), l, r, 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<BinNodeLike 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 1810 of file tpl_binNodeUtils.H.

References Aleph::assert_valid_tree_root(), Aleph::blossom_maximum_cardinality_matching(), cmp(), root(), and Aleph::split_key_rec_helper().

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

split_key_rec_xt()

template<BinNodeLike 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 525 of file tpl_binNodeXt.H.

References Aleph::__split_key_rec_xt(), Aleph::blossom_maximum_cardinality_matching(), cmp(), l, r, 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<RankedBinNodeLike 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 727 of file tpl_binNodeXt.H.

References ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::COUNT(), and r.

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<BinNodeLike 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 480 of file tpl_binNodeUtils.H.

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

swap_node_with_predecessor()

template<BinNodeLike 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 2270 of file tpl_binNodeUtils.H.

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

swap_node_with_successor()

template<BinNodeLike 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 2218 of file tpl_binNodeUtils.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), LLINK, and 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 1442 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:

1. p: pointer to the currently visited node.
2. level: the level of p in the tree.
3. 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 1063 of file tpl_tree_node.H.

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

Referenced by main(), and 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:

1. p: pointer to the currently visited node.
2. level: the level of p in the tree.
3. 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 988 of file tpl_tree_node.H.

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

Referenced by compute_coordinates_for_forest_and_set_picture_size(), compute_coordinates_for_tree(), and main().

tree_to_bits() [1/2]

template<BinNodeLike 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 1045 of file tpl_binNodeUtils.H.

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

tree_to_bits() [2/2]

template<BinNodeLike 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 1018 of file tpl_binNodeUtils.H.

References LLINK, Aleph::BitArray::push(), 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().