Simple class that implements an AVL tree. More...

#include <avl.hpp>

Classes
struct	frequencies
	Frequency of a value in the tree v. More...

struct	tree_node
	Node of the tree. More...

Public Member Functions
	~AVL () noexcept
	Destructor.

void	clear () noexcept
	Empties the tree.

std::pair< const T &, frequencies >	get_largest_value () const noexcept
	Finds the largest value.

template<bool use_counter>
frequencies	remove_largest () noexcept
	Remove an element from the tree.

template<bool use_counter>
frequencies	remove_smallest () noexcept
	Remove an element from the tree.

std::pair< const T &, frequencies >	get_smallest_value () const noexcept
	Find the largest value.

frequencies	element_frequency (const T &v) const noexcept
	Number of occurrences associated to a given value.

template<typename U >
frequencies	insert (U &&v) noexcept
	Insert a new value v into the tree.

template<bool use_counter>
frequencies	remove (const T &v) noexcept
	Remove an element from the tree.

template<typename U >
void	join_sorted_all_greater (U &&v) noexcept
	Add to the tree the elements in the vector v.

std::size_t	num_nodes () const noexcept
	Size of the tree.

std::size_t	total_elements () const noexcept
	Total number of elements inserted.

Private Member Functions
void	free_node (tree_node *const n) const noexcept
	Deallocates the memory of node n.

tree_node *	right_rotation (tree_node *const n) const noexcept
	Performs a right-rotation at node n.

tree_node *	left_rotation (tree_node *const n) const noexcept
	Performs a left-rotation at node n.

tree_node *	left_left_case (tree_node *const n) const noexcept
	Left-left imbalance case.

tree_node *	left_right_case (tree_node *const n) const noexcept
	Left-right imbalance case.

tree_node *	right_right_case (tree_node *const n) const noexcept
	Right-right imbalance case.

tree_node *	right_left_case (tree_node *const n) const noexcept
	Right-left imbalance case.

tree_node *	balance (tree_node *const n) const noexcept
	Balance a node of the AVL tree.

template<typename U >
tree_node *	insert (tree_node p, tree_node n, U &&x, frequencies &freqs) const noexcept
	Insert element 'x' to the tree.

template<bool use_counter_to_remove, bool move_in_leftmost>
bool	delete_after_move (tree_node n, tree_node k, frequencies &freqs) const noexcept
	Moves the contents of n to k, when appropriate.

template<bool use_counter_to_remove>
tree_node *	remove_leftmost (tree_node n, tree_node k, frequencies &freqs) const noexcept
	Remove the leftmost node in tree rooted at n.

template<bool use_counter_to_remove>
tree_node *	remove_rightmost (tree_node n, tree_node k, frequencies &freqs) const noexcept
	Remove the rightmost node in tree rooted at n.

template<bool use_counter_to_remove>
tree_node *	remove (tree_node *n, const T &x, frequencies &freqs) const noexcept
	Remove an element from the tree.

tree_node *	join_taller (tree_node T1, tree_node T2) const noexcept
	Join two AVL trees.

tree_node *	join_shorter (tree_node T1, tree_node T2) const noexcept
	Join two AVL trees.

template<typename U >
tree_node *	_make_tree (U &&v, std::size_t l, std::size_t r, tree_node *p, char s) const noexcept
	Make an AVL tree from the elements in v.

Private Attributes
tree_node *	m_root = nullptr
	Root of this AVL tree.

Detailed Description

template<typename T>
class lal::detail::AVL< T >

Simple class that implements an AVL tree.

This class can store repeated elements. However, it will never contain two nodes with the same key. Every element is inserted with a total number of occurrences associated to it. So an element inserted three times (and never deleted) will be in the tree in a single node and its number of occurrences will be 3. Each time an element is removed, its number of occurrences decreases by 1.

Deletion of nodes depends on the template parameter of functions remove. Read their documentation for further details.

Member Function Documentation

◆ _make_tree()

template<typename T >

template<typename U >

tree_node * lal::detail::AVL< T >::_make_tree	(	U &&	v,
		std::size_t	l,
		std::size_t	r,
		tree_node *	p,
		char	s ) const

inlinenodiscardprivatenoexcept

Make an AVL tree from the elements in v.

This function performs a recursive binary search over v. The limits of this search are l and r. At each call, this function creates a tree_node with the value in the midpoint between l and r.

Parameters

v	Vector sorted non-decreasingly.
l	Left-limit of the binary search-
r	Right-limit of the binary search.
p	Parent of the new node to be created.
s	Side of the node to create with respect to the parent.

◆ balance()

template<typename T >

tree_node * lal::detail::AVL< T >::balance ( tree_node *const n ) const

inlinenodiscardprivatenoexcept

Balance a node of the AVL tree.

Uses the functions left_left_case, left_right_case, right_right_case, right_left_case.

Parameters

n	Node to balance

Returns: The root of the new balanced tree.

◆ clear()

template<typename T >

void lal::detail::AVL< T >::clear ( )

inlinenoexcept

