Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare > Class Template Reference

AVL balanced binary search tree with rank (order statistics). More...

#include <tpl_avlRk.H>

Inheritance diagram for Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >:

Collaboration diagram for Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >:

Classes
class	Iterator
	Iterator over the nodes. More...

Public Types
using	Node = NodeType< Key >
using	key_type = Key

Public Member Functions
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.

Private Types
enum	Rotation_Type { ROTATE_LEFT , ROTATE_RIGHT , DOUBLE_ROTATE_LEFT , DOUBLE_ROTATE_RIGHT }

Private Member Functions
bool	avl_stack_empty () noexcept
void	clean_avl_stack () noexcept
Node *	search_and_stack_avl (const Key &key, signed char &cmp_result) noexcept
Node *	search_dup_and_stack_avl (const Key &key, signed char &cmp_result) noexcept
void	restore_avl_after_insertion (Node *p) noexcept
Node *	swapWithSuccessor (Node *p, Node *&pp) noexcept
void	restore_avl_after_deletion (bool left_deficit) noexcept
void	update_counters_after_insertion () noexcept
void	update_counters_after_deletion () noexcept
Node *	split_key_rec (Node *p, const Key &key, Node *&t1, Node *&t2) noexcept
void	split_key_dup_rec (Node *p, const Key &key, Node *&t1, Node *&t2) noexcept
void	split_pos_rec (Node *p, size_t pos, Node *&t1, Node *&t2) noexcept

Static Private Member Functions
static Node *	rotateLeft (Node *p) noexcept
static Node *	rotateRight (Node *p) noexcept
static Node *	doubleRotateLeft (Node *p) noexcept
static Node *	doubleRotateRight (Node *p) noexcept
static Rotation_Type	rotation_type (Node *p) noexcept
static Node *	restore_avl (Node *p, Node *pp) noexcept
static size_t	avl_height (Node *p) noexcept
static Node *	extract_min (Node *&p) noexcept
static Node *	extract_max (Node *&p) noexcept
static Node *	join_exclusive_rec (Node *t1, size_t h1, Node *t2, size_t h2) noexcept
static Node *	join_with_pivot (Node *t1, const size_t h1, Node *pivot, Node *t2, const size_t h2) noexcept
static Node *	join_right (Node *t1, const size_t h1, Node *pivot, Node *t2, const size_t h2) noexcept
static Node *	join_left (Node *t1, const size_t h1, Node *pivot, Node *t2, const size_t h2) noexcept

Private Attributes
FixedStack< Node * >	avl_stack
	The type of node.
Node	head_node
Node *	head_ptr
Node *&	root
Compare	cmp

Detailed Description

template<template< typename > class NodeType, typename Key, class Compare>
class Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >

AVL balanced binary search tree with rank (order statistics).

An AVL tree is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. This guarantees O(log n) worst-case time complexity for search, insertion, and deletion operations.

The maximum height of an AVL tree with n nodes is bounded by: \( 1.4404 \lg{(n + 2)} - 0.3277 \)

This extended version maintains a count in each node representing the number of nodes in its subtree, enabling O(log n) operations for selecting by position and finding the position of a key.

Template Parameters

NodeType	Template for the node type (typically AvlNodeRk).
Key	The type of keys stored in the tree.
Compare	Comparison functor for ordering keys.

Complexity:

• Search: O(log n) worst case
• Insert: O(log n) worst case
• Delete: O(log n) worst case
• Select: O(log n) worst case
• Position: O(log n) worst case
• Space: O(n)

Example:

Avl_Tree_Rk<int> tree;
tree.insert(new Avl_Tree_Rk<int>::Node(42));
tree.insert(new Avl_Tree_Rk<int>::Node(17));
auto node = tree.select(0);  // Get smallest element
auto [pos, found] = tree.position(42);  // Get position of key 42

Note

This is a low-level implementation that manages raw nodes. For automatic memory management, use DynSetAvlTreeRk instead.

See also

Avl_Tree_Rk Convenient typedef with default node type.

Avl_Tree_Rk_Vtl Version with virtual destructor nodes.

tpl_avl.H Base AVL tree without rank operations.

Definition at line 110 of file tpl_avlRk.H.

Member Typedef Documentation

key_type

template<template< typename > class NodeType, typename Key , class Compare >

using Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::key_type = Key

Definition at line 515 of file tpl_avlRk.H.

Node

template<template< typename > class NodeType, typename Key , class Compare >

using Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::Node = NodeType<Key>

Definition at line 113 of file tpl_avlRk.H.

Member Enumeration Documentation

Rotation_Type

template<template< typename > class NodeType, typename Key , class Compare >

enum Aleph::Gen_Avl_Tree_Rk::Rotation_Type

private

