Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
Aleph::Gen_Avl_Tree< NodeType, Key, Compare > Class Template Reference
Trees

AVL balanced binary search tree. More...

#include <tpl_avl.H>

Inheritance diagram for Aleph::Gen_Avl_Tree< NodeType, Key, Compare >:
[legend]
Collaboration diagram for Aleph::Gen_Avl_Tree< NodeType, Key, Compare >:
[legend]

Classes

struct  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 (Compare __cmp=Compare()) noexcept
 
void swap (Gen_Avl_Tree &tree) noexcept
 Swap in constant time all the items of this with the items of tree.
 
virtual ~Gen_Avl_Tree () 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.
 
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 an AVL tree the node containing key key.
 
bool verify () const noexcept
 

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
 

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
 

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< NodeType, Key, Compare >

AVL balanced binary search tree.

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 implementation uses balance factors stored in each node to track the height difference between subtrees. Rotations are performed after insertions and deletions to maintain the AVL property.

Template Parameters
NodeTypeTemplate for the node type (typically AvlNode).
KeyThe type of keys stored in the tree.
CompareComparison functor for ordering keys.
Complexity:
  • Search: O(log n) worst case
  • Insert: O(log n) worst case
  • Delete: O(log n) worst case
  • Space: O(n)
Example:
Avl_Tree<int> tree;
tree.insert(new Avl_Tree<int>::Node(42));
tree.insert(new Avl_Tree<int>::Node(17));
auto node = tree.search(42);
if (node != nullptr)
std::cout << "Found: " << node->get_key() << '\n';
Aleph::Gen_Avl_Tree::search
Node * search(const Key &key) const noexcept
Search a node containing key; if found, then a pointer to the node containing it is returned; otherwi...
Definition tpl_avl.H:513
Aleph::Gen_Avl_Tree::insert
Node * insert(Node *p) noexcept
Insert the node pointed by p in the tree.
Definition tpl_avl.H:529
Aleph::Gen_Avl_Tree::Node
NodeType< Key > Node
Definition tpl_avl.H:109
Aleph::Avl_Tree
AVL binary search tree with nodes without virtual destructor.
Definition tpl_avl.H:704
Note
This is a low-level implementation that manages raw nodes. For automatic memory management, use DynSetAvlTree instead.
See also
Avl_Tree Convenient typedef with default node type.
DynSetAvlTree High-level wrapper with automatic memory management.

Definition at line 106 of file tpl_avl.H.

Member Typedef Documentation

◆ key_type

template<template< typename > class NodeType, typename Key , class Compare >
using Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::key_type = Key

Definition at line 477 of file tpl_avl.H.

◆ Node

template<template< typename > class NodeType, typename Key , class Compare >
using Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::Node = NodeType<Key>

Definition at line 109 of file tpl_avl.H.

Member Enumeration Documentation

◆ Rotation_Type

template<template< typename > class NodeType, typename Key , class Compare >
enum Aleph::Gen_Avl_Tree::Rotation_Type
private
Enumerator
ROTATE_LEFT 
ROTATE_RIGHT 
DOUBLE_ROTATE_LEFT 
DOUBLE_ROTATE_RIGHT 

Definition at line 314 of file tpl_avl.H.

Constructor & Destructor Documentation

◆ Gen_Avl_Tree()

template<template< typename > class NodeType, typename Key , class Compare >
Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::Gen_Avl_Tree ( Compare  __cmp = Compare())
inlinenoexcept

Definition at line 485 of file tpl_avl.H.

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

◆ ~Gen_Avl_Tree()

template<template< typename > class NodeType, typename Key , class Compare >
virtual Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::~Gen_Avl_Tree ( )
inlinevirtualnoexcept

Definition at line 503 of file tpl_avl.H.

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

Member Function Documentation

◆ avl_stack_empty()

template<template< typename > class NodeType, typename Key , class Compare >
bool Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::avl_stack_empty ( )
inlineprivatenoexcept

Definition at line 118 of file tpl_avl.H.

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

