Intrusive balanced AVL binary tree container. More...

#include <bintree_avl.h>

Classes
struct	Node
	AVL binary tree node. More...

Public Types
typedef T	value_type

typedef TCompare	value_compare

typedef value_type &	reference

typedef const value_type &	const_reference

typedef value_type *	pointer

typedef const value_type *	const_pointer

typedef ptrdiff_t	difference_type

typedef size_t	size_type

typedef BinTreeIterator< BinTreeAVL< T, TCompare >, T >	iterator

typedef BinTreeConstIterator< BinTreeAVL< T, TCompare >, T >	const_iterator

typedef BinTreeReverseIterator< BinTreeAVL< T, TCompare >, T >	reverse_iterator

typedef BinTreeConstReverseIterator< BinTreeAVL< T, TCompare >, T >	const_reverse_iterator

Public Member Functions
	BinTreeAVL (const TCompare &compare=TCompare()) noexcept

template<class InputIterator >
	BinTreeAVL (InputIterator first, InputIterator last, const TCompare &compare=TCompare()) noexcept

	BinTreeAVL (const BinTreeAVL &) noexcept=default

	BinTreeAVL (BinTreeAVL &&) noexcept=default

	~BinTreeAVL () noexcept=default

BinTreeAVL &	operator= (const BinTreeAVL &) noexcept=default

BinTreeAVL &	operator= (BinTreeAVL &&) noexcept=default

	operator bool () const noexcept
	Check if the binary tree is not empty. More...

bool	empty () const noexcept
	Is the binary tree empty? More...

size_t	size () const noexcept
	Get the binary tree size. More...

T *	root () noexcept
	Get the root binary tree item. More...

const T *	root () const noexcept

T *	lowest () noexcept
	Get the lowest binary tree item. More...

const T *	lowest () const noexcept

T *	highest () noexcept
	Get the highest binary tree item. More...

const T *	highest () const noexcept

bool	compare (const T &item1, const T &item2) const noexcept
	Compare two items: if the first item is less than the second one? More...

iterator	begin () noexcept
	Get the begin binary tree iterator. More...

const_iterator	begin () const noexcept

const_iterator	cbegin () const noexcept

iterator	end () noexcept
	Get the end binary tree iterator. More...

const_iterator	end () const noexcept

const_iterator	cend () const noexcept

reverse_iterator	rbegin () noexcept
	Get the reverse begin binary tree iterator. More...

const_reverse_iterator	rbegin () const noexcept

const_reverse_iterator	crbegin () const noexcept

reverse_iterator	rend () noexcept
	Get the reverse end binary tree iterator. More...

const_reverse_iterator	rend () const noexcept

const_reverse_iterator	crend () const noexcept

iterator	find (const T &item) noexcept
	Find the iterator which points to the first equal item in the binary tree or return end iterator. More...

const_iterator	find (const T &item) const noexcept

iterator	lower_bound (const T &item) noexcept
	Find the iterator which points to the first item that not less than the given item in the binary tree or return end iterator. More...

const_iterator	lower_bound (const T &item) const noexcept

iterator	upper_bound (const T &item) noexcept
	Find the iterator which points to the first item that greater than the given item in the binary tree or return end iterator. More...

const_iterator	upper_bound (const T &item) const noexcept

std::pair< iterator, bool >	insert (T &item) noexcept
	Insert a new item into the binary tree. More...

std::pair< iterator, bool >	insert (const const_iterator &position, T &item) noexcept
	Insert a new item into the binary tree with a position hint. More...

T *	erase (const T &item) noexcept
	Erase the given item from the binary tree. More...

iterator	erase (const iterator &it) noexcept
	Erase the given item from the binary tree. More...

void	clear () noexcept
	Clear the binary tree. More...

void	swap (BinTreeAVL &bintree) noexcept
	Swap two instances. More...

Friends
template<typename U , typename UCompare >
void	swap (BinTreeAVL< U, UCompare > &bintree1, BinTreeAVL< U, UCompare > &bintree2) noexcept

Detailed Description

template<typename T, typename TCompare = std::less<T>>
class CppCommon::BinTreeAVL< T, TCompare >

Intrusive balanced AVL binary tree container.

Not thread-safe.

Overview
In computer science, an AVL tree is a self-balancing binary search tree, and the first such data structure to be invented. In an AVL tree the heights of the two child subtrees of any node differ by at most one, therefore it is also called height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more tree rotations.

