AVL tree implementation. More...

#include <_avl.hpp>

Inheritance diagram for datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >:

Collaboration diagram for datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >:

Public Types
using	node_ptr = typename base::node_ptr

using	key_type = typename base::key_type

Public Types inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, avl_node< TItem, TAlloc > >
using	key_type = TKey

using	item_type = TItem

using	comparator_type = TKeyComp

using	allocator_type = TAlloc

using	node_type = avl_node< TItem, TAlloc >

using	node_alloc_type = avl_node_allocator_type< node_type, allocator_type >
	The node allocator type.

using	node_ptr = avl_node_ptr< node_type, allocator_type >
	The node pointer type.

using	node_alloc_traits = std::allocator_traits< node_alloc_type >
	Node allocator traits.

using	size_type = typename node_alloc_traits::size_type
	The size type.

Public Member Functions
	avl_tree (const typename base::comparator_type &comparator, const typename base::allocator_type &allocator)
	Constructs new AVL tree.

	avl_tree (const avl_tree &other)
	Copies another tree.

avl_tree &	operator= (const avl_tree &other)
	Copies another tree.

	avl_tree (avl_tree &&other) noexcept
	Moves another tree into this one.

avl_tree &	operator= (avl_tree &&other) noexcept
	Moves another tree into this one.

	~avl_tree () noexcept
	Destroys the tree.

node_ptr	get_root () const noexcept
	Returns the trees root.

node_ptr	find (const key_type &key) const noexcept
	Finds a node with the given key, if there isn't any returns a `nullptr`.

node_ptr	successor (node_ptr node) const noexcept
	Returns the successor to the node.

node_ptr	predecessor (node_ptr node) const noexcept
	Returns the predecessor to the node.

template<bool lower>
node_ptr	bound (const key_type &key) const noexcept
	A 2-in-1 function for both lower and upper bounds accessing.

void	clear () noexcept
	Erases the whole tree.

template<class TInsertCallback , class TAssignCallback >
std::pair< node_ptr, bool >	insert (const key_type &key, TInsertCallback &&insert_callback, TAssignCallback &&assign_callback)
	Inserts an item to the tree.

template<class TInsertCallback >
std::pair< node_ptr, bool >	insert (const key_type &key, TInsertCallback &&insert_callback)
	Inserts an item to the tree.

void	erase (node_ptr node) noexcept
	Erases the node.

base::size_type	size () const noexcept
	Returns the current number of nodes.

int	get_height () const
	Returns the current height of the tree.

std::string	to_dot (bool print_invis) const
	Returns the dot representation of the tree.

template<class TInsertCallback , class TAssignCallback >
std::pair< typename avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr, bool >	insert (const key_type &key, TInsertCallback &&insert_callback, TAssignCallback &&assign_callback)

Public Member Functions inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, avl_node< TItem, TAlloc > >
	avl_tree_base (const comparator_type &comparator, const allocator_type &allocator)

	avl_tree_base (comparator_type &&comparator, allocator_type &&allocator) noexcept

virtual	~avl_tree_base ()=0

node_alloc_type	get_allocator () const noexcept
	Returns the associated allocator.

Additional Inherited Members
Static Public Member Functions inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, avl_node< TItem, TAlloc > >
static node_ptr	min_from (node_ptr node) noexcept
	Finds the minimum value starting at the given node.

static node_ptr	max_from (node_ptr node) noexcept
	Finds the maximum value starting at the given node.

Protected Types inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, avl_node< TItem, TAlloc > >
using	sign_type = avl_sign_type

Protected Member Functions inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, avl_node< TItem, TAlloc > >
node_ptr	create_node (T &&item)
	Constructs a new node with the given item.

node_ptr	create_node (TCallback &&callback)
	Constructs a new node with the item being the result of `callback()`.

void	destroy_node (node_ptr node) noexcept
	Destroys the node and frees the memory.

Protected Attributes inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, avl_node< TItem, TAlloc > >
comparator_type	comparator

node_alloc_type	allocator

Detailed Description

template<class TKey, class TItem, class TKeyComp, class TAlloc>
class datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >

AVL tree implementation.

It should keep a minimal interface, basically supports only insertion, deletion, basic access operations etc. And any more high-level shorcut functions should be implemented in the map or set wrappers.

