#include <tpl_binTree.H>

Inheritance diagram for Aleph::BinTree< Key, Compare >:

Collaboration diagram for Aleph::BinTree< Key, Compare >:

Public Types
using	Base = GenBinTree< BinNode, Key, Compare >

using	Node = BinNode< Key >

Public Member Functions
void	swap (GenBinTree &tree) noexcept
	Swap `this` with `tree` in constant time.

Compare &	key_comp () noexcept
	return the comparison criteria

Compare &	get_compare () noexcept

Node *	search (const Key &key) const noexcept

bool	verify () const
	Return `true` if the tree is a consistent (correct) binary search tree.

Node *&	getRoot ()
	Return the root of tree.

bool	verifyBin () const

Node *	insert (Node *p) noexcept

Node *	insert_dup (Node *p) noexcept

Node *	search_or_insert (Node *p) noexcept

bool	split (const Key &key, GenBinTree &l, GenBinTree &r) noexcept

void	split_dup (const Key &key, GenBinTree &l, GenBinTree &r) noexcept

Node *	remove (const Key &key) noexcept

void	join (GenBinTree &tree, GenBinTree &dup) noexcept

void	join_dup (GenBinTree &t) noexcept

void	join_exclusive (GenBinTree &t) noexcept

Detailed Description

template<typename Key, class Compare = Aleph::less<Key>>
struct Aleph::BinTree< Key, Compare >

Binary search tree with nodes without virtual destructors,

See also: GenBinTree BinTreeVtl DynBinTree

Member Function Documentation

◆ get_compare()

Compare& Aleph::GenBinTree< BinNode , Key, Compare >::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()

Node* Aleph::GenBinTree< BinNode , Key, Compare >::insert ( Node * p )

inlinenoexceptinherited

Insert a node in the tree

Parameters

[in] p pointer to the node to insert

Returns: if p->get_key() is not in the tree, then the pointer p is returned (it was inserted); othewise, nullptr is returned

◆ insert_dup()

Node* Aleph::GenBinTree< BinNode , Key, Compare >::insert_dup ( Node * p )

inlinenoexceptinherited

Insert a node in the tree.

This method does not fail. It always inserts.

Parameters

[in] p pointer to the node to insert

Returns: the p pointer

◆ join()

void Aleph::GenBinTree< BinNode , Key, Compare >::join	(	GenBinTree< BinNode, Key, Compare > &	tree,
		GenBinTree< BinNode, Key, Compare > &	dup
	)

inlinenoexceptinherited

Join tree with this. Duplicated keys of tree are put in dup parameter.

Parameters

[in,out]	tree	to join with `this`
[out]	dup	tree where the duplicated key belonging to `tree` are put.

◆ join_dup()

void Aleph::GenBinTree< BinNode , Key, Compare >::join_dup ( GenBinTree< BinNode, Key, Compare > & t )

inlinenoexceptinherited

Join this with t independently of the presence of duplicated keys

join(t) produces a random tree result of join of this and t. The resulting tree is stored in this.

Parameters

[in] t tree to join with this keys are inserted

◆ join_exclusive()

void Aleph::GenBinTree< BinNode , Key, Compare >::join_exclusive ( GenBinTree< BinNode, Key, Compare > & t )

inlinenoexceptinherited

Join exclusive of this with t

Exclusive means that all the keys of this are lesser than all the keys of t. This knowlege allows a more effcient way for joining that when the keys ranks are overlapped. However, use very carefully because the algorithm does not perform any check and the result would be incorrect.

Parameters

[in] t tree to exclusively join with this keys are inserted

◆ remove()

Node* Aleph::GenBinTree< BinNode , Key, Compare >::remove ( const Key & key )

inlinenoexceptinherited

Remove a key from the tree

Parameters

[in] key to remove

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

◆ search()

Node* Aleph::GenBinTree< BinNode , Key, Compare >::search ( const Key & key ) const

inlinenoexceptinherited

Search a key.

Parameters

[in] key to be searched

Returns: a pointer to the containing key if this was found; otherwise nullptr

◆ search_or_insert()

Node* Aleph::GenBinTree< BinNode , Key, Compare >::search_or_insert ( Node * p )

inlinenoexceptinherited

Search or insert a key.

search_or_insert(p) searches in the tree the key KEY(p). If this key is found, then a pointer to the node containing it is returned. Otherwise, p is inserted.

Parameters

[in] p node containing a key to be searched and eventually inserted

Returns: if the key contained in p is found, then a pointer to the containing key in the tree is returned. Otherwise, p is inserted and returned

◆ split()

bool Aleph::GenBinTree< BinNode , Key, Compare >::split	(	const Key &	key,
		GenBinTree< BinNode, Key, Compare > &	l,
		GenBinTree< BinNode, Key, Compare > &	r
	)

inlinenoexceptinherited

Split the tree according to a key

split(key, l, r) splits the tree according to key. That is, if key is not present in the tree, then the tree is split in two trees l which contains the key lesser than key and r which contains the keys greater than key. If key is found in the tree, then the split is not done

Parameters

[in]	key	for splitting
[out]	l	resulting tree with the keys lesser than `key`
[out]	r	resulting tree with the keys greater than `key`

Returns: true if the tree was split. false otherwise

◆ split_dup()

void Aleph::GenBinTree< BinNode , Key, Compare >::split_dup	(	const Key &	key,
		GenBinTree< BinNode, Key, Compare > &	l,
		GenBinTree< BinNode, Key, Compare > &	r
	)

inlinenoexceptinherited

Split the tree according to a key that could be in the tree

split_dup(key, l, r) splits the tree according to key in two trees l which contains the key lesser than key and r which contains the keys greater or equal than key.

Parameters

[in]	key	for splitting
[out]	l	resulting tree with the keys lesser than `key`
[out]	r	resulting tree with the keys greater or equal than `key`

◆ verifyBin()

bool Aleph::GenBinTree< BinNode , Key, Compare >::verifyBin ( ) const

inlineinherited

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

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

tpl_binTree.H

Public Types

Public Member Functions

Detailed Description

template<typename Key, class Compare = Aleph::less<Key>> struct Aleph::BinTree< Key, Compare >

Member Function Documentation

◆ get_compare()

◆ insert()

◆ insert_dup()

◆ join()

◆ join_dup()

◆ join_exclusive()

◆ remove()

◆ search()

◆ search_or_insert()

◆ split()

◆ split_dup()

◆ verifyBin()

template<typename Key, class Compare = Aleph::less<Key>>
struct Aleph::BinTree< Key, Compare >