AVL binary search tree. More...

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

Collaboration diagram for gum::AVLTree< Val, Cmp >:

Public Types

using	value_type = Val
	Types for STL compliance.
using	reference = Val&
	Types for STL compliance.
using	const_reference = const Val&
	Types for STL compliance.
using	pointer = Val*
	Types for STL compliance.
using	const_pointer = const Val*
	Types for STL compliance.
using	iterator = AVLTreeIterator< Val, Cmp >
	Types for STL compliance.
using	iterator_safe = AVLTreeIteratorSafe< Val, Cmp >
	Types for STL compliance.
using	reverse_iterator = AVLTreeReverseIterator< Val, Cmp >
	Types for STL compliance.
using	reverse_iterator_safe = AVLTreeReverseIteratorSafe< Val, Cmp >
	Types for STL compliance.
using	AVLNode = AVLTreeNode< Val >
	Types for STL compliance.

Public Member Functions
Constructors / Destructors
	AVLTree (const Cmp &compare=Cmp())
	Basic constructor.
	AVLTree (std::initializer_list< Val > list)
	Initializer list constructor.
	AVLTree (const AVLTree< Val, Cmp > &from)
	Copy constructor.
	AVLTree (AVLTree< Val, Cmp > &&from) noexcept
	Move constructor.
	~AVLTree ()
	Class destructor.
Operators
AVLTree< Val, Cmp > &	operator= (const AVLTree< Val, Cmp > &from)
	Copy operator.
AVLTree< Val, Cmp > &	operator= (AVLTree< Val, Cmp > &&from) noexcept
	Move operator.
Accessors / Modifiers
Size	size () const noexcept
	Returns the number of elements in the tree.
bool	empty () const noexcept
	Indicates whether the tree is empty.
bool	contains (const value_type &val) const
	Indicates whether the tree contains a given value.
bool	exists (const value_type &val) const
	Alias of contains: indicates whether the tree contains a given value.
const value_type &	highestValue () const
	returns the max element (w.r.t. Cmp) in the tree
const value_type &	lowestValue () const
	returns the min element (w.r.t. Cmp) in the tree
const value_type &	insert (const value_type &val)
	adds (by copy) a new element into the tree
const value_type &	insert (value_type &&val)
	adds (by move) a new element into the tree
template<typename... Args>
const value_type &	emplace (Args &&... args)
	emplace a new element into the tree
void	erase (const value_type &val)
	remove an element from the tree
void	erase (iterator_safe &iter)
	remove the element pointed to by an iterator
void	erase (reverse_iterator_safe &iter)
	remove the element pointed to by an iterator
void	clear ()
	remove all the elements in the tree
std::string	toString () const
	returns a string with the content of the tree, order from the lowest to the highest element
Iterators
iterator	begin () const
	returns a new iterator pointing to the minimal element of the tree
constexpr const iterator &	end () const
	returns an iterator pointing just after the maximal element
reverse_iterator	rbegin () const
	returns a new iterator pointing to the maximal element of the tree
constexpr const reverse_iterator &	rend () const
	returns an iterator pointing just before the minimal element
iterator_safe	beginSafe ()
	returns a new safe iterator pointing to the minimal element of the tree
constexpr const iterator_safe &	endSafe () const
	returns a safe iterator pointing just after the maximal element
reverse_iterator_safe	rbeginSafe ()
	returns a safe iterator pointing to the maximal element of the tree
constexpr const reverse_iterator_safe &	rendSafe () const
	returns a safe iterator pointing just before the minimal element

Protected Member Functions
AVLNode *	lowestNode_ () const noexcept
	returns the node containing the lowest element of the tree
AVLNode *	highestNode_ () const noexcept
	returns the node containing the highest element of the tree
AVLNode *	rightRotation_ (AVLNode *node_q)
	rotate the subtree rooted at q to the right
AVLNode *	leftRotation_ (AVLNode *node_p)
	rotate the subtree rooted at p to the left
void	rebalanceTree_ (AVLNode *node)
	rebalance the tree moving up recursively from a given node
AVLNode *	removeNodeFromTree_ (AVLNode *node)
	remove a node from the tree and returns the node that was actually removed
void	erase_ (AVLNode *node)
	remove a node from the tree and free memory
const value_type &	insert_ (AVLNode *node)
	insert a node into the tree