Every function is implemented without recursion.

The pointers, references and iterators are invalidated only by a deletion of the associated node, other modifications like balancing and assigments, etc. does not invalidate them.

There are two types TKey and TItem, it is this way to make the class more general and so that it can represent both sets and maps. The key type is the raw type that is used to query and compare nodes, the item type is the internal type stored in nodes, and it can be indentical to the key type.

The node allocator is derived from the item allocator TAlloc.

Template Parameters

TKey	The key type.
TItem	The item type, usually same as the `TKey` or `std::pair<TKey, TValue>` for some `TValue`.
TKeyComp	`TKeyComp` must allow comparisons between all of: two keys; two items; one key and one item; one item and one key. The comparisons must be all `noexcept`.
TAlloc	The item allocator type.

Member Typedef Documentation

◆ key_type

template<class TKey , class TItem , class TKeyComp , class TAlloc >

using datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::key_type = typename base::key_type

◆ node_ptr

template<class TKey , class TItem , class TKeyComp , class TAlloc >

using datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr = typename base::node_ptr

Constructor & Destructor Documentation

◆ avl_tree() [1/3]

template<class TKey , class TItem , class TKeyComp , class TAlloc >

datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::avl_tree	(	const typename base::comparator_type &	comparator,
		const typename base::allocator_type &	allocator
	)

Constructs new AVL tree.

The tree needs to get the comparator and allocator instance from its wrapper, because they can store essential context. And to minimize the interface this is the only constructor except for the copy/move ones.

Parameters

comparator	The comparator instance passed from the wrapper.
allocator	The allocator instance passed from the wrapper.

◆ avl_tree() [2/3]

template<class TKey , class TItem , class TKeyComp , class TAlloc >

datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::avl_tree ( const avl_tree< TKey, TItem, TKeyComp, TAlloc > & other )

Copies another tree.

◆ avl_tree() [3/3]

template<class TKey , class TItem , class TKeyComp , class TAlloc >

datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::avl_tree ( avl_tree< TKey, TItem, TKeyComp, TAlloc > && other )

noexcept

Moves another tree into this one.

◆ ~avl_tree()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::~avl_tree ( )

noexcept

Destroys the tree.

Correctly deallocates all the nodes without allocating any new memory.

Note: Time Complexity: O(n)

Member Function Documentation

◆ bound()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

template<bool lower>

avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::bound ( const key_type & key ) const

noexcept

A 2-in-1 function for both lower and upper bounds accessing.

If the lower template argument is true finds the first node whose key is not less than the given key, otherwise finds the first node whose key is greater than the given key.

Returns: The requested node, when no such node exists returns a nullptr.

Note: Time Complexity: O(log n)

◆ clear()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

void datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::clear ( )

noexcept

Erases the whole tree.

Erases every node without allocating any more space and thus cannot throw an exception.

Note: Time Complexity: O(n).; Space Complexity: O(1) including the stack size.

◆ erase()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

void datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::erase ( node_ptr node )

noexcept

Erases the node.

Directly erases the given node. Does not invalidate any other pointers.

Calling this on a nullptr is an UB.

Note: Time Complexity: O(log n)

◆ find()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::find ( const key_type & key ) const

noexcept

Finds a node with the given key, if there isn't any returns a nullptr.

Parameters

key	The key to look for.

Returns: The requested node or nullptr if such node does not exist.

Note: Time Complexity: O(log n)

◆ get_height()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

int datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::get_height ( ) const

Returns the current height of the tree.

Note: Time Complexity: O(log n)

◆ get_root()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

node_ptr datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::get_root ( ) const

inlinenoexcept

Returns the trees root.

◆ insert() [1/3]

template<class TKey , class TItem , class TKeyComp , class TAlloc >

template<class TInsertCallback >

std::pair< node_ptr, bool > datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::insert	(	const key_type &	key,
		TInsertCallback &&	insert_callback
	)

inline

Inserts an item to the tree.

This function functions as an all-in-one solution to the standard emplace/insert/assign methods. It takes in a key and two callback functions. Then it tries to find the key, when it succeeds, it does nothing.

When the key is not present then the new item is directly constructed from the result of insert_callback, the result is forwarded into the nodes constructor.

