#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

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

long	find_position (Node r, const Key &key, Node &p) noexcept

bool	split_key_rec (Node root, const Key &key, Node &l, Node *&r) noexcept

void	split_key_dup_rec (Node root, const Key &key, Node &l, Node *&r) noexcept

Node *	insert_root (Node &root, Node p) noexcept

Node *	insert_dup_root (Node &root, Node p) noexcept

Cmp &	key_comp () noexcept
	Return the comarison criteria.

Cmp &	get_compare () noexcept

Node *	search (Node *root, const Key &key) noexcept

Node *	search_parent (Node root, const Key &key, Node &parent) noexcept

Node *	search_rank_parent (Node *root, const Key &key) noexcept

Node *	insert (Node &root, Node p) noexcept

Node *	insert_dup (Node &root, Node p) noexcept

Node *	search_or_insert (Node &r, Node p) noexcept

bool	split_key_rec (Node &root, const Key &key, Node &ts, Node *&tg) noexcept

Node *	remove (Node *&root, const Key &key) noexcept

Node *	join_preorder (Node t1, Node t2, Node *&dup) noexcept

Node *	join (Node t1, Node t2, Node *&dup) noexcept

void	split_key (Node root, const Key &key, Node &l, Node *&r) noexcept

Node *	insert_root_rec (Node root, Node p) noexcept

Node *	search_or_insert_root_rec (Node root, Node p) noexcept

Protected Attributes
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

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 inmediataly greater than key.

Parameters

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

Returns: the positions of key in the tree

Here is the call graph for this function:

◆ get_compare()

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

Cmp& Aleph::BinTree_Operation< Node, Cmp >::get_compare ( )

inlinenoexceptinherited

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ insert()

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

Node* Aleph::BinTree_Operation< Node, Cmp >::insert	(	Node *&	root,
		Node *	p
	)

inlinenoexceptinherited

Insert a node p in a binary search tree

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

Parameters

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert_dup()

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

Node* Aleph::BinTree_Operation< Node, Cmp >::insert_dup	(	Node *&	root,
		Node *	p
	)

inlinenoexceptinherited

Insert a node p in a binary search tree

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

Returns: the pointer p

Here is the call graph for this function:

◆ 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 isnerted node p that has became root

Here is the call graph for this function:

◆ insert_root_rec()

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

Node* Aleph::BinTree_Operation< Node, Cmp >::insert_root_rec	(	Node *	root,
		Node *	p
	)

inlinenoexceptinherited

Insert a node as root in a binary search tree.

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

Parameters

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

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

Here is the call graph for this function:

◆ join()

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

Node* Aleph::BinTree_Operation< Node, Cmp >::join	(	Node *	t1,
		Node *	t2,
		Node *&	dup
	)

inlinenoexceptinherited

Fast union of two binary search trees

join(t1, t2, dup) 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

Returns: pointer to the root of resulting join

Here is the call graph for this function:

◆ join_preorder()

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

Node* Aleph::BinTree_Operation< Node, Cmp >::join_preorder	(	Node *	t1,
		Node *	t2,
		Node *&	dup
	)

inlinenoexceptinherited

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

Returns: a pointer to the resulting root of tree

Here is the call graph for this function:

◆ remove()

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

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

inlinenoexceptinherited

Remove a key from a binary search tree

Parameters

[in,out]	root	of tree
[in]	key	to remove

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

Here is the call graph for this function:

◆ search()

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

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

inlinenoexceptinherited

Search a node with a specific key.

Parameters

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

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

Here is the call graph for this function:

◆ search_or_insert()

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

Node* Aleph::BinTree_Operation< Node, Cmp >::search_or_insert	(	Node *&	r,
		Node *	p
	)

inlinenoexceptinherited

Search or insert a node in a binary search tree.

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

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

Here is the call graph for this function:

◆ search_or_insert_root_rec()

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

Node* Aleph::BinTree_Operation< Node, Cmp >::search_or_insert_root_rec	(	Node *	root,
		Node *	p
	)

inlinenoexceptinherited

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

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

Here is the call graph for this function:

◆ search_parent()

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

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

inlinenoexceptinherited

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 indetermined

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

◆ split_key()

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

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

inlinenoexceptinherited

Split a binary search tree according to a key.

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

Parameters

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

Here is the call graph for this function:

◆ 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 accoding 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`

Here is the call graph for this function:

◆ split_key_rec() [1/2]

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

bool Aleph::BinTree_Operation< Node, Cmp >::split_key_rec	(	Node *&	root,
		const Key &	key,
		Node *&	ts,
		Node *&	tg
	)

inlinenoexceptinherited

Split recursively according to a key.

split_key_rec(root, key, ts, tg) 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`

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ split_key_rec() [2/2]

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

Here is the call graph for this function:

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

tpl_binTreeOps.H

Public Types

Public Member Functions

Protected Attributes

Detailed Description

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

Member Function Documentation

◆ find_position()

◆ get_compare()

◆ insert()

◆ insert_dup()

◆ insert_dup_root()

◆ insert_root_rec()

◆ join()

◆ join_preorder()

◆ remove()

◆ search()

◆ search_or_insert()

◆ search_or_insert_root_rec()

◆ search_parent()

◆ split_key()

◆ split_key_dup_rec()

◆ split_key_rec() [1/2]

◆ split_key_rec() [2/2]

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