Functor encompassing basic operation for extended binary search trees. More...

#include <tpl_binTreeOps.H>

Inheritance diagram for Aleph::BinTreeXt_Operation< Node, Cmp >:

Collaboration diagram for Aleph::BinTreeXt_Operation< Node, Cmp >:

Public Types
using	Key = typename Node::key_type

Public Types inherited from Aleph::BinTree_Operation< Node, Cmp >
using	Key = typename Node::key_type

using	key_type = typename Node::key_type
	The type of key.

Public Member Functions
	BinTreeXt_Operation (Cmp cmp=Cmp()) noexcept
	Initialize the functor with comparison criteria `cmp`

long	inorder_position (Node r, const Key &key, Node &p) noexcept
	Compute the inorder position of a key.

long	find_position (Node r, const Key &key, Node &p) noexcept
	Find the inorder position of a key in an extended binary search tree.

bool	split_key_rec (Node root, const Key &key, Node &l, Node *&r) noexcept
	Split an extended binary search tree according to a key.

void	split_key_dup_rec (Node root, const Key &key, Node &l, Node *&r) noexcept
	Split an extended binary search tree according to a key which can be in the tree.

Node *	insert_root (Node &root, Node p) noexcept
	Insert a node `p` as root of an extended binary search tree.

Node *	insert_dup_root (Node &root, Node p) noexcept
	Insert a node as root of an extended binary search tree.

Public Member Functions inherited from Aleph::BinTree_Operation< Node, Cmp >
Cmp &	key_comp () noexcept
	Return the comparison criteria.

Cmp &	get_compare () noexcept

	BinTree_Operation (Cmp cmp_=Cmp()) noexcept
	The type of key.

Node *	search (Node *root, const Key &key) noexcept
	Search a node with a specific key.

Node *	search_parent (Node root, const Key &key, Node &parent) noexcept
	Search a key and find its node and parent.

Node *	search_rank_parent (Node *root, const Key &key) noexcept
	Rank search of a key in a binary search tree.

Node *	insert (Node &root, Node p) noexcept
	Insert a node `p` in a binary search tree.

Node *	insert_dup (Node &root, Node p) noexcept
	Insert a node `p` in a binary search tree.

Node *	search_or_insert (Node &r, Node p) noexcept
	Search or insert a node in a binary search tree.

bool	split_key_rec (Node &root, const Key &key, Node &ts, Node *&tg) noexcept
	Split recursively according to a key.

void	split_key_dup_rec (Node &root, const typename Node::key_type &key, Node &ts, Node *&tg) noexcept
	Split a tree according to a key value.

Node *	remove (Node *&root, const Key &key) noexcept
	Remove a key from a binary search tree.

Node *	insert_root (Node &root, Node p) noexcept
	Insert the node `p` as the root of a binary search tree.

Node *	insert_dup_root (Node &root, Node p) noexcept
	Insert node `p` as root of a binary search tree.

Node *	join_preorder (Node t1, Node t2, Node *&dup) noexcept
	Union of two binary search trees.

Node *	join (Node t1, Node t2, Node *&dup) noexcept
	Fast union of two binary search trees.

void	split_key (Node root, const Key &key, Node &l, Node *&r) noexcept
	Split a binary search tree according to a key.

Node *	insert_root_rec (Node root, Node p) noexcept
	Insert a node as root in a binary search tree.

Node *	search_or_insert_root_rec (Node root, Node p) noexcept
	Search and eventually insert `p` as root in a binary search tree.

Related Symbols
(Note that these are not member symbols.)
	inorder_position

	inorder_position

	inorder_position

Additional Inherited Members
Protected Attributes inherited from Aleph::BinTree_Operation< Node, Cmp >
Cmp	cmp

Detailed Description

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

Functor encompassing basic operation for extended binary search trees.

See also: BinNode

Definition at line 594 of file tpl_binTreeOps.H.

Member Typedef Documentation

◆ Key

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

using Aleph::BinTreeXt_Operation< Node, Cmp >::Key = typename Node::key_type

Definition at line 597 of file tpl_binTreeOps.H.

Constructor & Destructor Documentation

◆ BinTreeXt_Operation()

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

Aleph::BinTreeXt_Operation< Node, Cmp >::BinTreeXt_Operation ( Cmp cmp = Cmp() )

inlinenoexcept

Initialize the functor with comparison criteria cmp

Definition at line 600 of file tpl_binTreeOps.H.

Member Function Documentation

◆ find_position()

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

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

inlinenoexcept

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

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

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

Parameters

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

Returns: the positions of key in the tree

Definition at line 665 of file tpl_binTreeOps.H.

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

◆ insert_dup_root()

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

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

inlinenoexcept

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

insert_dup_root(root, p) 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

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

Definition at line 823 of file tpl_binTreeOps.H.

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

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

◆ split_key_dup_rec()

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

void Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_dup_rec	(	Node *	root,
		const Key &	key,
		Node *&	l,
		Node *&	r
	)

inlinenoexcept

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

split_key__dup_rec(root, key, l, r) 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`

Definition at line 761 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, Aleph::COUNT(), KEY, l, Aleph::LLINK(), Aleph::RLINK(), root(), and Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_dup_rec().

Referenced by Aleph::BinTreeXt_Operation< Node, Cmp >::insert_dup_root(), and Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_dup_rec().

◆ split_key_rec()

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

bool Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_rec	(	Node *	root,
		const Key &	key,
		Node *&	l,
		Node *&	r
	)

inlinenoexcept

Split an extended binary search tree according to a key.

split_key_rec(root, key, l, r) splits a tree according a non-existing key

Parameters

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

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

Definition at line 719 of file tpl_binTreeOps.H.

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

Referenced by Aleph::BinTreeXt_Operation< Node, Cmp >::insert_root(), and Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_rec().

Friends And Related Symbol Documentation

◆ inorder_position() [1/3]

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

Aleph::inorder_position ( )

Referenced by Aleph::BinTreeXt_Operation< Node, Cmp >::inorder_position().

◆ inorder_position() [2/3]

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

Aleph::inorder_position ( )

◆ inorder_position() [3/3]

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

Aleph::inorder_position ( )

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Related Symbols

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Key

Constructor & Destructor Documentation

◆ BinTreeXt_Operation()

Member Function Documentation

◆ find_position()

◆ insert_dup_root()

◆ split_key_dup_rec()

◆ split_key_rec()

Friends And Related Symbol Documentation

◆ inorder_position() [1/3]

◆ inorder_position() [2/3]

◆ inorder_position() [3/3]