void	insertIntoSafeList_ (iterator_safe *iter)
	register a new safe iterator
void	removeFromSafeList_ (iterator_safe *iter)
	unregister a safe iterator

Static Protected Member Functions
static AVLNode *	copySubtree_ (const AVLNode from_node, AVLNode new_parent)
	copies recursively a subtree of the AVL tree
static void	deleteSubtree_ (AVLNode *subtree_root_node)
	deletes recursively a subtree of the AVL tree

Protected Attributes
AVLNode *	root_node_ {nullptr}
	the root of the AVL tree
AVLNode *	lowest_node_ {nullptr}
	the node containing the lowest element
AVLNode *	highest_node_ {nullptr}
	the node containing the highest element
Size	nb_elements_ {Size(0)}
	the number of elements in the tree
bool	owns_nodes_ {true}
	indicates whether the tree owns its nodes. If not, it won't delete them
Cmp	cmp_
	the comparison function
std::vector< iterator_safe * >	safe_iterators_
	The list of safe iterators and reverse iterators used by the AVL tree.
friend	iterator
	make the iterators access to the AVLNodes
friend	reverse_iterator
friend	iterator_safe
friend	reverse_iterator_safe

Detailed Description

template<typename Val, typename Cmp = std::less< Val >>
class gum::AVLTree< Val, Cmp >

AVL binary search tree.

Template Parameters

Val	The type of the elements stored into the tree.
Cmp	The function used for sorting the elements. queues.

Definition at line 168 of file AVLTree.h.

Member Typedef Documentation

◆ AVLNode

template<typename Val, typename Cmp = std::less< Val >>

using gum::AVLTree< Val, Cmp >::AVLNode = AVLTreeNode< Val >

Types for STL compliance.

Definition at line 181 of file AVLTree.h.

◆ const_pointer

template<typename Val, typename Cmp = std::less< Val >>

using gum::AVLTree< Val, Cmp >::const_pointer = const Val*

Types for STL compliance.

Definition at line 176 of file AVLTree.h.

◆ const_reference

template<typename Val, typename Cmp = std::less< Val >>

using gum::AVLTree< Val, Cmp >::const_reference = const Val&

Types for STL compliance.

Definition at line 174 of file AVLTree.h.

◆ iterator

template<typename Val, typename Cmp = std::less< Val >>

using gum::AVLTree< Val, Cmp >::iterator = AVLTreeIterator< Val, Cmp >

Types for STL compliance.

Definition at line 177 of file AVLTree.h.

◆ iterator_safe

template<typename Val, typename Cmp = std::less< Val >>

using gum::AVLTree< Val, Cmp >::iterator_safe = AVLTreeIteratorSafe< Val, Cmp >

Types for STL compliance.

Definition at line 178 of file AVLTree.h.

◆ pointer

template<typename Val, typename Cmp = std::less< Val >>

using gum::AVLTree< Val, Cmp >::pointer = Val*

Types for STL compliance.

Definition at line 175 of file AVLTree.h.

◆ reference

template<typename Val, typename Cmp = std::less< Val >>

using gum::AVLTree< Val, Cmp >::reference = Val&

Types for STL compliance.

Definition at line 173 of file AVLTree.h.

◆ reverse_iterator

template<typename Val, typename Cmp = std::less< Val >>

using gum::AVLTree< Val, Cmp >::reverse_iterator = AVLTreeReverseIterator< Val, Cmp >

Types for STL compliance.

Definition at line 179 of file AVLTree.h.

◆ reverse_iterator_safe

template<typename Val, typename Cmp = std::less< Val >>

using gum::AVLTree< Val, Cmp >::reverse_iterator_safe = AVLTreeReverseIteratorSafe< Val, Cmp >

Types for STL compliance.

Definition at line 180 of file AVLTree.h.

◆ value_type

template<typename Val, typename Cmp = std::less< Val >>

using gum::AVLTree< Val, Cmp >::value_type = Val

Types for STL compliance.

Definition at line 172 of file AVLTree.h.

Constructor & Destructor Documentation

◆ AVLTree() [1/4]

template<typename Val, typename Cmp = std::less< Val >>

gum::AVLTree< Val, Cmp >::AVLTree ( const Cmp & compare = Cmp() )

explicit

Basic constructor.

Creates an empty tree.

Parameters

