Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Protected Attributes | Private Member Functions | List of all members
Aleph::BinTree_Operation< Node, Cmp > Class Template Reference
Trees

Functor encompassing basic operation for binary search trees. More...

#include <tpl_binTreeOps.H>

Inheritance diagram for Aleph::BinTree_Operation< Node, Cmp >:
[legend]
Collaboration diagram for Aleph::BinTree_Operation< Node, Cmp >:
[legend]

Public Types

using Key = typename Node::key_type
 
using key_type = typename Node::key_type
 The type of key.
 

Public Member Functions

Cmp & key_comp () noexcept
 Return the comparison criteria.
 
Cmp & get_compare () noexcept
 
 BinTree_Operation (Cmp cmp_=Cmp()) noexcept
 The type of key.
 
Node * search (Node *root, const Key &key) noexcept
 Search a node with a specific key.
 
Node * search_parent (Node *root, const Key &key, Node *&parent) noexcept
 Search a key and find its node and parent.
 
Node * search_rank_parent (Node *root, const Key &key) noexcept
 Rank search of a key in a binary search tree.
 
Node * insert (Node *&root, Node *p) noexcept
 Insert a node p in a binary search tree.
 
Node * insert_dup (Node *&root, Node *p) noexcept
 Insert a node p in a binary search tree.
 
Node * search_or_insert (Node *&r, Node *p) noexcept
 Search or insert a node in a binary search tree.
 
bool split_key_rec (Node *&root, const Key &key, Node *&ts, Node *&tg) noexcept
 Split recursively according to a key.
 
void split_key_dup_rec (Node *&root, const typename Node::key_type &key, Node *&ts, Node *&tg) noexcept
 Split a tree according to a key value.
 
Node * remove (Node *&root, const Key &key) noexcept
 Remove a key from a binary search tree.
 
Node * insert_root (Node *&root, Node *p) noexcept
 Insert the node p as the root of a binary search tree.
 
Node * insert_dup_root (Node *&root, Node *p) noexcept
 Insert node p as root of a binary search tree.
 
Node * join_preorder (Node *t1, Node *t2, Node *&dup) noexcept
 Union of two binary search trees.
 
Node * join (Node *t1, Node *t2, Node *&dup) noexcept
 Fast union of two binary search trees.
 
void split_key (Node *root, const Key &key, Node *&l, Node *&r) noexcept
 Split a binary search tree according to a key.
 
Node * insert_root_rec (Node *root, Node *p) noexcept
 Insert a node as root in a binary search tree.
 
Node * search_or_insert_root_rec (Node *root, Node *p) noexcept
 Search and eventually insert p as root in a binary search tree.
 

Protected Attributes

Cmp cmp
 

Private Member Functions

bool split_key_rec_helper (Node *root, const Key &key, Node *&ts, Node *&tg) noexcept
 
void split_key_dup_rec_helper (Node *root, const typename Node::key_type &key, Node *&ts, Node *&tg) noexcept
 

Detailed Description

template<class Node, class Cmp = Aleph::less<typename Node::key_type>>
class Aleph::BinTree_Operation< Node, Cmp >

Functor encompassing basic operation for binary search trees.

See also
BinNode

Definition at line 56 of file tpl_binTreeOps.H.

Member Typedef Documentation

◆ Key

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
using Aleph::BinTree_Operation< Node, Cmp >::Key = typename Node::key_type

Definition at line 68 of file tpl_binTreeOps.H.

◆ key_type

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
using Aleph::BinTree_Operation< Node, Cmp >::key_type = typename Node::key_type

The type of key.

Definition at line 70 of file tpl_binTreeOps.H.

Constructor & Destructor Documentation

◆ BinTree_Operation()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Aleph::BinTree_Operation< Node, Cmp >::BinTree_Operation ( Cmp  cmp_ = Cmp())
inlinenoexcept

The type of key.

Initialize the functor with comparison criteria cmp_

Definition at line 73 of file tpl_binTreeOps.H.

Member Function Documentation

◆ get_compare()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Cmp & Aleph::BinTree_Operation< Node, Cmp >::get_compare ( )
inlinenoexcept

