tpl_binNodeXt.H File Reference

Extended binary node with subtree count. More...

#include <tpl_binNode.H>
#include <tpl_binNodeUtils.H>

Include dependency graph for tpl_binNodeXt.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::BinNodeXt_Data
class	Aleph::BinNodeXt< Key >
	Node for extended binary search tree. More...
class	Aleph::BinNodeXtVtl< Key >
class	Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >
	Base iterator template for ranked binary search trees. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<class Node >
auto &	Aleph::COUNT (Node *p) noexcept
	Return the number of nodes of the tree fron p is root.
template<class Node >
static Node *	Aleph::__select_rec (Node *r, const size_t i) noexcept
template<class Node >
Node *	Aleph::select_rec (Node *r, const size_t i)
	Recursively select the i-th node inorder sense.
template<class Node >
Node *	Aleph::select_ne (Node *r, const size_t pos) noexcept
	Iterative selection of a node according to inorder position without exception.
template<class Node >
Node *	Aleph::select (Node *r, const size_t pos)
	Iterative selection of a node according to inorder position.
template<class Node >
Node *	Aleph::select (Node *root, const size_t pos, Node *&parent)
	Iterative selection of a node according to inorder psoition and determination of parent of selected node.
template<class Node , class Compare >
long	Aleph::inorder_position (Node *r, const typename Node::key_type &key, Node *&p, Compare &cmp) noexcept
	Compute the inorder position of a key.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
long	Aleph::inorder_position (Node *r, const typename Node::key_type &key, Node *&p, Compare &&cmp=Compare()) noexcept
template<class Node , class Compare >
long	Aleph::inorder_position (Node *r, const typename Node::key_type &key, Compare &cmp) noexcept
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
long	Aleph::inorder_position (Node *r, const typename Node::key_type &key, Compare &&cmp=Compare()) noexcept
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
long	Aleph::find_position (Node *r, const typename Node::key_type &key, Node *&p, Compare &cmp) noexcept
	Find the inorder position of a key in an extended binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
long	Aleph::find_position (Node *r, const typename Node::key_type &key, Node *&p, Compare &&cmp=Compare()) noexcept
template<class Node , class Compare >
Node *	Aleph::insert_by_key_xt (Node *&r, Node *p, Compare &cmp) noexcept
	Insert a node in an extended binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_by_key_xt (Node *&r, Node *p, Compare &&cmp=Compare()) noexcept
template<class Node , class Compare >
Node *	Aleph::insert_dup_by_key_xt (Node *&r, Node *p, Compare &cmp) noexcept
	Insert a node in an extended binary search tree without testing for duplicity.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_dup_by_key_xt (Node *&r, Node *p, Compare &&cmp=Compare()) noexcept
template<class Node , class Compare >
Node *	Aleph::search_or_insert_by_key_xt (Node *&r, Node *p, Compare &cmp) noexcept
	Search or insert a node in an extended binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_or_insert_by_key_xt (Node *&r, Node *p, Compare &&cmp=Compare()) noexcept
template<class Node , class Compare >
static bool	Aleph::__split_key_rec_xt (Node *root, const typename Node::key_type &key, Node *&l, Node *&r, Compare &cmp) noexcept
template<class Node , class Compare >
bool	Aleph::split_key_rec_xt (Node *&root, const typename Node::key_type &key, Node *&l, Node *&r, Compare &cmp) noexcept
	Split an extended binary search tree according to a key.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
bool	Aleph::split_key_rec_xt (Node *&root, const typename Node::key_type &key, Node *&l, Node *&r, Compare &&cmp=Compare()) noexcept
template<class Node , class Compare >
static void	Aleph::__split_key_dup_rec_xt (Node *root, const typename Node::key_type &key, Node *&l, Node *&r, Compare &cmp) noexcept
template<class Node , class Compare >
void	Aleph::split_key_dup_rec_xt (Node *&root, const typename Node::key_type &key, Node *&l, Node *&r, Compare &cmp) noexcept
	Split an extended binary search tree according to a key which can be in the tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
void	Aleph::split_key_dup_rec_xt (Node *&root, const typename Node::key_type &key, Node *&l, Node *&r, Compare &&cmp=Compare()) noexcept
template<class Node , class Compare >
Node *	Aleph::insert_root_xt (Node *&root, Node *p, Compare &cmp) noexcept
	Insert a node p as root of an extended binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_root_xt (Node *&root, Node *p, Compare &&cmp=Compare()) noexcept
template<class Node , class Compare >
Node *	Aleph::insert_dup_root_xt (Node *&root, Node *p, Compare &cmp) noexcept
	Insert a node as root of an extended binary search tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::insert_dup_root_xt (Node *&root, Node *p, Compare &&cmp=Compare()) noexcept
template<class Node >
static void	Aleph::__split_pos_rec (Node *r, size_t i, Node *&ts, Node *&tg) noexcept
template<class Node >
void	Aleph::split_pos_rec (Node *&r, const size_t i, Node *&ts, Node *&tg)
	Split a extended binary tree according to a position.
template<class Node >
void	Aleph::insert_by_pos_xt (Node *&r, Node *p, size_t pos)
	Insert a node in a specific inorder position in a binary tree.
template<class Node >
Node *	Aleph::join_exclusive_xt (Node *&ts, Node *&tg) noexcept
	Exclusive union of two extended binary search trees.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::remove_by_key_xt (Node *&root, const typename Node::key_type &key, Compare &cmp) noexcept
	Remove a key of extended binary tree.
template<class Node , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::remove_by_key_xt (Node *&root, const typename Node::key_type &key, Compare &&cmp=Compare()) noexcept
template<class Node >
static Node *	Aleph::__remove_by_pos_xt (Node *&root, size_t pos) noexcept
template<class Node >
Node *	Aleph::remove_by_pos_xt (Node *&root, size_t pos)
	Remove from a extended binary tree the node whose inorder position is pos.
template<class Node >
bool	Aleph::check_rank_tree (Node *root) noexcept
	Return true if root is a valid extended binary tree.
template<class Node >
Node *	Aleph::rotate_to_right_xt (Node *p) noexcept
	Rotate to right the extended bianry tree with root p
template<class Node >
Node *	Aleph::rotate_to_left_xt (Node *p) noexcept
	Rotate to left the extended binary tree with root p.
template<class Node , class Key , class Compare >
Node *	Aleph::search_or_insert_root_rec_xt (Node *root, Node *p, Compare &cmp) noexcept
	Search or insert a key in an extended binary search tree.
template<class Node , class Key , class Compare = Aleph::less<typename Node::key_type>>
Node *	Aleph::search_or_insert_root_rec_xt (Node *root, Node *p, Compare &&cmp=Compare()) noexcept

Detailed Description

Extended binary node with subtree count.

Binary node augmented with subtree size for order statistics.

See also

tpl_binNodeAux.H Base node

Author

Leandro Rabindranath León

Definition in file tpl_binNodeXt.H.