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

A generic binary search tree. More...

#include <agrum/core/binSearchTree.h>

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

Public Member Functions

Class constructors and destructors
 BinSearchTree (bool uniqueness_policy=false)
 Basic constructor: returns an empty binary search tree. More...
 
 BinSearchTree (const BinSearchTree< Val, Cmp, Node > &from)
 Copy constructor. More...
 
virtual ~BinSearchTree ()
 Class destructor. More...
 
Class operators
BinSearchTree< Val, Cmp, Node > & operator= (const BinSearchTree< Val, Cmp, Node > &from)
 Copy operator. More...
 
Class iterators
iterator begin ()
 Begin iterator. More...
 
const_iterator begin () const
 Begin iterator. More...
 
iterator rbegin ()
 Reverse iterator. More...
 
const_iterator rbegin () const
 Reverse iterator. More...
 
const iteratorend ()
 End iterator. More...
 
const const_iteratorend () const
 End iterator. More...
 
const iteratorrend ()
 Reverse end iterator. More...
 
const const_iteratorrend () const
 Reverse end iterator. More...
 
iterator root ()
 Returns an iterator at the root of the tree. More...
 
const_iterator root () const
 Returns an iterator at the root of the tree. More...
 
Class Accessors and Modifiers
const Val & rootValue () const
 Returns the value of the root of the tree. More...
 
const Val & minValue () const
 Returns the value of the leftmost node with the minimal key in the tree. More...
 
const Val & maxValue () const
 Returns the value of the rightmost node with the maximal key in the tree. More...
 
const Val & insert (const Val &val)
 Creates a copy of the value, insert it in the tree and returns the copy value. More...
 
void erase (const Val &val)
 Erase the leftmost node with the given (key,val) pair. More...
 
void erase (const iterator &iter)
 Erase the node pointed to by the iterator. More...
 
bool contains (const Val &val) const
 Returns true if the gum::BinSearchTree contains the value. More...
 
void clear ()
 Removes all the elements from the gum::BinSearchTree. More...
 
Size size () const
 Returns the number of elements in the binary search tree. More...
 
bool empty () const
 Indicates whether the gum::BinSearchTree search tree is empty. More...
 
virtual const std::string toString () const
 Displays the content of the tree, in increasing order w.r.t. More...
 
Fine tuning
bool uniquenessPolicy () const
 Returns the current uniqueness policy. More...
 
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. More...
 

Public Types

typedef BinSearchTreeIterator< Val, Cmp, Node > iterator
 Alias for gum::BinSearchTree iterators. More...
 
typedef BinSearchTreeIterator< Val, Cmp, Node > const_iterator
 Alias for gum::BinSearchTree iterators. More...
 

Protected Attributes

Node * _root
 The root node of the tree. More...
 
Cmp _cmp
 The comparison function. More...
 
iterator_iterator_list
 The list of iterators pointing to the binary search tree. More...
 
bool _uniqueness_policy
 The uniqueness property: whether the same value can appear multiple times. More...
 
Size _nb_elements
 The number of elements stored in the tree. More...
 
iterator _iter_end
 Pseudo static iterator. More...
 

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. More...
 
Node * _minNode (Node *node) const
 Returns the smallest node w.r.t. More...
 
Node * _maxNode (Node *node) const
 Returns the greatest node w.r.t. More...
 
Node * _succNode (Node *node) const
 Returns the next node according to the weak ordering Cmp. More...
 
Node * _prevNode (Node *node) const
 Returns the previous node according to weak ordering Cmp. More...
 
Node * _getNode (const Val &val) const
 Returns the node containing a given value. More...
 
void _deleteSubTree (Node *node)
 A method for recursively deleting a subtree of the gum::BinSearchTree. More...
 
virtual void _erase (Node *node)
 Erase the node passed in argument. More...
 
virtual Node * _insert (const Val &val)
 Creates a copy of the value, insert it in the gum::BinSearchTree and returns the copy value. More...
 

Friends

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

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
ValThe values type to store in the binary search tree.
CmpThe compatator for sorting the binary search tree.
NodeThe nodes type used to store values in the binary search tree.

Definition at line 65 of file binSearchTree.h.

Member Typedef Documentation

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

Alias for gum::BinSearchTree iterators.

Definition at line 70 of file binSearchTree.h.

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

Alias for gum::BinSearchTree iterators.

Definition at line 69 of file binSearchTree.h.

Constructor & Destructor Documentation

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_policyAllows (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.

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
fromThe gum::BinSearchTree to copy.
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

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
nodeThe node to erase.
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
nodeThe node that is erased.
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_fromThe root of the tree to be copied.
parentThe node that should be the parent of the copy.
dirThe direction of the edge parent->copy.
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
nodeThe root of the subtree to delete.
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
nodeThe Node to erase.
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
valThe value of the node to return.
Returns
Returns the node containing a given value (0 if the value cannot be found).
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
DuplicateElementexception is raised if the binary tree already contains the value and the uniqueness property is set to true.
Parameters
valThe value added by copy.
Returns
Returns the node containing the newly created copy.
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
nodeThe root for looking for the the greatest node.
Returns
Returns the greatest node.
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
nodeThe root for looking for the the smallest node.
Returns
Returns the smallest node.
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
nodeThe node for which the previous node is returned.
Returns
Returns the previous node according to the weak ordering Cmp.
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
nodeThe node for which the sucessor is returned.
Returns
Returns the next node according to the weak ordering Cmp.
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 begining of the gum::BinSearchTree.
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 begining of the gum::BinSearchTree.
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.

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
valThe value tested for existence.
Returns
Returns true if the gum::BinSearchTree contains the value.
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.
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.
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.
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
valThe value to remove.
Exceptions
NotFoundRaised if we could not find the node.
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
iterThe iterator pointing toward the valeu to remove.
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
valThe value added by copy.
Returns
Returns a reference over copy added in the gum::BinSearchTree.
Exceptions
DuplicateElementRaised if the binary tree already contains the value and the uniqueness property is set to true.
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
NotFoundRaised if the tree is empty/
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
NotFoundRaised if the tree is empty.
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
fromThe gum::BinSearchTree to copy.
Returns
Returns this gum::BinSearchTree.
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 begining of the gum::BinSearchTree for reverse iteration.
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 begining of the gum::BinSearchTree for reverse iteration.
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.
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.
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.
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.
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
NotFoundRaised if the tree is empty.
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_policySet the uniqueness policy on or off.
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.
template<typename Val, class Cmp = std::less< Val >, class Node = BinTreeNode< Val >>
virtual const 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.
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 Function Documentation

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 320 of file binSearchTree.h.

Member Data Documentation

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 296 of file binSearchTree.h.

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 316 of file binSearchTree.h.

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 299 of file binSearchTree.h.

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 306 of file binSearchTree.h.

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 293 of file binSearchTree.h.

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 303 of file binSearchTree.h.


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