Enumerator
ROTATE_LEFT
ROTATE_RIGHT
DOUBLE_ROTATE_LEFT
DOUBLE_ROTATE_RIGHT

Definition at line 333 of file tpl_avlRk.H.

Constructor & Destructor Documentation

Gen_Avl_Tree_Rk()

template<template< typename > class NodeType, typename Key , class Compare >

Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::Gen_Avl_Tree_Rk ( Compare  cmf_fct = Compare() )

inlinenoexcept

Definition at line 523 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_ptr, and Aleph::FixedStack< T >::push().

~Gen_Avl_Tree_Rk()

template<template< typename > class NodeType, typename Key , class Compare >

virtual Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::~Gen_Avl_Tree_Rk ( )

inlinevirtualnoexcept

Definition at line 541 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_empty(), and Aleph::maps().

Member Function Documentation

avl_height()

template<template< typename > class NodeType, typename Key , class Compare >

static size_t Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 747 of file tpl_avlRk.H.

References DIFF, h, Aleph::LLINK(), and Aleph::RLINK().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec().

avl_stack_empty()

template<template< typename > class NodeType, typename Key , class Compare >

bool Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_empty ( )

inlineprivatenoexcept

Definition at line 122 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_ptr, and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::~Gen_Avl_Tree_Rk(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl().

clean_avl_stack()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack ( )

inlineprivatenoexcept

Definition at line 124 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::FixedStack< T >::popn(), and Aleph::FixedStack< T >::size().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_or_insert().

doubleRotateLeft()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateLeft ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 255 of file tpl_avlRk.H.

References Aleph::COUNT(), DIFF, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_min(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

doubleRotateRight()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateRight ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 295 of file tpl_avlRk.H.

References Aleph::COUNT(), DIFF, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_max(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

extract_max()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_max ( Node *&  p )

inlinestaticprivatenoexcept

Definition at line 820 of file tpl_avlRk.H.

References Aleph::COUNT(), DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateRight(), Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateRight().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec().

extract_min()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_min ( Node *&  p )

inlinestaticprivatenoexcept

Definition at line 764 of file tpl_avlRk.H.

References Aleph::COUNT(), DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateLeft(), Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateLeft().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec().

find_position()

template<template< typename > class NodeType, typename Key , class Compare >

std::pair< long, Node * > Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::find_position ( const Key &  key ) const

inlinenoexcept

Find the inorder position of a key in the tree.

Parameters

[in]

key

to be searched

Returns

a pair with the position and the node pointer

Definition at line 729 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::find_position(), Aleph::maps(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::find_position().

get_compare()

template<template< typename > class NodeType, typename Key , class Compare >

constexpr Compare & Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::get_compare ( )

inlineconstexprnoexcept

Definition at line 521 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::key_comp().

getRoot() [1/2]

template<template< typename > class NodeType, typename Key , class Compare >

constexpr Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::getRoot ( ) const

inlineconstexprnoexcept

Return a modifiable reference to tree's root.

Definition at line 547 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

getRoot() [2/2]

template<template< typename > class NodeType, typename Key , class Compare >

constexpr Node *& Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::getRoot ( )

inlineconstexprnoexcept

Return a modifiable reference to tree's root.

Definition at line 544 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST().

insert()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert ( Node *  p )

inlinenoexcept

Insert the node pointed by p in the tree.

Parameters

[in]

p

the node to be inserted

Returns

p if KEY(p) is not found in the tree, nullptr otherwise.

Definition at line 568 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), Aleph::CmpEqual, Aleph::CmpGreater, Aleph::CmpLess, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), Aleph::RLINK(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

insert_dup()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert_dup ( Node *  p )

inlinenoexcept

Insert the node p without testing for key duplicity.

Definition at line 622 of file tpl_avlRk.H.

References Aleph::CmpEqual, Aleph::CmpLess, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), Aleph::RLINK(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

Referenced by TEST(), and TEST().

is_empty()

template<template< typename > class NodeType, typename Key , class Compare >

constexpr bool Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty ( ) const

inlineconstexprnoexcept

Return true if tree is empty.

Definition at line 553 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

join_exclusive()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive ( Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t )

inlinenoexcept

Join this tree exclusively with another tree.

All keys in this tree must be less than all keys in t. After the operation, t becomes empty and this tree contains all nodes.

Parameters

[in,out]

t

tree to join with (will be empty after)

Note

O(m log(n+m)) time complexity where m is size of t

Definition at line 1197 of file tpl_avlRk.H.

References Aleph::COUNT(), DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

join_exclusive_rec()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec ( Node *  t1, size_t  h1, Node *  t2, size_t  h2  )

inlinestaticprivatenoexcept

Definition at line 874 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_max(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_min(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot(), and Aleph::maps().

join_left()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left ( Node *  t1, const size_t  h1, Node *  pivot, Node *  t2, const size_t  h2  )

inlinestaticprivatenoexcept

Definition at line 983 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::COUNT(), DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateRight(), Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateRight().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot().

join_right()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right ( Node *  t1, const size_t  h1, Node *  pivot, Node *  t2, const size_t  h2  )

inlinestaticprivatenoexcept

Definition at line 930 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::COUNT(), DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateLeft(), Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateLeft().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot().

join_with_pivot()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot ( Node *  t1, const size_t  h1, Node *  pivot, Node *  t2, const size_t  h2  )

inlinestaticprivatenoexcept

Definition at line 905 of file tpl_avlRk.H.

References Aleph::COUNT(), DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right(), Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec().

key_comp()

template<template< typename > class NodeType, typename Key , class Compare >

Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::key_comp ( )

inlineconstexprnoexcept

The key type.

Return a reference to the comparison criteria

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 518 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::get_compare().

position()

template<template< typename > class NodeType, typename Key , class Compare >

std::pair< long, Node * > Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::position ( const Key &  key ) const

inlinenoexcept

Compute the inorder position of a key.

Parameters

[in]

key

to be searched

Returns

a pair with the inorder position and the node pointer. If key is not found, position is -1.

Definition at line 714 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::inorder_position(), Aleph::maps(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST(), TEST(), and TEST().

remove()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove ( const Key &  key )

inlinenoexcept

Remove from tree the node containing key.

Returns the removed node if the key is found; nullptr otherwise.

Definition at line 642 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), Aleph::CmpEqual, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_ptr, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion(), Aleph::RLINK(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swapWithSuccessor(), Aleph::FixedStack< T >::top(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion().

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

restore_avl()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl ( Node *  p, Node *  pp  )

inlinestaticprivatenoexcept

Definition at line 358 of file tpl_avlRk.H.

References AH_ERROR, DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::DOUBLE_ROTATE_LEFT, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::DOUBLE_ROTATE_RIGHT, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateLeft(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateRight(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::ROTATE_LEFT, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::ROTATE_RIGHT, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateLeft(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateRight(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotation_type().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion().

restore_avl_after_deletion()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion ( bool  left_deficit )

inlineprivatenoexcept

Definition at line 470 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), DIFF, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::popn(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove().

restore_avl_after_insertion()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion ( Node *  p )

inlineprivatenoexcept

Definition at line 378 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_empty(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), DIFF, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert_dup(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_or_insert().

rotateLeft()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateLeft ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 205 of file tpl_avlRk.H.

References Aleph::COUNT(), DIFF, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_min(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

rotateRight()

template<template< typename > class NodeType, typename Key , class Compare >

static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateRight ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 230 of file tpl_avlRk.H.

References Aleph::COUNT(), DIFF, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_max(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

rotation_type()

template<template< typename > class NodeType, typename Key , class Compare >

static Rotation_Type Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotation_type ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 338 of file tpl_avlRk.H.

References DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::DOUBLE_ROTATE_LEFT, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::DOUBLE_ROTATE_RIGHT, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::ROTATE_LEFT, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::ROTATE_RIGHT.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

search()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search ( const Key &  key ) const

inlinenoexcept

Search a node containing key; if found, then a pointer to the node containing it is returned; otherwise nullptr is returned.

Definition at line 557 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::maps(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST().

search_and_stack_avl()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl ( const Key &  key, signed char &  cmp_result  )

inlineprivatenoexcept

Definition at line 126 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_empty(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::CmpEqual, Aleph::CmpGreater, Aleph::CmpLess, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::popn(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_or_insert().

search_dup_and_stack_avl()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl ( const Key &  key, signed char &  cmp_result  )

inlineprivatenoexcept

Definition at line 172 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_empty(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::CmpEqual, Aleph::CmpGreater, Aleph::CmpLess, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert_dup().

search_or_insert()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_or_insert ( Node *  p )

inlinenoexcept

Search or insert a key.

Parameters

[in]

p

the node whose key must be searched and eventually inserted

Returns

if p is inserted, this value is returned; otherwise, a pointer to the node containing KEY(p) is returned.

Definition at line 598 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), Aleph::CmpEqual, Aleph::CmpGreater, Aleph::CmpLess, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), Aleph::RLINK(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

Referenced by TEST().

select()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::select ( const size_t  i ) const

inline

Return the i-th node in order sense.

Parameters

[in]

i

inorder position of node to be selected

Returns

a pointer to the i-th node inorder sense

Exceptions

out_of_range

if i is greater or equal than the number of nodes of tree

Definition at line 703 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, and Aleph::select().

Referenced by TEST(), TEST(), and TEST().

size()

template<template< typename > class NodeType, typename Key , class Compare >

size_t Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size ( ) const

inlinenoexcept

Return the number of nodes in the tree.

Definition at line 550 of file tpl_avlRk.H.

References Aleph::COUNT(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

split_key()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key ( const Key &  key, Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t1, Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t2  )

inlinenoexcept

Split tree by key.

After the operation:

• t1 contains all keys < key
• t2 contains all keys > key
• This tree becomes empty

Parameters

[in]	key	the splitting key
[out]	t1	tree to receive keys < key
[out]	t2	tree to receive keys > key

Returns

pointer to node containing key, or nullptr if not found

Note

O(n) time complexity (simple iterative implementation)

Definition at line 1247 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), DIFF, Aleph::DynList< T >::insert(), Aleph::FixedStack< T >::is_empty(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST(), and TEST().

split_key_dup()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup ( const Key &  key, Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t1, Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t2  )

inlinenoexcept

Split tree by key including duplicates.

After the operation:

• t1 contains all keys <= key
• t2 contains all keys > key
• This tree becomes empty

Parameters

[in]	key	the splitting key
[out]	t1	tree to receive keys <= key
[out]	t2	tree to receive keys > key

Note

O(n) time complexity (simple iterative implementation)

Definition at line 1297 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), DIFF, Aleph::DynList< T >::insert(), Aleph::FixedStack< T >::is_empty(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST().

split_key_dup_rec()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec ( Node *  p, const Key &  key, Node *&  t1, Node *&  t2  )

inlineprivatenoexcept

Definition at line 1095 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec().

split_key_rec()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec ( Node *  p, const Key &  key, Node *&  t1, Node *&  t2  )

inlineprivatenoexcept

Definition at line 1034 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec().

split_pos()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos ( const size_t  pos, Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t1, Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t2  )

inlinenoexcept

Split tree by inorder position.

After the operation:

• t1 contains nodes at positions [0, pos)
• t2 contains nodes at positions [pos, size)
• This tree becomes empty

Parameters

[in]	pos	the splitting position (0-based)
[out]	t1	tree to receive positions [0, pos)
[out]	t2	tree to receive positions [pos, size)

Note

O(n) time complexity (simple iterative implementation)

Definition at line 1341 of file tpl_avlRk.H.

References Aleph::count(), Aleph::COUNT(), DIFF, Aleph::DynList< T >::insert(), Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size().

Referenced by TEST(), TEST(), and TEST().

split_pos_rec()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec ( Node *  p, size_t  pos, Node *&  t1, Node *&  t2  )

inlineprivatenoexcept

Definition at line 1142 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::COUNT(), DIFF, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec().

swap()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swap ( Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  tree )

inlinenoexcept

Swap in constant time all the items of this with the items of tree.

Parameters

[in]

tree

the tree to swap with this

Definition at line 535 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

swapWithSuccessor()

template<template< typename > class NodeType, typename Key , class Compare >

Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swapWithSuccessor ( Node *  p, Node *&  pp  )

inlineprivatenoexcept

Definition at line 419 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::COUNT(), DIFF, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove().

update_counters_after_deletion()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion ( )

inlineprivatenoexcept

Definition at line 507 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::COUNT(), Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove().

update_counters_after_insertion()

template<template< typename > class NodeType, typename Key , class Compare >

void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion ( )

inlineprivatenoexcept

Definition at line 497 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::COUNT(), Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert_dup(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_or_insert().

verify()

template<template< typename > class NodeType, typename Key , class Compare >

bool Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::verify ( ) const

inlinenoexcept

Return true if the tree is a valid AVL tree with correct counters.

Definition at line 740 of file tpl_avlRk.H.

References Aleph::check_rank_tree(), Aleph::is_avl_rk(), Aleph::maps(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST(), TEST(), and TEST().

Member Data Documentation

avl_stack

template<template< typename > class NodeType, typename Key , class Compare >

FixedStack<Node *> Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack

private

The type of node.

Definition at line 116 of file tpl_avlRk.H.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::Gen_Avl_Tree_Rk(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_empty(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swapWithSuccessor(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

cmp

template<template< typename > class NodeType, typename Key , class Compare >

Compare Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp

private

Definition at line 120 of file tpl_avlRk.H.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::find_position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::key_comp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swap().

head_node

template<template< typename > class NodeType, typename Key , class Compare >

Node Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_node

private

Definition at line 117 of file tpl_avlRk.H.

head_ptr

template<template< typename > class NodeType, typename Key , class Compare >

Node* Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_ptr

private

Definition at line 118 of file tpl_avlRk.H.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::Gen_Avl_Tree_Rk(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_empty(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove().

root

template<template< typename > class NodeType, typename Key , class Compare >

Node*& Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root

private

Definition at line 119 of file tpl_avlRk.H.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::find_position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swap(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::verify().

---

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

• tpl_avlRk.H