Empties the tree.

Clears all the memory used by this tree. References to its elements are invalidated.

◆ delete_after_move()

template<typename T >

template<bool use_counter_to_remove, bool move_in_leftmost>

bool lal::detail::AVL< T >::delete_after_move	(	tree_node *	n,
		tree_node *	k,
		frequencies &	freqs ) const

inlinenodiscardprivatenoexcept

Moves the contents of n to k, when appropriate.

Template Parameters

use_counter_to_remove	If true then this node is to be removed only if the counter has reached 0. If false, the node will be removed regardless of the value.
move_in_leftmost	Was this function called from remove_leftmost?

Parameters

	n	Node of the tree.
[out]	k	Copy of the leftmost node.
[out]	freqs	The frequencies associated to the leftmost node.

Returns: True if the node is to be deleted; False if the node is not to be deleted.

◆ element_frequency()

template<typename T >

frequencies lal::detail::AVL< T >::element_frequency ( const T & v ) const

inlinenodiscardnoexcept

Number of occurrences associated to a given value.

Parameters

v	Value to find.

Returns: The element's frequency statistics.

◆ get_largest_value()

template<typename T >

std::pair< const T &, frequencies > lal::detail::AVL< T >::get_largest_value ( ) const

inlinenodiscardnoexcept

Finds the largest value.

Returns: A pair with a constant reference to the largest value and its frequency statistics.

◆ get_smallest_value()

template<typename T >

std::pair< const T &, frequencies > lal::detail::AVL< T >::get_smallest_value ( ) const

inlinenodiscardnoexcept

Find the largest value.

Returns: A pair with a constant reference to the largest value and its frequency statistics.

◆ insert() [1/2]

template<typename T >

template<typename U >

tree_node * lal::detail::AVL< T >::insert	(	tree_node *	p,
		tree_node *	n,
		U &&	x,
		frequencies &	freqs ) const

inlinenodiscardprivatenoexcept

Insert element 'x' to the tree.

Parameters

	p	Parent of node n
	n	Node to which the element 'x' is to be assigned.
	x	Element to be added.
[out]	freqs	Frequencies associated to the value x.

Returns: The tree node containing as key the value x.

◆ insert() [2/2]

template<typename T >

template<typename U >

frequencies lal::detail::AVL< T >::insert ( U && v )

inlinenodiscardnoexcept

Insert a new value v into the tree.

Parameters

v	New value.

Returns: The element's frequency statistics.

◆ join_shorter()

template<typename T >

tree_node * lal::detail::AVL< T >::join_shorter	(	tree_node *	T1,
		tree_node *	T2 ) const

inlinenodiscardprivatenoexcept

Join two AVL trees.

Parameters

T1	Shorter tree.
T2	Taller tree.

Returns: A tree node.

Precondition: The largest element in T1 is smaller than the smallest element in T2.

◆ join_sorted_all_greater()

template<typename T >

template<typename U >

void lal::detail::AVL< T >::join_sorted_all_greater ( U && v )

inlinenoexcept

Add to the tree the elements in the vector v.

The element passed as parameter must be a std::vector<T>.

Parameters

v	A sorted collection of unique elements.

Precondition: The vector v is sorted.; The elements in vector v are unique.; The first element of the vector is larger than the largest element of the tree.

◆ join_taller()

template<typename T >

tree_node * lal::detail::AVL< T >::join_taller	(	tree_node *	T1,
		tree_node *	T2 ) const

inlinenodiscardprivatenoexcept

Join two AVL trees.

Parameters

T1	Taller tree.
T2	Shorter tree.

Returns: A tree node.

Precondition: The largest element in T1 is smaller than the smallest element in T2.

◆ left_left_case()

template<typename T >

tree_node * lal::detail::AVL< T >::left_left_case ( tree_node *const n ) const

inlinenodiscardprivatenoexcept

Left-left imbalance case.

Parameters

n Node.

Returns: The root of the new balanced tree after a left-left rotation.

Precondition: Node n has a left subtree.

◆ left_right_case()

template<typename T >

tree_node * lal::detail::AVL< T >::left_right_case ( tree_node *const n ) const

inlinenodiscardprivatenoexcept

Left-right imbalance case.

Parameters

n Node.

Returns: The root of the new balanced tree after a left-right rotation.

Precondition: Node n has a left subtree.

◆ left_rotation()

template<typename T >

tree_node * lal::detail::AVL< T >::left_rotation ( tree_node *const n ) const

inlinenodiscardprivatenoexcept

Performs a left-rotation at node n.

Parameters

n Node.

Returns: The root of the new balanced tree after a left rotation.

Precondition: Node n has a right subtree.

◆ num_nodes()

template<typename T >

std::size_t lal::detail::AVL< T >::num_nodes ( ) const

inlinenodiscardnoexcept

Size of the tree.

Returns: The number of nodes in the tree.

◆ remove() [1/2]

template<typename T >

template<bool use_counter>

frequencies lal::detail::AVL< T >::remove ( const T & v )