Definition at line 66 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp.

◆ insert()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::insert ( Node *&  root,
Node *  p 
)
inlinenoexcept

Insert a node p in a binary search tree.

insert(root, p) inserts the node p in the binary search tree with root

Parameters
[in,out]rootof tree
[in]ppointer to the node to be inserted
Returns
p if this was inserted; that is if p->get_key() is not in the tree; otherwise, Node::NullPtr is returned

Definition at line 135 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, Aleph::BinTree_Operation< Node, Cmp >::insert(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::insert(), Aleph::BinTree_Operation< Node, Cmp >::join(), and Aleph::BinTree_Operation< Node, Cmp >::join_preorder().

◆ insert_dup()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::insert_dup ( Node *&  root,
Node *  p 
)
inlinenoexcept

Insert a node p in a binary search tree.

insert_dup(root, p) inserts the node p in the binary search tree with root. The key contained in p can be already present in the tree.

Parameters
[in,out]rootof tree
[in]ppointer to the node to be inserted
Returns
the pointer p

Definition at line 166 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, Aleph::BinTree_Operation< Node, Cmp >::insert_dup(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::insert_dup().

◆ insert_dup_root()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::insert_dup_root ( Node *&  root,
Node *  p 
)
inlinenoexcept

Insert node p as root of a binary search tree.

The key of p can be duplicated.

Parameters
[in,out]rootof tree
[in]pnode to insert as root
Returns
the pointer p which has became the root of tree

Definition at line 364 of file tpl_binTreeOps.H.

References KEY, Aleph::LLINK(), Aleph::RLINK(), root(), and Aleph::BinTree_Operation< Node, Cmp >::split_key_dup_rec().

◆ insert_root()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::insert_root ( Node *&  root,
Node *  p 
)
inlinenoexcept

Insert the node p as the root of a binary search tree.

insert_root(root, p) inserts in the tree root the node p. After insertion, p becomes the new root of tree.

Parameters
[in,out]rootof binary search tree
[in]ppointer to node to insert
Returns
a pointer to p if this was inserted; that is, if p->get_key() was not present in the tree. Otherwise, no insertion is done and Node::NullPtr is returned

Definition at line 343 of file tpl_binTreeOps.H.

References KEY, l, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), and Aleph::BinTree_Operation< Node, Cmp >::split_key_rec().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::join().

◆ insert_root_rec()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::insert_root_rec ( Node *  root,
Node *  p 
)
inlinenoexcept

Insert a node as root in a binary search tree.

This version first inserts p as a leaf of a tree. Then p is rotated until the root.

Parameters
[in]rootof tree
[in]ppointer to the node to insert
Returns
pointer to p if p->get_key() is not in the tree. Otherwise the function returns Node::NullPtr

Definition at line 514 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, Aleph::BinTree_Operation< Node, Cmp >::insert_root_rec(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), Aleph::rotate_to_left(), and Aleph::rotate_to_right().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::insert_root_rec().

◆ join()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::join ( Node *  t1,
Node *  t2,
Node *&  dup 
)
inlinenoexcept

Fast union of two binary search trees.

join(t1, t2, dup) joins the nodes of t1 with the nodes of t2. The duplicated keys of t2 are copied in the binary search tree dup.

Parameters
[in]t1root of first tree
[in]t2root of second tree
[out]duptree where the duplicated keys of t2 are put
Returns
pointer to the root of resulting join

Definition at line 409 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::insert(), Aleph::BinTree_Operation< Node, Cmp >::insert_root(), Aleph::BinTree_Operation< Node, Cmp >::join(), KEY, l, Aleph::LLINK(), Aleph::maps(), Aleph::BinTree_Operation< Node, Cmp >::remove(), Aleph::HTList::reset(), and Aleph::RLINK().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::join().

◆ join_preorder()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::join_preorder ( Node *  t1,
Node *  t2,
Node *&  dup 
)
inlinenoexcept

Union of two binary search trees.

Warning
This union is \(O(n \lg m)\) where n and m are the sizes of t1 and t2respectively. Use join() which is much more faster
Parameters
[in]t1root of first tree
[in]t2root of second tree
[out]duproot of tree where the duplicated keys will be put
Returns
a pointer to the resulting root of tree

Definition at line 381 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::insert(), Aleph::BinTree_Operation< Node, Cmp >::join_preorder(), l, Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::join_preorder().

◆ key_comp()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Aleph::BinTree_Operation< Node, Cmp >::key_comp ( )
inlinenoexcept

Return 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 63 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp.

◆ remove()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::remove ( Node *&  root,
const Key &  key 
)
inlinenoexcept

Remove a key from a binary search tree.

Parameters
[in,out]rootof tree
[in]keyto remove
Returns
a valid pointer to the removed node if key was found in the tree, Node::NullPtr otherwise

Definition at line 314 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, Aleph::join_exclusive(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::BinTree_Operation< Node, Cmp >::remove(), Aleph::HTList::reset(), Aleph::RLINK(), and root().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::join(), and Aleph::BinTree_Operation< Node, Cmp >::remove().

◆ search()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::search ( Node *  root,
const Key &  key 
)
inlinenoexcept

Search a node with a specific key.

Parameters
[in]rootof the tree
[in]keyto be searched
Returns
a pointer to a node containing the key if this was found; Node::NullPtr otherwise

Definition at line 84 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, root(), and Aleph::searchInBinTree().

◆ search_or_insert()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::search_or_insert ( Node *&  r,
Node *  p 
)
inlinenoexcept

Search or insert a node in a binary search tree.

search_or_insert(root, p) searches in root a node containing p->get_key(). If found, then this node is returned. Otherwise, p is inserted and returned.

Parameters
[in,out]rroot of tree
[in]pnode to search or insert
Returns
p if its key was not in the tree; otherwise, a pointer containing the tree is returned.

Definition at line 194 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and Aleph::BinTree_Operation< Node, Cmp >::search_or_insert().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::search_or_insert().

◆ search_or_insert_root_rec()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::search_or_insert_root_rec ( Node *  root,
Node *  p 
)
inlinenoexcept

Search and eventually insert p as root in a binary search tree.

Parameters
[in]rootof tree
[in]ppointer to the node to eventually insert
Returns
if p is inserted, then it returns p; otherwise, it returns a pointer to the tree node containing to p->get_key()

Definition at line 550 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), Aleph::rotate_to_left(), Aleph::rotate_to_right(), and Aleph::BinTree_Operation< Node, Cmp >::search_or_insert_root_rec().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::search_or_insert_root_rec().

◆ search_parent()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Node * Aleph::BinTree_Operation< Node, Cmp >::search_parent ( Node *  root,
const Key &  key,
Node *&  parent 
)
inlinenoexcept

Search a key and find its node and parent.

Parameters
[in]rootof tree
[in]keyto search
[out]parentpointer to parent node if key was found. Otherwise, value is undetermined
Returns
a valid pointer to a node containing key if this is found; otherwise, it returns a pointer to the last visited node

Definition at line 98 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, Aleph::maps(), and root().

◆ split_key()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
void Aleph::BinTree_Operation< Node, Cmp >::split_key ( Node *  root,
const Key &  key,
Node *&  l,
Node *&  r 
)
inlinenoexcept

Split a binary search tree according to a key.

split_key(root, key, l, r) splits the tree root according to key. At the end, l contains all the keys lesser than key and r all the keys greater or equal than key.

Parameters
[in,out]rootof tree to split
[in]keyfor splitting
[out]ltree with keys lesser than key
[out]rtree with keys greater or equal than key

Definition at line 448 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, KEY, l, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().

◆ split_key_dup_rec()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
void Aleph::BinTree_Operation< Node, Cmp >::split_key_dup_rec ( Node *&  root,
const typename Node::key_type &  key,
Node *&  ts,
Node *&  tg 
)
inlinenoexcept

Split a tree according to a key value.

split_key_dup_rec(root, key, ts, tg) splits according to key the tree withrootand build two trees.t1contains the keys lesser thankeyandt2the keys greater or equal thankey`.

Parameters
[in,out]rootof tre to be split
[in]keyfor splitting
[out]tstree with the keys lesser than key
[out]tgtree with the keys greater or equal than key

Definition at line 300 of file tpl_binTreeOps.H.

References Aleph::maps(), root(), and Aleph::BinTree_Operation< Node, Cmp >::split_key_dup_rec_helper().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::insert_dup_root().

◆ split_key_dup_rec_helper()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
void Aleph::BinTree_Operation< Node, Cmp >::split_key_dup_rec_helper ( Node *  root,
const typename Node::key_type &  key,
Node *&  ts,
Node *&  tg 
)
inlineprivatenoexcept

Definition at line 271 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), and Aleph::BinTree_Operation< Node, Cmp >::split_key_dup_rec_helper().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::split_key_dup_rec(), and Aleph::BinTree_Operation< Node, Cmp >::split_key_dup_rec_helper().

◆ split_key_rec()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
bool Aleph::BinTree_Operation< Node, Cmp >::split_key_rec ( Node *&  root,
const Key &  key,
Node *&  ts,
Node *&  tg 
)
inlinenoexcept

Split recursively according to a key.

split_key_rec(root, key, ts, tg) splits the tree with root in two trees t1 which contain the keys lesser than key and t2 which contains the keys greater than key.

The split only is performed if key is not in the tree.

Parameters
[in,out]rootof tree
[in]keyfor slitting
[out]tstree with keys lesser than key
[out]tgtree with keys greater than key
Returns
true if the tree was split; that is if key was not in the tree. Otherwise, the split is not performed and it return false

Definition at line 261 of file tpl_binTreeOps.H.

References Aleph::maps(), root(), and Aleph::BinTree_Operation< Node, Cmp >::split_key_rec_helper().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::insert_root().

◆ split_key_rec_helper()

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
bool Aleph::BinTree_Operation< Node, Cmp >::split_key_rec_helper ( Node *  root,
const Key &  key,
Node *&  ts,
Node *&  tg 
)
inlineprivatenoexcept

Definition at line 216 of file tpl_binTreeOps.H.

References Aleph::BinTree_Operation< Node, Cmp >::cmp, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), and Aleph::BinTree_Operation< Node, Cmp >::split_key_rec_helper().

Referenced by Aleph::BinTree_Operation< Node, Cmp >::split_key_rec(), and Aleph::BinTree_Operation< Node, Cmp >::split_key_rec_helper().

Member Data Documentation

◆ cmp

template<class Node , class Cmp = Aleph::less<typename Node::key_type>>
Cmp Aleph::BinTree_Operation< Node, Cmp >::cmp
protected

Definition at line 59 of file tpl_binTreeOps.H.

Referenced by Aleph::BinTreeXt_Operation< Node, Cmp >::find_position(), Aleph::BinTree_Operation< Node, Cmp >::get_compare(), Aleph::BinTreeXt_Operation< Node, Cmp >::inorder_position(), Aleph::BinTree_Operation< Node, Cmp >::insert(), Aleph::BinTree_Operation< Node, Cmp >::insert_dup(), Aleph::BinTree_Operation< Node, Cmp >::insert_root_rec(), Aleph::BinTree_Operation< Node, Cmp >::key_comp(), Aleph::BinTree_Operation< Node, Cmp >::remove(), Aleph::BinTree_Operation< Node, Cmp >::search(), Aleph::BinTree_Operation< Node, Cmp >::search_or_insert(), Aleph::BinTree_Operation< Node, Cmp >::search_or_insert_root_rec(), Aleph::BinTree_Operation< Node, Cmp >::search_parent(), Aleph::BinTree_Operation< Node, Cmp >::search_rank_parent(), Aleph::BinTree_Operation< Node, Cmp >::split_key(), Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_dup_rec(), Aleph::BinTree_Operation< Node, Cmp >::split_key_dup_rec_helper(), Aleph::BinTreeXt_Operation< Node, Cmp >::split_key_rec(), and Aleph::BinTree_Operation< Node, Cmp >::split_key_rec_helper().

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