The AVL tree is named after its two inventors, G.M. Adelson-Velsky and E.M. Landis, who published it in their 1962 paper "An algorithm for the organization of information."

The balance factor of a node is the height of its right subtree minus the height of its left subtree. A node with balance factor 1, 0, or -1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.

While AVL trees are theoretically quite sound, they are not commonly implemented due to their high implementation complexity to keep it balanced, making development less effective when compared to self- correcting tree structures, such as splay trees or heaps. They do, however, perform better than e.g. red-black trees. They are widely used in academic settings as an instructional data structure.

Operations
The basic operations of an AVL tree generally involve carrying out the same algorithms as would be carried out on an unbalanced binary search tree, but preceded or followed by one or more of the so-called "AVL rotations."

Insertion
Insertion into an AVL tree may be carried out by inserting the given value into the tree as if it were an unbalanced binary search tree, and then retracing one's steps toward the root, rotating about any nodes which have become unbalanced during the insertion (see tree rotation). Since at most 1.5 times lg n nodes are retraced on the journey back to the root, and each AVL rotation takes constant time, the insertion process in total takes O(log n) time.

Deletion
Deletion from an AVL tree may be carried out by rotating the node to be deleted down into a leaf node, and then pruning off that leaf node directly. Since at most log n nodes are rotated during the rotation into the leaf, and each AVL rotation takes constant time, the deletion process in total takes O(log n) time.

Practically, this is a large overhead and complex to program. Therefore, it's more common to implement a lazy deletion – leave the deletion target in place, flag it as "deleted", and replace it with an inserted node if they would occupy the same spot.

Lookup
Lookup in an AVL tree is performed exactly as in an unbalanced binary search tree, and thus takes O(log n) time, since an AVL tree is always kept balanced. No special provisions need to be taken, and the tree's structure is not modified by lookups. (This is in contrast to splay tree lookups, which do modify their tree's structure.)

Usage
AVL trees are faster than Red-Black trees when lookups are more frequent than inserts/deletes and comparisons are expensive.

References

G. Adelson-Velskii and E.M. Landis, "An algorithm for the organization of information." Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian). English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259-1263, 1962.
Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 458-475 of section 6.2.3: Balanced Trees. Note that Knuth calls AVL trees simply "balanced trees".

Taken from:
AVL tree from Wikipedia, the free encyclopedia http://en.wikipedia.org/wiki/AVL_tree

Definition at line 99 of file bintree_avl.h.

Member Typedef Documentation

◆ const_iterator

template<typename T , typename TCompare = std::less<T>>

typedef BinTreeConstIterator<BinTreeAVL<T, TCompare>, T> CppCommon::BinTreeAVL< T, TCompare >::const_iterator

Definition at line 112 of file bintree_avl.h.

◆ const_pointer

template<typename T , typename TCompare = std::less<T>>

typedef const value_type* CppCommon::BinTreeAVL< T, TCompare >::const_pointer

Definition at line 108 of file bintree_avl.h.

◆ const_reference

template<typename T , typename TCompare = std::less<T>>

typedef const value_type& CppCommon::BinTreeAVL< T, TCompare >::const_reference

Definition at line 106 of file bintree_avl.h.

◆ const_reverse_iterator

template<typename T , typename TCompare = std::less<T>>

typedef BinTreeConstReverseIterator<BinTreeAVL<T, TCompare>, T> CppCommon::BinTreeAVL< T, TCompare >::const_reverse_iterator

Definition at line 114 of file bintree_avl.h.

◆ difference_type

template<typename T , typename TCompare = std::less<T>>

typedef ptrdiff_t CppCommon::BinTreeAVL< T, TCompare >::difference_type

Definition at line 109 of file bintree_avl.h.

◆ iterator

template<typename T , typename TCompare = std::less<T>>

typedef BinTreeIterator<BinTreeAVL<T, TCompare>, T> CppCommon::BinTreeAVL< T, TCompare >::iterator

Definition at line 111 of file bintree_avl.h.

◆ pointer

template<typename T , typename TCompare = std::less<T>>

typedef value_type* CppCommon::BinTreeAVL< T, TCompare >::pointer

Definition at line 107 of file bintree_avl.h.

◆ reference

template<typename T , typename TCompare = std::less<T>>