compare A function taking two elements in argument, say e1 and e2, and returning a Boolean indicating whether e1 < e2, i.e., whether e1 should be "on the left of" e2.

Referenced by AVLTree(), AVLTree(), operator=(), and operator=().

Here is the caller graph for this function:

◆ AVLTree() [2/4]

template<typename Val, typename Cmp = std::less< Val >>

gum::AVLTree< Val, Cmp >::AVLTree ( std::initializer_list< Val > list )

explicit

Initializer list constructor.

A default comparison function is provided.

Parameters

list	The initializer list.

◆ AVLTree() [3/4]

template<typename Val, typename Cmp = std::less< Val >>

gum::AVLTree< Val, Cmp >::AVLTree ( const AVLTree< Val, Cmp > & from )

Copy constructor.

Parameters

from	The gum::AVLTree to copy.

References AVLTree().

Here is the call graph for this function:

◆ AVLTree() [4/4]

template<typename Val, typename Cmp = std::less< Val >>

gum::AVLTree< Val, Cmp >::AVLTree ( AVLTree< Val, Cmp > && from )

noexcept

Move constructor.

Parameters

from	The gum::AVLTree to move.

References AVLTree().

Here is the call graph for this function:

◆ ~AVLTree()

template<typename Val, typename Cmp = std::less< Val >>

gum::AVLTree< Val, Cmp >::~AVLTree ( )

Class destructor.

Member Function Documentation

◆ begin()

template<typename Val, typename Cmp = std::less< Val >>

iterator gum::AVLTree< Val, Cmp >::begin ( ) const

returns a new iterator pointing to the minimal element of the tree

References begin().

Referenced by begin().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ beginSafe()

template<typename Val, typename Cmp = std::less< Val >>

iterator_safe gum::AVLTree< Val, Cmp >::beginSafe ( )

returns a new safe iterator pointing to the minimal element of the tree

References beginSafe().

Referenced by beginSafe().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clear()

template<typename Val, typename Cmp = std::less< Val >>

void gum::AVLTree< Val, Cmp >::clear ( )

remove all the elements in the tree

References clear().

Referenced by clear().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ contains()

template<typename Val, typename Cmp = std::less< Val >>

bool gum::AVLTree< Val, Cmp >::contains ( const value_type & val ) const

Indicates whether the tree contains a given value.

Parameters

val	The value to look for.

Returns: Returns true if val is in the tree.

References contains().

Referenced by contains().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ copySubtree_()

template<typename Val, typename Cmp = std::less< Val >>

AVLNode * gum::AVLTree< Val, Cmp >::copySubtree_	(	const AVLNode *	from_node,
		AVLNode *	new_parent )

staticprotected

copies recursively a subtree of the AVL tree

Parameters

from_node	the root node of the subtree that we copy recursively
new_parent	the parent of the root node of the copied subtree

Returns: the root node of the copied subtree

References copySubtree_().

Referenced by copySubtree_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ deleteSubtree_()

template<typename Val, typename Cmp = std::less< Val >>

void gum::AVLTree< Val, Cmp >::deleteSubtree_ ( AVLNode * subtree_root_node )

staticprotected

deletes recursively a subtree of the AVL tree

References deleteSubtree_().

Referenced by deleteSubtree_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ emplace()

template<typename Val, typename Cmp = std::less< Val >>

template<typename... Args>

const value_type & gum::AVLTree< Val, Cmp >::emplace ( Args &&... args )

emplace a new element into the tree

References emplace().

Referenced by emplace().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ empty()

template<typename Val, typename Cmp = std::less< Val >>

bool gum::AVLTree< Val, Cmp >::empty ( ) const

noexcept

Indicates whether the tree is empty.

Returns: Returns true if the tree is empty.

References empty().

Referenced by empty().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ end()

template<typename Val, typename Cmp = std::less< Val >>

const iterator & gum::AVLTree< Val, Cmp >::end ( ) const

constexpr

returns an iterator pointing just after the maximal element

References end().

Referenced by end().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ endSafe()

template<typename Val, typename Cmp = std::less< Val >>

const iterator_safe & gum::AVLTree< Val, Cmp >::endSafe ( ) const

constexpr

returns a safe iterator pointing just after the maximal element

References endSafe().

Referenced by endSafe().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ erase() [1/3]

