datastructures::detail Namespace Reference

Classes
class	avl_iterator
	The AVL tree iterator type. More...
struct	avl_node
	AVL Tree Node. More...
class	avl_tree
	AVL tree implementation. More...
class	avl_tree_base
	Base class for avl trees. More...
struct	persistent_avl_node
	Persistent AVL Tree Node. More...
class	persistent_avl_tree
	Persitent AVL tree implementation. More...

Typedefs
using	avl_sign_type = int8_t
	The type to use for the trinary sign value for each node.
template<class TNode , class TAlloc >
using	avl_node_allocator_type = std::allocator_traits< TAlloc >::template rebind_alloc< TNode >
	An allocator to allocate nodes.
template<class TNode , class TAlloc >
using	avl_node_ptr = std::allocator_traits< avl_node_allocator_type< TNode, TAlloc > >::pointer
	A node pointer type.
using	persistent_avl_version_type = int
	The version type.

Functions
int	avl_calc_max_height (size_t n)
	Returns the maximum allowed height for an AVL tree of given size.

Typedef Documentation

avl_node_allocator_type

template<class TNode , class TAlloc >

using datastructures::detail::avl_node_allocator_type = typedef std::allocator_traits<TAlloc>::template rebind_alloc<TNode>

An allocator to allocate nodes.

Decladed externally for easier use in the other classes.

Template Parameters

TNode	The node type to allocate.
TAlloc	Allocator to rebind from, usually the item allocator.

avl_node_ptr

template<class TNode , class TAlloc >

using datastructures::detail::avl_node_ptr = typedef std::allocator_traits<avl_node_allocator_type<TNode, TAlloc> >::pointer

A node pointer type.

Automatically deduces the node pointer type based on the given node type and allocator.

Template Parameters

TNode	The node type.
TAlloc	Allocator to rebind the node allocator from, usually the item allocator.

avl_sign_type

using datastructures::detail::avl_sign_type = typedef int8_t

The type to use for the trinary sign value for each node.

It represent whether the node is leaning left, right or is balanced.

persistent_avl_version_type

using datastructures::detail::persistent_avl_version_type = typedef int

The version type.

Function Documentation

avl_calc_max_height()

int datastructures::detail::avl_calc_max_height ( size_t  n )

inline

Returns the maximum allowed height for an AVL tree of given size.

Computes the height of the tallest tree that can be build from number of nodes n.

Correct usage is tree.get_height() <= avl_calc_max_height(tree.size()). This is a necessary contition of being balanced.

The value is computed by iteratively computing the modified Fibonatchi numbers: $a_{n+2} = a_{n} + a_{n+1} + 1$ which represent thi minimum number of nodes per a given height and checking it against the given n until it is equal to or bigger than it.

Parameters

n	The number of nodes

Returns

The maximum height.

Note

Time Complexity: O(log n)