AVL binary search tree with virtual destructor in its nodes and with subtree counters for select/position operations. More...

#include <tpl_avlRk.H>

Inheritance diagram for Aleph::Avl_Tree_Rk_Vtl< Key, Compare >:

[legend]

Collaboration diagram for Aleph::Avl_Tree_Rk_Vtl< Key, Compare >:

[legend]

Public Types
using	Base = Gen_Avl_Tree_Rk< AvlNodeRkVtl, Key, Compare >

Public Types inherited from Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >
using	Node = NodeType< Key >

using	key_type = Key

Additional Inherited Members
Public Member Functions inherited from Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >
constexpr Compare &	key_comp () noexcept
	The key type.

constexpr Compare &	get_compare () noexcept

	Gen_Avl_Tree_Rk (Compare cmf_fct=Compare()) noexcept

void	swap (Gen_Avl_Tree_Rk &tree) noexcept
	Swap in constant time all the items of `this` with the items of `tree`.

virtual	~Gen_Avl_Tree_Rk () noexcept

constexpr Node *&	getRoot () noexcept
	Return a modifiable reference to tree's root.

constexpr Node *	getRoot () const noexcept
	Return a modifiable reference to tree's root.

size_t	size () const noexcept
	Return the number of nodes in the tree.

constexpr bool	is_empty () const noexcept
	Return true if tree is empty.

Node *	search (const Key &key) const noexcept
	Search a node containing key; if found, then a pointer to the node containing it is returned; otherwise `nullptr` is returned.

Node *	insert (Node *p) noexcept
	Insert the node pointed by p in the tree.

Node *	search_or_insert (Node *p) noexcept
	Search or insert a key.

Node *	insert_dup (Node *p) noexcept
	Insert the node p without testing for key duplicity.

Node *	remove (const Key &key) noexcept
	Remove from tree the node containing key.

Node *	select (const size_t i) const
	Return the i-th node in order sense.

std::pair< long, Node * >	position (const Key &key) const noexcept
	Compute the inorder position of a key.

std::pair< long, Node * >	find_position (const Key &key) const noexcept
	Find the inorder position of a key in the tree.

bool	verify () const noexcept
	Return true if the tree is a valid AVL tree with correct counters.

void	join_exclusive (Gen_Avl_Tree_Rk &t) noexcept
	Join this tree exclusively with another tree.

Node *	split_key (const Key &key, Gen_Avl_Tree_Rk &t1, Gen_Avl_Tree_Rk &t2) noexcept
	Split tree by key.

void	split_key_dup (const Key &key, Gen_Avl_Tree_Rk &t1, Gen_Avl_Tree_Rk &t2) noexcept
	Split tree by key including duplicates.

void	split_pos (const size_t pos, Gen_Avl_Tree_Rk &t1, Gen_Avl_Tree_Rk &t2) noexcept
	Split tree by inorder position.

Detailed Description

template<typename Key, class Compare = Aleph::less<Key>>
struct Aleph::Avl_Tree_Rk_Vtl< Key, Compare >

AVL binary search tree with virtual destructor in its nodes and with subtree counters for select/position operations.

Parameters

Key	the key type stored in the tree nodes.
Compare	key comparison class; by default, this is the less-than relational operator for type Key.

See also: Avl_Tree_Rk

Definition at line 1440 of file tpl_avlRk.H.

Member Typedef Documentation

◆ Base

template<typename Key , class Compare = Aleph::less<Key>>

using Aleph::Avl_Tree_Rk_Vtl< Key, Compare >::Base = Gen_Avl_Tree_Rk<AvlNodeRkVtl, Key, Compare>

Definition at line 1442 of file tpl_avlRk.H.

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

tpl_avlRk.H

Public Types

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Base