template<typename Val, typename Cmp = std::less< Val >>

void gum::AVLTree< Val, Cmp >::erase ( const value_type & val )

remove an element from the tree

If the element does not exist, the function does nothing. In particular, it does not raise any exception.

For speed reasons, if you already have an iterator pointing to val, prefer using erase(iterator) rather than erase(val).

References erase().

Referenced by erase(), erase(), and erase().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ erase() [2/3]

template<typename Val, typename Cmp = std::less< Val >>

void gum::AVLTree< Val, Cmp >::erase ( iterator_safe & iter )

remove the element pointed to by an iterator

Warning: after removing the element, you can still use safely the ++operator (resp. –operator) to move to the next (resp. preceding) elements. This results from the fact that the iterators compute their next and preceding nodes as soon as they move to a new noed. As a result, do not use a ++ followed by a – operator, or a – followed by a ++ operator, just after removing the element because it will create a segfault.

References erase().

Here is the call graph for this function:

◆ erase() [3/3]

template<typename Val, typename Cmp = std::less< Val >>

void gum::AVLTree< Val, Cmp >::erase ( reverse_iterator_safe & iter )

remove the element pointed to by an iterator

Warning: after removing the element, you can still use safely the ++operator (resp. –operator) to move to the next (resp. preceding) elements. This results from the fact that the iterators compute their next and preceding nodes as soon as they move to a new noed. As a result, do not use a ++ followed by a – operator, or a – followed by a ++ operator, just after removing the element because it will create a segfault.

References erase().

Here is the call graph for this function:

◆ erase_()

template<typename Val, typename Cmp = std::less< Val >>

void gum::AVLTree< Val, Cmp >::erase_ ( AVLNode * node )

protected

remove a node from the tree and free memory

References erase_().

Referenced by erase_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ exists()

template<typename Val, typename Cmp = std::less< Val >>

bool gum::AVLTree< Val, Cmp >::exists ( const value_type & val ) const

Alias of contains: indicates whether the tree contains a given value.

Parameters

val	The value to look for.

Returns: Returns true if val is in the tree.

References exists().

Referenced by exists().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ highestNode_()

template<typename Val, typename Cmp = std::less< Val >>

AVLNode * gum::AVLTree< Val, Cmp >::highestNode_ ( ) const

protectednoexcept

returns the node containing the highest element of the tree

References highestNode_().

Referenced by highestNode_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ highestValue()

template<typename Val, typename Cmp = std::less< Val >>

const value_type & gum::AVLTree< Val, Cmp >::highestValue ( ) const

returns the max element (w.r.t. Cmp) in the tree

Exceptions

NotFound Raised if the tree is empty

References highestValue().

Referenced by highestValue().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert() [1/2]

template<typename Val, typename Cmp = std::less< Val >>

const value_type & gum::AVLTree< Val, Cmp >::insert ( const value_type & val )

adds (by copy) a new element into the tree

References insert().

Referenced by insert(), and insert().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert() [2/2]

template<typename Val, typename Cmp = std::less< Val >>

const value_type & gum::AVLTree< Val, Cmp >::insert ( value_type && val )

adds (by move) a new element into the tree

References insert().

Here is the call graph for this function:

◆ insert_()

template<typename Val, typename Cmp = std::less< Val >>

const value_type & gum::AVLTree< Val, Cmp >::insert_ ( AVLNode * node )

protected

insert a node into the tree

References insert_().

Referenced by insert_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insertIntoSafeList_()

template<typename Val, typename Cmp = std::less< Val >>

void gum::AVLTree< Val, Cmp >::insertIntoSafeList_ ( iterator_safe * iter )

protected

register a new safe iterator

References insertIntoSafeList_().

Referenced by insertIntoSafeList_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ leftRotation_()

template<typename Val, typename Cmp = std::less< Val >>

AVLNode * gum::AVLTree< Val, Cmp >::leftRotation_ ( AVLNode * node_p )

protected

rotate the subtree rooted at p to the left

References leftRotation_().

Referenced by leftRotation_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ lowestNode_()

template<typename Val, typename Cmp = std::less< Val >>

AVLNode * gum::AVLTree< Val, Cmp >::lowestNode_ ( ) const

protectednoexcept

returns the node containing the lowest element of the tree

◆ lowestValue()

