Red-Black binary search tree with nodes without virtual destructor and with subtree counters for select/position operations. More...

#include <tpl_rbRk.H>

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

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

Public Types
using	Base = Gen_Rb_Tree_Rk< RbNodeRk, Key, Compare >

Public Types inherited from Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >
typedef NodeType< Key >	Node

typedef Key	key_type

Additional Inherited Members
Public Member Functions inherited from Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >
Compare &	key_comp () noexcept

Compare &	get_compare () noexcept

	Gen_Rb_Tree_Rk (Compare cmp_arg=Compare())

void	swap (Gen_Rb_Tree_Rk &tree) noexcept

	Gen_Rb_Tree_Rk (Gen_Rb_Tree_Rk &&tree) noexcept

Gen_Rb_Tree_Rk &	operator= (Gen_Rb_Tree_Rk &&tree) noexcept

virtual	~Gen_Rb_Tree_Rk ()=default

Node *	search (const Key &key)

Node *&	getRoot () noexcept

bool	is_empty () const noexcept

size_t	size () const noexcept

Node *	insert (Node *p)

Node *	search_or_insert (Node *p)

Node *	insert_dup (Node *p)

bool	verify () const

Node *	remove (const Key &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.

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

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

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

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

Detailed Description

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

Red-Black binary search tree with nodes without virtual destructor and with subtree counters for select/position operations.

Parameters

Key	key type stored in the tree nodes.
Compare	comparison functor between keys.

Definition at line 1543 of file tpl_rbRk.H.

Member Typedef Documentation

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

Definition at line 1545 of file tpl_rbRk.H.

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