Template Parameters

TInsertCallback The callback to call when constructing a new node. It should not have any parameters. It can return either an rvalue reference or lvalue reference.

Note: Time Complexity: O(log n);; Space Complexity: O(1); Strong exception guarantee.

◆ insert() [2/3]

template<class TKey , class TItem , class TKeyComp , class TAlloc >

template<class TInsertCallback , class TAssignCallback >

std::pair< node_ptr, bool > datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::insert	(	const key_type &	key,
		TInsertCallback &&	insert_callback,
		TAssignCallback &&	assign_callback
	)

Inserts an item to the tree.

This function functions as an all-in-one solution to the standard emplace/insert/assign methods. It takes in a key and two callback functions. Then it tries to find the key, when it succeeds, it calls the assign_callback on the found nodes item field, so it must take in an lvalue reference to the item type an inside it you can decide whether to change the value or keep the value.

When the key is not present then the new item is directly constructed from the result of insert_callback, the result is forwarded into the nodes constructor.

Template Parameters

TAssignCallback	The callback to call when assigning a new value to an existing item field, it shall be of this signature `void(item_type &)`.
TInsertCallback	The callback to call when constructing a new node. It should not have any parameters. It can return either an rvalue reference or lvalue reference.

Note: Time Complexity: O(log n);; Space Complexity: O(1); Strong exception guarantee.

◆ insert() [3/3]

template<class TKey , class TItem , class TKeyComp , class TAlloc >

template<class TInsertCallback , class TAssignCallback >

std::pair< typename avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr, bool > datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::insert	(	const key_type &	key,
		TInsertCallback &&	insert_callback,
		TAssignCallback &&	assign_callback
	)

◆ operator=() [1/2]

template<class TKey , class TItem , class TKeyComp , class TAlloc >

avl_tree< TKey, TItem, TKeyComp, TAlloc > & datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::operator= ( avl_tree< TKey, TItem, TKeyComp, TAlloc > && other )

noexcept

Moves another tree into this one.

◆ operator=() [2/2]

template<class TKey , class TItem , class TKeyComp , class TAlloc >

avl_tree< TKey, TItem, TKeyComp, TAlloc > & datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::operator= ( const avl_tree< TKey, TItem, TKeyComp, TAlloc > & other )

Copies another tree.

◆ predecessor()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::predecessor ( node_ptr node ) const

noexcept

Returns the predecessor to the node.

For a nullptr returns a nullptr

Note: Time Complexity: worst-case: O(log n), accessing all the items one by one: amortized O(1)

◆ size()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

base::size_type datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::size ( ) const

inlinenoexcept

Returns the current number of nodes.

Note: Time Complexity: O(1)

◆ successor()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::successor ( node_ptr node ) const

noexcept

Returns the successor to the node.

For a nullptr returns a nullptr

Note: Time Complexity: worst-case: O(log n), accessing all the items one by one: amortized O(1)

◆ to_dot()

template<class TKey , class TItem , class TKeyComp , class TAlloc >

std::string datastructures::detail::avl_tree< TKey, TItem, TKeyComp, TAlloc >::to_dot ( bool print_invis ) const

Returns the dot representation of the tree.

Safe to call for every key/item type, automatically tries to convert the nodes to their string representation in the most readable way. If it fails to convert the key to string it uses their unique pointers as labels, because this function is meant to be called during debugging from the debugger, it is sufficient to display the correct structure and map it to the debugging info.

If the print_invis flag is set to true even the nullptr children will be rendered although they will be set to be invisible. It is so that you can more easily tell whether the node is greater than its child or the other way in case it has just one in some types of renders.

Parameters

print_invis Toggles nulltpr rendering.

Returns: The dot language representation of the tree.

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

include/datastructures/_avl.hpp
include/datastructures/_avl.ipp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ key_type

◆ node_ptr

Constructor & Destructor Documentation

◆ avl_tree() [1/3]

◆ avl_tree() [2/3]

◆ avl_tree() [3/3]

◆ ~avl_tree()

Member Function Documentation

◆ bound()

◆ clear()

◆ erase()

◆ find()

◆ get_height()

◆ get_root()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ predecessor()

◆ size()

◆ successor()

◆ to_dot()