Referenced by Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::~Gen_Avl_Tree(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::restore_avl_after_insertion(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_and_stack_avl(), and Aleph::Gen_Avl_Tree< 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< NodeType, Key, Compare >::clean_avl_stack ( )
inlineprivatenoexcept

Definition at line 120 of file tpl_avl.H.

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

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

◆ doubleRotateLeft()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::doubleRotateLeft ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 240 of file tpl_avl.H.

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

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

◆ doubleRotateRight()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::doubleRotateRight ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 277 of file tpl_avl.H.

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

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

◆ get_compare()

template<template< typename > class NodeType, typename Key , class Compare >
constexpr Compare & Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::get_compare ( )
inlineconstexprnoexcept

Definition at line 483 of file tpl_avl.H.

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

◆ getRoot() [1/2]

template<template< typename > class NodeType, typename Key , class Compare >
constexpr Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot ( ) const
inlineconstexprnoexcept

Return a modifiable reference to tree's root.

Definition at line 509 of file tpl_avl.H.

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

◆ getRoot() [2/2]

template<template< typename > class NodeType, typename Key , class Compare >
constexpr Node *& Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot ( )
inlineconstexprnoexcept

Return a modifiable reference to tree's root.

Definition at line 506 of file tpl_avl.H.

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

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

◆ insert()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert ( Node *  p)
inlinenoexcept

Insert the node pointed by p in the tree.

‘insert(p)’ inserts the node p into AVL tree. If KEY(p) is found in the tree, then no insertion is done and nullptr is returned. Otherwise, p is inserted and this same value is returned.

Parameters
[in]pthe node to be inserted
Returns
a the pointer p if KEY(p) is not found in the tree, nullptr otherwise.

Definition at line 529 of file tpl_avl.H.

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

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

◆ insert_dup()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert_dup ( Node *  p)
inlinenoexcept

Insert the node p without testing for key duplicity.

Definition at line 589 of file tpl_avl.H.

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

Referenced by TEST(), and TEST().

◆ key_comp()

template<template< typename > class NodeType, typename Key , class Compare >
Aleph::Gen_Avl_Tree< 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 480 of file tpl_avl.H.

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

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

◆ remove()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove ( const Key &  key)
inlinenoexcept

Remove from an AVL tree the node containing key key.

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

Definition at line 608 of file tpl_avl.H.

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

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

◆ restore_avl()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::restore_avl ( Node *  p,
Node *  pp 
)
inlinestaticprivatenoexcept

Definition at line 340 of file tpl_avl.H.

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

Referenced by Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::restore_avl_after_deletion(), and Aleph::Gen_Avl_Tree< 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< NodeType, Key, Compare >::restore_avl_after_deletion ( bool  left_deficit)
inlineprivatenoexcept

Definition at line 451 of file tpl_avl.H.

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

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

◆ restore_avl_after_insertion()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::restore_avl_after_insertion ( Node *  p)
inlineprivatenoexcept

Definition at line 361 of file tpl_avl.H.

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

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

◆ rotateLeft()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::rotateLeft ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 200 of file tpl_avl.H.

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

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

◆ rotateRight()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::rotateRight ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 220 of file tpl_avl.H.

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

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

◆ rotation_type()

template<template< typename > class NodeType, typename Key , class Compare >
static Rotation_Type Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::rotation_type ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 319 of file tpl_avl.H.

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

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

◆ search()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree< 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 513 of file tpl_avl.H.

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

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

◆ search_and_stack_avl()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_and_stack_avl ( const Key &  key,
signed char &  cmp_result 
)
inlineprivatenoexcept

Definition at line 122 of file tpl_avl.H.

References Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::avl_stack_empty(), Aleph::Gen_Avl_Tree< 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< NodeType, Key, Compare >::root, Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove(), and Aleph::Gen_Avl_Tree< 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< NodeType, Key, Compare >::search_dup_and_stack_avl ( const Key &  key,
signed char &  cmp_result 
)
inlineprivatenoexcept

Definition at line 168 of file tpl_avl.H.

References Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::avl_stack_empty(), Aleph::Gen_Avl_Tree< 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< NodeType, Key, Compare >::root, and Aleph::FixedStack< T >::top().

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

◆ search_or_insert()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_or_insert ( Node *  p)
inlinenoexcept

Search or insert a key.

search_or_insert(p) searches in the tree a node containing KEY(p). If this is found, then a pointer to the node in the tree is returned. Otherwise, p is inserted and its value returned,

This method is very useful when it is required to search and eventually to insert,

Parameters
[in]pthe node whose key must be searched and eventually inserted,
Returns
if p is inserted, the value is returned; otherwise, a pointer to the node containing KEY(p) is returned.

Definition at line 566 of file tpl_avl.H.

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

Referenced by TEST(), and TEST().

◆ swap()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::swap ( Gen_Avl_Tree< NodeType, Key, Compare > &  tree)
inlinenoexcept

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

Parameters
[in]treethe tree to swap with this

Definition at line 497 of file tpl_avl.H.

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

◆ swapWithSuccessor()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::swapWithSuccessor ( Node *  p,
Node *&  pp 
)
inlineprivatenoexcept

Definition at line 402 of file tpl_avl.H.

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

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

◆ verify()

template<template< typename > class NodeType, typename Key , class Compare >
bool Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify ( ) const
inlinenoexcept

Definition at line 662 of file tpl_avl.H.

References is_avl(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::root.

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

Member Data Documentation

◆ avl_stack

template<template< typename > class NodeType, typename Key , class Compare >
FixedStack<Node *> Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::avl_stack
private

The type of node.

Definition at line 112 of file tpl_avl.H.

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

◆ cmp

template<template< typename > class NodeType, typename Key , class Compare >
Compare Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::cmp
private

Definition at line 116 of file tpl_avl.H.

Referenced by Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::key_comp(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_and_stack_avl(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_dup_and_stack_avl(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::swap().

◆ head_node

template<template< typename > class NodeType, typename Key , class Compare >
Node Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::head_node
private

Definition at line 113 of file tpl_avl.H.

◆ head_ptr

template<template< typename > class NodeType, typename Key , class Compare >
Node* Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::head_ptr
private

Definition at line 114 of file tpl_avl.H.

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

◆ root

template<template< typename > class NodeType, typename Key , class Compare >
Node*& Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::root
private

Definition at line 115 of file tpl_avl.H.

Referenced by Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::restore_avl_after_deletion(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_and_stack_avl(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_dup_and_stack_avl(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::swap(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

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