gum::BinSearchTree< Val, Cmp, Node > Class Template Reference

A generic binary search tree. More...

#include <agrum/base/core/binSearchTree.h>

Collaboration diagram for gum::BinSearchTree< Val, Cmp, Node >:

Public Types
using	iterator = BinSearchTreeIterator< Val, Cmp, Node >
	Alias for gum::BinSearchTree iterators.
using	const_iterator = BinSearchTreeIterator< Val, Cmp, Node >
	Alias for gum::BinSearchTree iterators.

Public Member Functions
Class constructors and destructors
	BinSearchTree (bool uniqueness_policy=false)
	Basic constructor: returns an empty binary search tree.
	BinSearchTree (const BinSearchTree< Val, Cmp, Node > &from)
	Copy constructor.
virtual	~BinSearchTree ()
	Class destructor.
Class operators
BinSearchTree< Val, Cmp, Node > &	operator= (const BinSearchTree< Val, Cmp, Node > &from)
	Copy operator.
Class iterators
iterator	begin ()
	Begin iterator.
const_iterator	begin () const
	Begin iterator.
iterator	rbegin ()
	Reverse iterator.
const_iterator	rbegin () const
	Reverse iterator.
const iterator &	end ()
	End iterator.
const const_iterator &	end () const
	End iterator.
const iterator &	rend ()
	Reverse end iterator.
const const_iterator &	rend () const
	Reverse end iterator.
iterator	root ()
	Returns an iterator at the root of the tree.
const_iterator	root () const
	Returns an iterator at the root of the tree.
Class Accessors and Modifiers
const Val &	rootValue () const
	Returns the value of the root of the tree.
const Val &	minValue () const
	Returns the value of the leftmost node with the minimal key in the tree.
const Val &	maxValue () const
	Returns the value of the rightmost node with the maximal key in the tree.
const Val &	insert (const Val &val)
	Creates a copy of the value, insert it in the tree and returns the copy value.
void	erase (const Val &val)
	Erase the leftmost node with the given (key,val) pair.
void	erase (const iterator &iter)
	Erase the node pointed to by the iterator.
bool	contains (const Val &val) const
	Returns true if the gum::BinSearchTree contains the value.
void	clear ()
	Removes all the elements from the gum::BinSearchTree.
Size	size () const
	Returns the number of elements in the binary search tree.
bool	empty () const
	Indicates whether the gum::BinSearchTree search tree is empty.
virtual std::string	toString () const
	Displays the content of the tree, in increasing order w.r.t.
Fine tuning
bool	uniquenessPolicy () const
	Returns the current uniqueness policy.
void	setUniquenessPolicy (const bool new_policy)
	Enables the user to change dynamically the policy for checking whether there can exist several identical elements in the binary tree.

Protected Member Functions
Node *	copy_ (Node *root_from, Node *parent=0, BinTreeDir dir=BinTreeDir::LEFT_CHILD)
	A method for recursively copying the contents of a BinSearchTree.
Node *	minNode_ (Node *node) const
	Returns the smallest node w.r.t.
Node *	maxNode_ (Node *node) const
	Returns the greatest node w.r.t.
Node *	succNode_ (Node *node) const
	Returns the next node according to the weak ordering Cmp.
Node *	prevNode_ (Node *node) const
	Returns the previous node according to weak ordering Cmp.
Node *	getNode_ (const Val &val) const
	Returns the node containing a given value.
void	deleteSubTree_ (Node *node)
	A method for recursively deleting a subtree of the gum::BinSearchTree.
virtual void	erase_ (Node *node)
	Erase the node passed in argument.
virtual Node *	insert_ (const Val &val)
	Creates a copy of the value, insert it in the gum::BinSearchTree and returns the copy value.

Protected Attributes
Node *	root_
	The root node of the tree.
Cmp	cmp_
	The comparison function.
iterator *	iterator_list_
	The list of iterators pointing to the binary search tree.
bool	uniqueness_policy_
	The uniqueness property: whether the same value can appear multiple times.
Size	nb_elements_
	The number of elements stored in the tree.
iterator	iter_end_
	Pseudo static iterator.

Private Member Functions
void	_eraseWithTwoChildren_ (Node *node)
	Erase a node with two children.
void	_updateEraseIterators_ (Node *node)
	Update all iterators when a given node is deleted.

Friends
class	BinSearchTreeIterator< Val, Cmp, Node >
	To speed-up accesses.

Detailed Description

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
class gum::BinSearchTree< Val, Cmp, Node >