inlinenodiscardnoexcept

Remove an element from the tree.

Template Parameters

use_counter If true then a node will be removed only if its counter has reached 0. If false then the node will be removed regardless of the value of the counter.

Parameters

v	The element to be removed.

Returns: The element's frequency statistics before removal.

◆ remove() [2/2]

template<typename T >

template<bool use_counter_to_remove>

tree_node * lal::detail::AVL< T >::remove	(	tree_node *	n,
		const T &	x,
		frequencies &	freqs ) const

inlinenodiscardprivatenoexcept

Remove an element from the tree.

Template Parameters

use_counter_to_remove If true, the node is deleted only when the node counter reaches 0. If false, the node is always deleted.

Parameters

	n	Root node.
	x	Element to be removed.
[out]	freqs	Frequencies associated to the value x.

Returns: A tree node.

◆ remove_largest()

template<typename T >

template<bool use_counter>

frequencies lal::detail::AVL< T >::remove_largest ( )

inlinenodiscardnoexcept

Remove an element from the tree.

Template Parameters

use_counter If true then a node will be removed only if its counter has reached 0. If false then the node will be removed regardless of the value of the counter.

Returns: The element's frequency statistics before removal. If the node is removed from the tree the references returned by get_largest_value are invalidated.

◆ remove_leftmost()

template<typename T >

template<bool use_counter_to_remove>

tree_node * lal::detail::AVL< T >::remove_leftmost	(	tree_node *	n,
		tree_node *	k,
		frequencies &	freqs ) const

inlinenodiscardprivatenoexcept

Remove the leftmost node in tree rooted at n.

Template Parameters

use_counter_to_remove If true then this node is to be removed only if the counter has reached 0. If false, the node will be removed regardless of the value.

Parameters

	n	Node of the tree.
[out]	k	Copy of the leftmost node.
[out]	freqs	The frequencies associated to the leftmost node.

Returns: The root of the tree resulting from the removal of the righmost node in tree n.

◆ remove_rightmost()

template<typename T >

template<bool use_counter_to_remove>

tree_node * lal::detail::AVL< T >::remove_rightmost	(	tree_node *	n,
		tree_node *	k,
		frequencies &	freqs ) const

inlinenodiscardprivatenoexcept

Remove the rightmost node in tree rooted at n.

Template Parameters

use_counter_to_remove If true then this node is to be removed only if the counter has reached 0. If false, the node will be removed regardless of the value.

Parameters

	n	Node of the tree.
[out]	k	Copy of the rightmost node.
[out]	freqs	The frequencies associated to the rightmost node.

Returns: The root of the tree resulting from the removal of the righmost node in tree n.

◆ remove_smallest()

template<typename T >

template<bool use_counter>

frequencies lal::detail::AVL< T >::remove_smallest ( )

inlinenodiscardnoexcept

Remove an element from the tree.

Template Parameters

use_counter If true then a node will be removed only if its counter has reached 0. If false then the node will be removed regardless of the value of the counter.

Returns: The element's frequency statistics before removal. If the node is removed from the tree the references returned by get_largest_value are invalidated.

◆ right_left_case()

template<typename T >

tree_node * lal::detail::AVL< T >::right_left_case ( tree_node *const n ) const

inlinenodiscardprivatenoexcept

Right-left imbalance case.

Parameters

n Node.

Returns: The root of the new balanced tree after a right-left rotation.

Precondition: Node n has a right subtree.

◆ right_right_case()

template<typename T >

tree_node * lal::detail::AVL< T >::right_right_case ( tree_node *const n ) const

inlinenodiscardprivatenoexcept

Right-right imbalance case.

Parameters

n Node.

Returns: The root of the new balanced tree after a right-right rotation.

Precondition: Node n has a right subtree.

◆ right_rotation()

template<typename T >

tree_node * lal::detail::AVL< T >::right_rotation ( tree_node *const n ) const

inlinenodiscardprivatenoexcept

Performs a right-rotation at node n.

Parameters

n Node.

Returns: The root of the new balanced tree after a right rotation.

Precondition: Node n has a left subtree.

◆ total_elements()

template<typename T >

std::size_t lal::detail::AVL< T >::total_elements ( ) const

inlinenodiscardnoexcept

Total number of elements inserted.

Returns: The total sum of occurrences of the elements in the tree.

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

lal/detail/avl.hpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

◆ _make_tree()

◆ balance()

◆ clear()

◆ delete_after_move()

◆ element_frequency()

◆ get_largest_value()

◆ get_smallest_value()

◆ insert() [1/2]

◆ insert() [2/2]

◆ join_shorter()

◆ join_sorted_all_greater()

◆ join_taller()

◆ left_left_case()

◆ left_right_case()

◆ left_rotation()

◆ num_nodes()

◆ remove() [1/2]

◆ remove() [2/2]

◆ remove_largest()

◆ remove_leftmost()

◆ remove_rightmost()

◆ remove_smallest()

◆ right_left_case()

◆ right_right_case()

◆ right_rotation()

◆ total_elements()