template<typename Val, typename Cmp = std::less< Val >>

const value_type & gum::AVLTree< Val, Cmp >::lowestValue ( ) const

returns the min element (w.r.t. Cmp) in the tree

Exceptions

NotFound Raised if the tree is empty

References lowestValue().

Referenced by lowestValue().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator=() [1/2]

template<typename Val, typename Cmp = std::less< Val >>

AVLTree< Val, Cmp > & gum::AVLTree< Val, Cmp >::operator= ( AVLTree< Val, Cmp > && from )

noexcept

Move operator.

Parameters

from	The gum::AVLTree to move.

Returns: Returns this gum::AVLTree.

References AVLTree().

Here is the call graph for this function:

◆ operator=() [2/2]

template<typename Val, typename Cmp = std::less< Val >>

AVLTree< Val, Cmp > & gum::AVLTree< Val, Cmp >::operator= ( const AVLTree< Val, Cmp > & from )

Copy operator.

Parameters

from	The gum::AVLTree to copy.

Returns: Returns this gum::AVLTree.

References AVLTree().

Here is the call graph for this function:

◆ rbegin()

template<typename Val, typename Cmp = std::less< Val >>

reverse_iterator gum::AVLTree< Val, Cmp >::rbegin ( ) const

returns a new iterator pointing to the maximal element of the tree

References rbegin().

Referenced by rbegin().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rbeginSafe()

template<typename Val, typename Cmp = std::less< Val >>

reverse_iterator_safe gum::AVLTree< Val, Cmp >::rbeginSafe ( )

returns a safe iterator pointing to the maximal element of the tree

References rbeginSafe().

Referenced by rbeginSafe().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rebalanceTree_()

template<typename Val, typename Cmp = std::less< Val >>

void gum::AVLTree< Val, Cmp >::rebalanceTree_ ( AVLNode * node )

protected

rebalance the tree moving up recursively from a given node

References rebalanceTree_().

Referenced by rebalanceTree_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ removeFromSafeList_()

template<typename Val, typename Cmp = std::less< Val >>

void gum::AVLTree< Val, Cmp >::removeFromSafeList_ ( iterator_safe * iter )

protected

unregister a safe iterator

References removeFromSafeList_().

Referenced by removeFromSafeList_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ removeNodeFromTree_()

template<typename Val, typename Cmp = std::less< Val >>

AVLNode * gum::AVLTree< Val, Cmp >::removeNodeFromTree_ ( AVLNode * node )

protected

remove a node from the tree and returns the node that was actually removed

Warning: the function does not free the memory, it just remove the node from the tree. If you wish to also free memory, use methode erase_ instead.

Returns: a pointer to the node that should be deleted after the removal. Actually, a tree that owns its nodes can swap the content of the node to remove with that of another node if this can speed-up the removal process. In such a case, the node that should be deleted after this removal is not necessarily "node". Hence the method returns a pointer to the very node that should be deleted.

References removeNodeFromTree_().

Referenced by removeNodeFromTree_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rend()

template<typename Val, typename Cmp = std::less< Val >>

const reverse_iterator & gum::AVLTree< Val, Cmp >::rend ( ) const

constexpr

returns an iterator pointing just before the minimal element

References rend().

Referenced by rend().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rendSafe()

template<typename Val, typename Cmp = std::less< Val >>

const reverse_iterator_safe & gum::AVLTree< Val, Cmp >::rendSafe ( ) const

constexpr

returns a safe iterator pointing just before the minimal element

References rendSafe().

Referenced by rendSafe().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rightRotation_()

template<typename Val, typename Cmp = std::less< Val >>

AVLNode * gum::AVLTree< Val, Cmp >::rightRotation_ ( AVLNode * node_q )

protected

rotate the subtree rooted at q to the right

References rightRotation_().

Referenced by rightRotation_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ size()

template<typename Val, typename Cmp = std::less< Val >>

Size gum::AVLTree< Val, Cmp >::size ( ) const

noexcept

Returns the number of elements in the tree.

Returns: Returns the number of elements in the tree.

◆ toString()

template<typename Val, typename Cmp = std::less< Val >>

std::string gum::AVLTree< Val, Cmp >::toString ( ) const

returns a string with the content of the tree, order from the lowest to the highest element

References toString().

Referenced by toString().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ cmp_

template<typename Val, typename Cmp = std::less< Val >>