A generic binary search tree.

Template Parameters

Val	The values type to store in the binary search tree.
Cmp	The comparator for sorting the binary search tree.
Node	The nodes type used to store values in the binary search tree.

Definition at line 84 of file binSearchTree.h.

Member Typedef Documentation

const_iterator

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

using gum::BinSearchTree< Val, Cmp, Node >::const_iterator = BinSearchTreeIterator< Val, Cmp, Node >

Alias for gum::BinSearchTree iterators.

Definition at line 89 of file binSearchTree.h.

iterator

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

using gum::BinSearchTree< Val, Cmp, Node >::iterator = BinSearchTreeIterator< Val, Cmp, Node >

Alias for gum::BinSearchTree iterators.

Definition at line 88 of file binSearchTree.h.

Constructor & Destructor Documentation

BinSearchTree() [1/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

gum::BinSearchTree< Val, Cmp, Node >::BinSearchTree ( bool uniqueness_policy = false )

explicit

Basic constructor: returns an empty binary search tree.

Parameters

uniqueness_policy

Allows (false) or disables (true) the binary tree uniqueness.

It is possible for the binary tree to have multiple instances of the same value within the tree.

BinSearchTree() [2/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

gum::BinSearchTree< Val, Cmp, Node >::BinSearchTree

(

const BinSearchTree< Val, Cmp, Node > &

from

)

Copy constructor.

Parameters

from	The gum::BinSearchTree to copy.

~BinSearchTree()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

virtual gum::BinSearchTree< Val, Cmp, Node >::~BinSearchTree ( )

virtual

Class destructor.

Member Function Documentation

_eraseWithTwoChildren_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

void gum::BinSearchTree< Val, Cmp, Node >::_eraseWithTwoChildren_ ( Node * node )

private

Erase a node with two children.

This is used by gum::BinSearchTree::erase_(Node*).

Parameters

node	The node to erase.

_updateEraseIterators_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

void gum::BinSearchTree< Val, Cmp, Node >::_updateEraseIterators_ ( Node * node )

private

Update all iterators when a given node is deleted.

Parameters

node	The node that is erased.

begin() [1/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

iterator gum::BinSearchTree< Val, Cmp, Node >::begin

(

)

Begin iterator.

Returns

Returns an iterator at the beginning of the gum::BinSearchTree.

begin() [2/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const_iterator gum::BinSearchTree< Val, Cmp, Node >::begin

(

)

const

Begin iterator.

Returns

Returns an iterator at the beginning of the gum::BinSearchTree.

clear()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

void gum::BinSearchTree< Val, Cmp, Node >::clear

(

)

Removes all the elements from the gum::BinSearchTree.

contains()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

bool gum::BinSearchTree< Val, Cmp, Node >::contains

(

const Val &

val

)

const

Returns true if the gum::BinSearchTree contains the value.

Parameters

val	The value tested for existence.

Returns

Returns true if the gum::BinSearchTree contains the value.

copy_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

Node * gum::BinSearchTree< Val, Cmp, Node >::copy_ ( Node * root_from, Node * parent = 0, BinTreeDir dir = BinTreeDir::LEFT_CHILD )

protected

A method for recursively copying the contents of a BinSearchTree.

Warning

This function produces a tree with precisely the same structure as that passed in argument (node). Hence, this should be used only when copying binary search trees storing data w.r.t. the same weak order Cmp.

Parameters

root_from	The root of the tree to be copied.
parent	The node that should be the parent of the copy.
dir	The direction of the edge parent->copy.

References gum::LEFT_CHILD.

deleteSubTree_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

void gum::BinSearchTree< Val, Cmp, Node >::deleteSubTree_ ( Node * node )

protected

A method for recursively deleting a subtree of the gum::BinSearchTree.

Note that this method does not update the iterators pointing to nodes of the subtree. These should be cleared before deleteSubTree_ is called.

Parameters

node	The root of the subtree to delete.

empty()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

bool gum::BinSearchTree< Val, Cmp, Node >::empty

(

)

const

Indicates whether the gum::BinSearchTree search tree is empty.

Returns

Returns true if the gum::BinSearchTree is empty.

end() [1/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const iterator & gum::BinSearchTree< Val, Cmp, Node >::end

(

)

End iterator.

Returns

Returns an iterator at the end of the gum::BinSearchTree.

end() [2/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const const_iterator & gum::BinSearchTree< Val, Cmp, Node >::end

(

)

const

End iterator.

Returns

Returns an iterator at the end of the gum::BinSearchTree.

erase() [1/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

void gum::BinSearchTree< Val, Cmp, Node >::erase

(

const iterator &

iter

)

Erase the node pointed to by the iterator.

If we could not find the node, then nothing happens. In particular, no exception is raised.

Parameters

iter	The iterator pointing toward the value to remove.

erase() [2/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

void gum::BinSearchTree< Val, Cmp, Node >::erase

(

const Val &

val

)

Erase the leftmost node with the given (key,val) pair.

Parameters

val	The value to remove.

Exceptions

NotFound

Raised if we could not find the node.

erase_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

virtual void gum::BinSearchTree< Val, Cmp, Node >::erase_ ( Node * node )

protectedvirtual

Erase the node passed in argument.

Parameters

node	The Node to erase.

getNode_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

Node * gum::BinSearchTree< Val, Cmp, Node >::getNode_ ( const Val & val ) const

protected

Returns the node containing a given value.

Parameters

val	The value of the node to return.

Returns

Returns the node containing a given value (0 if the value cannot be found).

insert()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const Val & gum::BinSearchTree< Val, Cmp, Node >::insert

(

const Val &

val

)

Creates a copy of the value, insert it in the tree and returns the copy value.

When elements are inserted into binary search trees, this is actually copies that are inserted. Thus, the method returns the newly created copy, so that the user may reference it.

Parameters

val	The value added by copy.

Returns

Returns a reference over copy added in the gum::BinSearchTree.

Exceptions

DuplicateElement

Raised if the binary tree already contains the value and the uniqueness property is set to true.

insert_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

virtual Node * gum::BinSearchTree< Val, Cmp, Node >::insert_ ( const Val & val )

protectedvirtual

Creates a copy of the value, insert it in the gum::BinSearchTree and returns the copy value.

When elements are inserted into gum::BinSearchTree, this is actually copies that are inserted. Thus, the method returns the node containing the newly created copy, so that the user may reference the new copy.

Warning

this method is actually the implementation of method insert. It is used to speed-up insertions in terminal classes such as AVL trees.

Exceptions

DuplicateElement

exception is raised if the binary tree already contains the value and the uniqueness property is set to true.

Parameters

val	The value added by copy.

Returns

Returns the node containing the newly created copy.

maxNode_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

Node * gum::BinSearchTree< Val, Cmp, Node >::maxNode_ ( Node * node ) const

protected

Returns the greatest node w.r.t.

order Cmp in the subtree rooted at node.

Parameters

node	The root for looking for the the greatest node.

Returns

Returns the greatest node.

maxValue()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const Val & gum::BinSearchTree< Val, Cmp, Node >::maxValue

(

)

const

Returns the value of the rightmost node with the maximal key in the tree.

Returns

Returns the value of the rightmost node with the maximal key in the tree.

Exceptions

NotFound

Raised if the tree is empty/

minNode_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

Node * gum::BinSearchTree< Val, Cmp, Node >::minNode_ ( Node * node ) const

protected

Returns the smallest node w.r.t.

order Cmp in the subtree rooted at node.

Parameters

node	The root for looking for the the smallest node.

Returns

Returns the smallest node.

minValue()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const Val & gum::BinSearchTree< Val, Cmp, Node >::minValue

(

)

const

Returns the value of the leftmost node with the minimal key in the tree.

Returns

Returns the value of the leftmost node with the minimal key in the tree.

Exceptions

NotFound

Raised if the tree is empty.

operator=()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

BinSearchTree< Val, Cmp, Node > & gum::BinSearchTree< Val, Cmp, Node >::operator=

(

const BinSearchTree< Val, Cmp, Node > &

from

)

Copy operator.

Parameters

from	The gum::BinSearchTree to copy.

Returns

Returns this gum::BinSearchTree.

prevNode_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

Node * gum::BinSearchTree< Val, Cmp, Node >::prevNode_ ( Node * node ) const

protected

Returns the previous node according to weak ordering Cmp.

Parameters

node	The node for which the previous node is returned.

Returns

Returns the previous node according to the weak ordering Cmp.

rbegin() [1/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

iterator gum::BinSearchTree< Val, Cmp, Node >::rbegin

(

)

Reverse iterator.

Returns

Returns an iterator at the beginning of the gum::BinSearchTree for reverse iteration.

rbegin() [2/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const_iterator gum::BinSearchTree< Val, Cmp, Node >::rbegin

(

)

const

Reverse iterator.

Returns

Returns an iterator at the beginning of the gum::BinSearchTree for reverse iteration.

rend() [1/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const iterator & gum::BinSearchTree< Val, Cmp, Node >::rend

(

)

Reverse end iterator.

Returns

Returns an iterator at the end of the gum::BinSearchTree for reverse iteration.

rend() [2/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const const_iterator & gum::BinSearchTree< Val, Cmp, Node >::rend

(

)

const

Reverse end iterator.

Returns

Returns an iterator at the end of the gum::BinSearchTree for reverse iteration.

root() [1/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

iterator gum::BinSearchTree< Val, Cmp, Node >::root

(

)

Returns an iterator at the root of the tree.

Returns

Returns an iterator at the root of the tree.

root() [2/2]

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const_iterator gum::BinSearchTree< Val, Cmp, Node >::root

(

)

const

Returns an iterator at the root of the tree.

Returns

Returns an iterator at the root of the tree.

rootValue()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

const Val & gum::BinSearchTree< Val, Cmp, Node >::rootValue

(

)

const

Returns the value of the root of the tree.

Returns

Returns the value of the root of the tree.

Exceptions

NotFound

Raised if the tree is empty.

setUniquenessPolicy()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

void gum::BinSearchTree< Val, Cmp, Node >::setUniquenessPolicy

(

const bool

new_policy

)

Enables the user to change dynamically the policy for checking whether there can exist several identical elements in the binary tree.

By default, trees can store several times the same element. However, for some applications, we should ensure that all elements in the binary search tree are distinct.

Warning

When setting the policy to "uniqueness", the function does not check whether the tree already contains identical elements. It thus only ensures that elements inserted from now on do not already belong to the tree.

Parameters

new_policy

Set the uniqueness policy on or off.

size()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

Size gum::BinSearchTree< Val, Cmp, Node >::size

(

)

const

Returns the number of elements in the binary search tree.

Returns

Returns the number of elements in the binary search tree.

succNode_()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

Node * gum::BinSearchTree< Val, Cmp, Node >::succNode_ ( Node * node ) const

protected

Returns the next node according to the weak ordering Cmp.

Parameters

node	The node for which the sucessor is returned.

Returns

Returns the next node according to the weak ordering Cmp.

toString()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

virtual std::string gum::BinSearchTree< Val, Cmp, Node >::toString ( ) const

virtual

Displays the content of the tree, in increasing order w.r.t.

Cmp.

Returns

Returns the content of the tree in a string.

uniquenessPolicy()

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

bool gum::BinSearchTree< Val, Cmp, Node >::uniquenessPolicy

(

)

const

Returns the current uniqueness policy.

Returns

Returns the current uniqueness policy.

Friends And Related Symbol Documentation

BinSearchTreeIterator< Val, Cmp, Node >

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

friend class BinSearchTreeIterator< Val, Cmp, Node >

friend

To speed-up accesses.

Definition at line 334 of file binSearchTree.h.

References iter_end_.

Member Data Documentation

cmp_

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

Cmp gum::BinSearchTree< Val, Cmp, Node >::cmp_

protected

The comparison function.

Definition at line 314 of file binSearchTree.h.

iter_end_

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

iterator gum::BinSearchTree< Val, Cmp, Node >::iter_end_

protected

Pseudo static iterator.

The end and rend iterators are constructed only once per binary search tree so as to optimize for(iter = begin();iter != end(); iter++) loops: this will avoid creating objects end and rend each time we pass in the loop.

Definition at line 334 of file binSearchTree.h.

Referenced by BinSearchTreeIterator< Val, Cmp, Node >.

iterator_list_

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

iterator* gum::BinSearchTree< Val, Cmp, Node >::iterator_list_

mutableprotected

The list of iterators pointing to the binary search tree.

Definition at line 317 of file binSearchTree.h.

nb_elements_

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

Size gum::BinSearchTree< Val, Cmp, Node >::nb_elements_

protected

The number of elements stored in the tree.

Definition at line 324 of file binSearchTree.h.

root_

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

Node* gum::BinSearchTree< Val, Cmp, Node >::root_

protected

The root node of the tree.

Definition at line 311 of file binSearchTree.h.

uniqueness_policy_

template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>

bool gum::BinSearchTree< Val, Cmp, Node >::uniqueness_policy_

mutableprotected

The uniqueness property: whether the same value can appear multiple times.

Definition at line 321 of file binSearchTree.h.

---

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

• agrum/base/core/binSearchTree.h