typedef value_type& CppCommon::BinTreeAVL< T, TCompare >::reference

Definition at line 105 of file bintree_avl.h.

◆ reverse_iterator

template<typename T , typename TCompare = std::less<T>>

typedef BinTreeReverseIterator<BinTreeAVL<T, TCompare>, T> CppCommon::BinTreeAVL< T, TCompare >::reverse_iterator

Definition at line 113 of file bintree_avl.h.

◆ size_type

template<typename T , typename TCompare = std::less<T>>

typedef size_t CppCommon::BinTreeAVL< T, TCompare >::size_type

Definition at line 110 of file bintree_avl.h.

◆ value_compare

template<typename T , typename TCompare = std::less<T>>

typedef TCompare CppCommon::BinTreeAVL< T, TCompare >::value_compare

Definition at line 104 of file bintree_avl.h.

◆ value_type

template<typename T , typename TCompare = std::less<T>>

typedef T CppCommon::BinTreeAVL< T, TCompare >::value_type

Definition at line 103 of file bintree_avl.h.

Constructor & Destructor Documentation

◆ BinTreeAVL() [1/4]

template<typename T , typename TCompare = std::less<T>>

CppCommon::BinTreeAVL< T, TCompare >::BinTreeAVL ( const TCompare & compare = TCompare() )

inlineexplicitnoexcept

Definition at line 127 of file bintree_avl.h.

◆ BinTreeAVL() [2/4]

template<typename T , typename TCompare >

template<class InputIterator >

CppCommon::BinTreeAVL< T, TCompare >::BinTreeAVL	(	InputIterator	first,
		InputIterator	last,
		const TCompare &	compare = `TCompare()`
	)

inlinenoexcept

Definition at line 13 of file bintree_avl.inl.

◆ BinTreeAVL() [3/4]

template<typename T , typename TCompare = std::less<T>>

CppCommon::BinTreeAVL< T, TCompare >::BinTreeAVL ( const BinTreeAVL< T, TCompare > & )

defaultnoexcept

◆ BinTreeAVL() [4/4]

template<typename T , typename TCompare = std::less<T>>

CppCommon::BinTreeAVL< T, TCompare >::BinTreeAVL ( BinTreeAVL< T, TCompare > && )

defaultnoexcept

◆ ~BinTreeAVL()

template<typename T , typename TCompare = std::less<T>>

CppCommon::BinTreeAVL< T, TCompare >::~BinTreeAVL ( )

defaultnoexcept

Member Function Documentation