Cmp gum::AVLTree< Val, Cmp >::cmp_

protected

the comparison function

Definition at line 384 of file AVLTree.h.

◆ highest_node_

template<typename Val, typename Cmp = std::less< Val >>

AVLNode* gum::AVLTree< Val, Cmp >::highest_node_ {nullptr}

protected

the node containing the highest element

Definition at line 375 of file AVLTree.h.

375{nullptr};

◆ iterator

template<typename Val, typename Cmp = std::less< Val >>

friend gum::AVLTree< Val, Cmp >::iterator

protected

make the iterators access to the AVLNodes

Definition at line 440 of file AVLTree.h.

◆ iterator_safe

template<typename Val, typename Cmp = std::less< Val >>

friend gum::AVLTree< Val, Cmp >::iterator_safe

protected

Definition at line 442 of file AVLTree.h.

◆ lowest_node_

template<typename Val, typename Cmp = std::less< Val >>

AVLNode* gum::AVLTree< Val, Cmp >::lowest_node_ {nullptr}

protected

the node containing the lowest element

Definition at line 372 of file AVLTree.h.

372{nullptr};

◆ nb_elements_

template<typename Val, typename Cmp = std::less< Val >>

Size gum::AVLTree< Val, Cmp >::nb_elements_ {Size(0)}

protected

the number of elements in the tree

Definition at line 378 of file AVLTree.h.

378{Size(0)};

gum::AVLTree

AVL binary search tree.

Definition AVLTree.h:168

◆ owns_nodes_

template<typename Val, typename Cmp = std::less< Val >>

bool gum::AVLTree< Val, Cmp >::owns_nodes_ {true}

protected

indicates whether the tree owns its nodes. If not, it won't delete them

Definition at line 381 of file AVLTree.h.

381{true};

◆ reverse_iterator

template<typename Val, typename Cmp = std::less< Val >>

friend gum::AVLTree< Val, Cmp >::reverse_iterator

protected

Definition at line 441 of file AVLTree.h.

◆ reverse_iterator_safe

template<typename Val, typename Cmp = std::less< Val >>

friend gum::AVLTree< Val, Cmp >::reverse_iterator_safe

protected

Definition at line 443 of file AVLTree.h.

◆ root_node_

template<typename Val, typename Cmp = std::less< Val >>

AVLNode* gum::AVLTree< Val, Cmp >::root_node_ {nullptr}

protected

the root of the AVL tree

Definition at line 369 of file AVLTree.h.

369{nullptr};

◆ safe_iterators_

template<typename Val, typename Cmp = std::less< Val >>

std::vector< iterator_safe* > gum::AVLTree< Val, Cmp >::safe_iterators_

protected

The list of safe iterators and reverse iterators used by the AVL tree.

Definition at line 387 of file AVLTree.h.

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

agrum/base/core/AVLTree.h

Public Types

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ AVLNode

◆ const_pointer

◆ const_reference

◆ iterator

◆ iterator_safe

◆ pointer

◆ reference

◆ reverse_iterator

◆ reverse_iterator_safe

◆ value_type

Constructor & Destructor Documentation

◆ AVLTree() [1/4]

◆ AVLTree() [2/4]

◆ AVLTree() [3/4]

◆ AVLTree() [4/4]

◆ ~AVLTree()

Member Function Documentation

◆ begin()

◆ beginSafe()

◆ clear()

◆ contains()

◆ copySubtree_()

◆ deleteSubtree_()

◆ emplace()

◆ empty()

◆ end()

◆ endSafe()

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ erase_()

◆ exists()

◆ highestNode_()

◆ highestValue()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_()

◆ insertIntoSafeList_()

◆ leftRotation_()

◆ lowestNode_()

◆ lowestValue()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ rbegin()

◆ rbeginSafe()

◆ rebalanceTree_()

◆ removeFromSafeList_()

◆ removeNodeFromTree_()

◆ rend()

◆ rendSafe()

◆ rightRotation_()

◆ size()

◆ toString()

Member Data Documentation

◆ cmp_

◆ highest_node_

◆ iterator

◆ iterator_safe

◆ lowest_node_

◆ nb_elements_

◆ owns_nodes_

◆ reverse_iterator

◆ reverse_iterator_safe

◆ root_node_

◆ safe_iterators_