◆ begin() [1/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_iterator CppCommon::BinTreeAVL< T, TCompare >::begin

inlinenoexcept

Definition at line 71 of file bintree_avl.inl.

◆ begin() [2/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::iterator CppCommon::BinTreeAVL< T, TCompare >::begin

inlinenoexcept

Get the begin binary tree iterator.

Definition at line 65 of file bintree_avl.inl.

◆ cbegin()

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_iterator CppCommon::BinTreeAVL< T, TCompare >::cbegin

inlinenoexcept

Definition at line 77 of file bintree_avl.inl.

◆ cend()

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_iterator CppCommon::BinTreeAVL< T, TCompare >::cend

inlinenoexcept

Definition at line 95 of file bintree_avl.inl.

◆ clear()

template<typename T , typename TCompare >

void CppCommon::BinTreeAVL< T, TCompare >::clear

inlinenoexcept

Clear the binary tree.

Definition at line 794 of file bintree_avl.inl.

◆ compare()

template<typename T , typename TCompare = std::less<T>>

bool CppCommon::BinTreeAVL< T, TCompare >::compare	(	const T &	item1,
		const T &	item2
	)		const

inlinenoexcept

Compare two items: if the first item is less than the second one?

Definition at line 161 of file bintree_avl.h.

◆ crbegin()

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_reverse_iterator CppCommon::BinTreeAVL< T, TCompare >::crbegin

inlinenoexcept

Definition at line 113 of file bintree_avl.inl.

◆ crend()

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_reverse_iterator CppCommon::BinTreeAVL< T, TCompare >::crend

inlinenoexcept

Definition at line 131 of file bintree_avl.inl.

◆ empty()

template<typename T , typename TCompare = std::less<T>>

bool CppCommon::BinTreeAVL< T, TCompare >::empty ( ) const

inlinenoexcept

Is the binary tree empty?

Definition at line 145 of file bintree_avl.h.

◆ end() [1/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_iterator CppCommon::BinTreeAVL< T, TCompare >::end

inlinenoexcept

Definition at line 89 of file bintree_avl.inl.

◆ end() [2/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::iterator CppCommon::BinTreeAVL< T, TCompare >::end

inlinenoexcept

Get the end binary tree iterator.

Definition at line 83 of file bintree_avl.inl.

◆ erase() [1/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::iterator CppCommon::BinTreeAVL< T, TCompare >::erase ( const iterator & it )

inlinenoexcept

Erase the given item from the binary tree.

Parameters

it	- Iterator to the erased item

Returns: Erased item iterator

Definition at line 380 of file bintree_avl.inl.

◆ erase() [2/2]

template<typename T , typename TCompare >

T * CppCommon::BinTreeAVL< T, TCompare >::erase ( const T & item )

inlinenoexcept

Erase the given item from the binary tree.

Parameters

item	- Item to erase

Returns: Erased item

Definition at line 374 of file bintree_avl.inl.

◆ find() [1/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_iterator CppCommon::BinTreeAVL< T, TCompare >::find ( const T & item ) const

inlinenoexcept

Definition at line 143 of file bintree_avl.inl.

◆ find() [2/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::iterator CppCommon::BinTreeAVL< T, TCompare >::find ( const T & item )

inlinenoexcept

Find the iterator which points to the first equal item in the binary tree or return end iterator.

Definition at line 137 of file bintree_avl.inl.

◆ highest() [1/2]

template<typename T , typename TCompare >

const T * CppCommon::BinTreeAVL< T, TCompare >::highest

inlinenoexcept

Definition at line 49 of file bintree_avl.inl.

◆ highest() [2/2]

template<typename T , typename TCompare >

T * CppCommon::BinTreeAVL< T, TCompare >::highest

inlinenoexcept

Get the highest binary tree item.

Definition at line 43 of file bintree_avl.inl.

◆ insert() [1/2]

template<typename T , typename TCompare >

std::pair< typename BinTreeAVL< T, TCompare >::iterator, bool > CppCommon::BinTreeAVL< T, TCompare >::insert	(	const const_iterator &	position,
		T &	item
	)

inlinenoexcept

Insert a new item into the binary tree with a position hint.

Parameters

position	- Iterator position to the inserted item
item	- Item to insert

Returns: Pair with the iterator to the inserted item and success flag

Definition at line 266 of file bintree_avl.inl.

◆ insert() [2/2]

template<typename T , typename TCompare >

std::pair< typename BinTreeAVL< T, TCompare >::iterator, bool > CppCommon::BinTreeAVL< T, TCompare >::insert ( T & item )

inlinenoexcept

Insert a new item into the binary tree.

Parameters

item	- Item to insert

Returns: Pair with the iterator to the inserted item and success flag

Definition at line 260 of file bintree_avl.inl.

◆ lower_bound() [1/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_iterator CppCommon::BinTreeAVL< T, TCompare >::lower_bound ( const T & item ) const

inlinenoexcept

Definition at line 185 of file bintree_avl.inl.

◆ lower_bound() [2/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::iterator CppCommon::BinTreeAVL< T, TCompare >::lower_bound ( const T & item )

inlinenoexcept

Find the iterator which points to the first item that not less than the given item in the binary tree or return end iterator.

Definition at line 179 of file bintree_avl.inl.

◆ lowest() [1/2]

template<typename T , typename TCompare >

const T * CppCommon::BinTreeAVL< T, TCompare >::lowest

inlinenoexcept

Definition at line 27 of file bintree_avl.inl.

◆ lowest() [2/2]

template<typename T , typename TCompare >

T * CppCommon::BinTreeAVL< T, TCompare >::lowest

inlinenoexcept

Get the lowest binary tree item.

Definition at line 21 of file bintree_avl.inl.

◆ operator bool()

template<typename T , typename TCompare = std::less<T>>

CppCommon::BinTreeAVL< T, TCompare >::operator bool ( ) const

inlineexplicitnoexcept

Check if the binary tree is not empty.

Definition at line 142 of file bintree_avl.h.

◆ operator=() [1/2]

template<typename T , typename TCompare = std::less<T>>

BinTreeAVL& CppCommon::BinTreeAVL< T, TCompare >::operator= ( BinTreeAVL< T, TCompare > && )

defaultnoexcept

◆ operator=() [2/2]

template<typename T , typename TCompare = std::less<T>>

BinTreeAVL& CppCommon::BinTreeAVL< T, TCompare >::operator= ( const BinTreeAVL< T, TCompare > & )

defaultnoexcept

◆ rbegin() [1/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_reverse_iterator CppCommon::BinTreeAVL< T, TCompare >::rbegin

inlinenoexcept

Definition at line 107 of file bintree_avl.inl.

◆ rbegin() [2/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::reverse_iterator CppCommon::BinTreeAVL< T, TCompare >::rbegin

inlinenoexcept

Get the reverse begin binary tree iterator.

Definition at line 101 of file bintree_avl.inl.

◆ rend() [1/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_reverse_iterator CppCommon::BinTreeAVL< T, TCompare >::rend

inlinenoexcept

Definition at line 125 of file bintree_avl.inl.

◆ rend() [2/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::reverse_iterator CppCommon::BinTreeAVL< T, TCompare >::rend

inlinenoexcept

Get the reverse end binary tree iterator.

Definition at line 119 of file bintree_avl.inl.

◆ root() [1/2]

template<typename T , typename TCompare = std::less<T>>

const T* CppCommon::BinTreeAVL< T, TCompare >::root ( ) const

inlinenoexcept

Definition at line 152 of file bintree_avl.h.

◆ root() [2/2]

template<typename T , typename TCompare = std::less<T>>

T* CppCommon::BinTreeAVL< T, TCompare >::root ( )

inlinenoexcept

Get the root binary tree item.

Definition at line 151 of file bintree_avl.h.

◆ size()

template<typename T , typename TCompare = std::less<T>>

size_t CppCommon::BinTreeAVL< T, TCompare >::size ( ) const

inlinenoexcept

Get the binary tree size.

Definition at line 148 of file bintree_avl.h.

◆ swap()

template<typename T , typename TCompare >

void CppCommon::BinTreeAVL< T, TCompare >::swap ( BinTreeAVL< T, TCompare > & bintree )

inlinenoexcept

Swap two instances.

Definition at line 801 of file bintree_avl.inl.

◆ upper_bound() [1/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::const_iterator CppCommon::BinTreeAVL< T, TCompare >::upper_bound ( const T & item ) const

inlinenoexcept

Definition at line 229 of file bintree_avl.inl.

◆ upper_bound() [2/2]

template<typename T , typename TCompare >

BinTreeAVL< T, TCompare >::iterator CppCommon::BinTreeAVL< T, TCompare >::upper_bound ( const T & item )

inlinenoexcept

Find the iterator which points to the first item that greater than the given item in the binary tree or return end iterator.

Definition at line 223 of file bintree_avl.inl.

Friends And Related Function Documentation

◆ swap

template<typename T , typename TCompare = std::less<T>>

template<typename U , typename UCompare >

void swap	(	BinTreeAVL< U, UCompare > &	bintree1,
		BinTreeAVL< U, UCompare > &	bintree2
	)

friend

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

include/containers/bintree_avl.h
include/containers/bintree_avl.inl

Classes

Public Types

Public Member Functions

Friends

Detailed Description

template<typename T, typename TCompare = std::less<T>> class CppCommon::BinTreeAVL< T, TCompare >

Member Typedef Documentation

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ const_reverse_iterator

◆ difference_type

◆ iterator

◆ pointer

◆ reference

◆ reverse_iterator

◆ size_type

◆ value_compare

◆ value_type

Constructor & Destructor Documentation

◆ BinTreeAVL() [1/4]

◆ BinTreeAVL() [2/4]

◆ BinTreeAVL() [3/4]

◆ BinTreeAVL() [4/4]

◆ ~BinTreeAVL()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ compare()

◆ crbegin()

◆ crend()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ highest() [1/2]

◆ highest() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ lower_bound() [1/2]

◆ lower_bound() [2/2]

◆ lowest() [1/2]

◆ lowest() [2/2]

◆ operator bool()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ root() [1/2]

◆ root() [2/2]

◆ size()

◆ swap()

◆ upper_bound() [1/2]

◆ upper_bound() [2/2]

Friends And Related Function Documentation

◆ swap

template<typename T, typename TCompare = std::less<T>>
class CppCommon::BinTreeAVL< T, TCompare >