Top-down splay tree with rank support. More...

#include <tpl_splay_treeRk.H>

Inheritance diagram for GenTdSplayTreeRk< NodeType, Key, Compare >:

Classes
class	Iterator
	Inorder iterator over the extended splay tree. More...

Public Types
typedef NodeType< Key >	Node

typedef Key	key_type
	The key type stored in the node.

Public Member Functions
Compare &	key_comp ()
	Returns a reference to the comparison functor.

Compare &	get_compare ()

void	splay (const Key &key) noexcept
	search key within tree and splay that node.

	GenTdSplayTreeRk (Compare __cmp=Compare())
	Constructor.

void	swap (GenTdSplayTreeRk &tree)

virtual	~GenTdSplayTreeRk ()
	Destructor.

Node *	insert (Node *p)
	Inserts a node in a top down splay tree.

Node *	insert_dup (Node *p)

Node *	search (const Key &key)
	Searches a key in a top down splay tree.

Node *	search_or_insert (Node *p)

Node *	remove (const Key &key)
	Remove a key from a top-down splay tree.

Node *&	getRoot ()
	Get the top-down splay tree's root.

bool	verify () const

size_t	size () const
	Returns the number of nodes stored in the tree.

bool	is_empty () const
	Returns true if the tree is empty.

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

std::pair< long, Node * >	find_position (const Key &key)
	Returns the inorder (sorted) position of key.

Node *	select (const size_t &i)
	Returns the node whose inorder position in the extended tree is i.

Private Member Functions
signed char	splay_impl (const Key &key) noexcept

Node *	__insert (Node *p)

Node *	splay_max (Node *r) noexcept
	Splay the maximum element to the root.

Private Attributes
Node *	root

Compare	cmp

Static Private Attributes
static constexpr signed char	CmpLess = -1

static constexpr signed char	CmpEqual = 0

static constexpr signed char	CmpGreater = 1

Detailed Description

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

Top-down splay tree with rank support.

A splay tree is a self-adjusting binary search tree that moves recently accessed elements closer to the root. This provides amortized O(log n) time complexity for all operations, with frequently accessed elements having faster access times.

This implementation extends the basic splay tree with COUNT fields in each node, enabling:

O(log n) selection of the k-th smallest element
O(log n) rank queries (position of an element)
All standard BST operations with amortized O(log n) complexity

The splay operation brings the accessed node to the root using a sequence of zig, zig-zig, and zig-zag rotations. This top-down variant performs splaying during the descent, avoiding a second pass.

Template Parameters

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

Complexity (amortized):

Search: O(log n)
Insert: O(log n)
Delete: O(log n)
Select k-th: O(log n)
Rank query: O(log n)

Example:: Splay_Tree_Rk<int> tree;

tree.insert(new Splay_Tree_Rk<int>::Node(42));

tree.insert(new Splay_Tree_Rk<int>::Node(17));

tree.insert(new Splay_Tree_Rk<int>::Node(99));

// Find 2nd smallest element

auto node = tree.select(1); // 0-indexed

// Get rank of element

size_t pos = tree.position(KEY(node));

KEY
@ KEY
Definition btreepic.C:169

GenTdSplayTreeRk::position
std::pair< long, Node * > position(const Key &key)
Returns the inorder (sorted) position of key.
Definition tpl_splay_treeRk.H:472

GenTdSplayTreeRk::insert
Node * insert(Node *p)
Inserts a node in a top down splay tree.
Definition tpl_splay_treeRk.H:274

GenTdSplayTreeRk::Node
NodeType< Key > Node
Definition tpl_splay_treeRk.H:110

GenTdSplayTreeRk::select
Node * select(const size_t &i)
Returns the node whose inorder position in the extended tree is i.
Definition tpl_splay_treeRk.H:537

Splay_Tree_Rk
Definition tpl_splay_treeRk.H:630

Note: This is a low-level implementation managing raw nodes. For automatic memory management, use DynSetSplayTree.

See also: Splay_Tree Basic splay tree without rank support.; DynSetSplayTree High-level wrapper.

Definition at line 107 of file tpl_splay_treeRk.H.

Member Typedef Documentation

◆ key_type

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

typedef Key GenTdSplayTreeRk< NodeType, Key, Compare >::key_type

The key type stored in the node.

Definition at line 207 of file tpl_splay_treeRk.H.

◆ Node

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

typedef NodeType<Key> GenTdSplayTreeRk< NodeType, Key, Compare >::Node

Definition at line 110 of file tpl_splay_treeRk.H.

Constructor & Destructor Documentation

◆ GenTdSplayTreeRk()

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

GenTdSplayTreeRk< NodeType, Key, Compare >::GenTdSplayTreeRk ( Compare __cmp = Compare() )

inline

Constructor.

Definition at line 226 of file tpl_splay_treeRk.H.

◆ ~GenTdSplayTreeRk()

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

virtual GenTdSplayTreeRk< NodeType, Key, Compare >::~GenTdSplayTreeRk ( )

inlinevirtual

Destructor.

Definition at line 239 of file tpl_splay_treeRk.H.

Member Function Documentation

◆ __insert()

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

Node * GenTdSplayTreeRk< NodeType, Key, Compare >::__insert ( Node * p )

inlineprivate

Definition at line 244 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and GenTdSplayTreeRk< NodeType, Key, Compare >::root.

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

◆ find_position()

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

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

inline

Returns the inorder (sorted) position of key.

find_position(key) searches in the extended splay tree for key (which takes \(O(\lg n)\) time) and returns the inorder position of the node that contains the key together with the node. If the key is not in the tree, find_position(key) returns the position where it would be if key belonged to the tree.

The return value is a pair<long, Node*>. The first component is the inorder position and the second is the node.

If key is not found in the tree, three cases can be distinguished:

If key is smaller than the minimum key in the tree, then first is -1 and second is the node containing the minimum key.
If key is greater than the maximum key in the tree, then first is COUNT(root) (number of nodes in the tree) and second is the node containing the maximum key.
In any other case, first is the position that key would have in the tree and second (node p) is a key immediately adjacent to key. Note that second can hold a smaller or greater key, but it is guaranteed to be immediately adjacent to key.

Parameters

[in] key key to search and whose inorder position is requested.

Returns: a pair containing the inorder position of key within the ordered set together with the node if the key is found in the tree; otherwise it returns -1 and the node is unspecified.

Definition at line 511 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::CmpEqual, GenTdSplayTreeRk< NodeType, Key, Compare >::CmpLess, Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), GenTdSplayTreeRk< NodeType, Key, Compare >::root, and GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl().

◆ get_compare()

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

Compare & GenTdSplayTreeRk< NodeType, Key, Compare >::get_compare ( )

inline

Definition at line 213 of file tpl_splay_treeRk.H.

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

◆ getRoot()

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

Node *& GenTdSplayTreeRk< NodeType, Key, Compare >::getRoot ( )

inline

Get the top-down splay tree's root.

Definition at line 442 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::root.

◆ insert()

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

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

inline

Inserts a node in a top down splay tree.

Returns: a pointer to the inserted node if node is not found in tree; nullptr otherwise.

Parameters

p	a pointer to the node to be inserted

Definition at line 274 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::__insert(), GenTdSplayTreeRk< NodeType, Key, Compare >::CmpEqual, Aleph::COUNT(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), GenTdSplayTreeRk< NodeType, Key, Compare >::root, and GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl().

◆ insert_dup()

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

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

inline

Definition at line 293 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::__insert(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), GenTdSplayTreeRk< NodeType, Key, Compare >::root, and GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl().

◆ is_empty()

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

bool GenTdSplayTreeRk< NodeType, Key, Compare >::is_empty ( ) const

inline

Returns true if the tree is empty.

Definition at line 456 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::root.

◆ key_comp()

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

GenTdSplayTreeRk< NodeType, Key, Compare >::key_comp ( )

inline

Returns a reference to the comparison functor.

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 210 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::cmp.

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

◆ position()

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

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

inline

Returns the inorder (sorted) position of key.

position(key) searches in the extended splay tree for key (which takes \(O(\lg n)\) time) and returns the inorder position of the node that contains the key.

Parameters

[in] key key to search and whose inorder position is requested.

Returns: a pair containing the inorder position of key within the ordered set together with the node if the key is found in the tree; otherwise it returns -1 and the node is unspecified.

Definition at line 472 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::CmpEqual, Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), GenTdSplayTreeRk< NodeType, Key, Compare >::root, and GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl().

◆ remove()

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

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

inline

Remove a key from a top-down splay tree.

Searches a key in a top-down splay tree and remove the containing the key if this is found.

Returns: a pointer to node containing the removed key.

Parameters

key to search

Definition at line 405 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::CmpEqual, Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::HTList::reset(), Aleph::RLINK(), GenTdSplayTreeRk< NodeType, Key, Compare >::root, GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl(), and GenTdSplayTreeRk< NodeType, Key, Compare >::splay_max().

◆ search()

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

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

inline

Searches a key in a top down splay tree.

Returns: a pointer to the node containing the key if the key is found; nullptr otherwise.

Parameters

key	key to search

Definition at line 314 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::CmpEqual, Aleph::maps(), GenTdSplayTreeRk< NodeType, Key, Compare >::root, and GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl().

◆ search_or_insert()

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

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

inline

Definition at line 324 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::__insert(), GenTdSplayTreeRk< NodeType, Key, Compare >::CmpEqual, KEY, Aleph::maps(), GenTdSplayTreeRk< NodeType, Key, Compare >::root, and GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl().

◆ select()

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

Node * GenTdSplayTreeRk< NodeType, Key, Compare >::select ( const size_t & i )

inline

Returns the node whose inorder position in the extended tree is i.

select(i) returns the node in the extended splay tree whose inorder position is i.

Parameters

[in] i inorder position to select.

Returns: pointer to the node corresponding to inorder position i.

Exceptions

out_of_range if i is greater than or equal to the number of nodes in the tree.

Definition at line 537 of file tpl_splay_treeRk.H.

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

◆ size()

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

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

inline

Returns the number of nodes stored in the tree.

Definition at line 450 of file tpl_splay_treeRk.H.

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

◆ splay()

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

void GenTdSplayTreeRk< NodeType, Key, Compare >::splay ( const Key & key )

inlinenoexcept

search key within tree and splay that node.

Warning: The tree must not be empty. All public methods check for empty tree before calling splay().

Definition at line 220 of file tpl_splay_treeRk.H.

References Aleph::maps(), and GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl().

◆ splay_impl()

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

signed char GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl ( const Key & key )

inlineprivatenoexcept

Definition at line 119 of file tpl_splay_treeRk.H.

References GenTdSplayTreeRk< NodeType, Key, Compare >::cmp, GenTdSplayTreeRk< NodeType, Key, Compare >::CmpEqual, GenTdSplayTreeRk< NodeType, Key, Compare >::CmpGreater, GenTdSplayTreeRk< NodeType, Key, Compare >::CmpLess, Aleph::COUNT(), KEY, l, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), GenTdSplayTreeRk< NodeType, Key, Compare >::root, Aleph::rotate_to_left_xt(), Aleph::rotate_to_right_xt(), sentinelCtor, and y.

Referenced by GenTdSplayTreeRk< NodeType, Key, Compare >::find_position(), GenTdSplayTreeRk< NodeType, Key, Compare >::insert(), GenTdSplayTreeRk< NodeType, Key, Compare >::insert_dup(), GenTdSplayTreeRk< NodeType, Key, Compare >::position(), GenTdSplayTreeRk< NodeType, Key, Compare >::remove(), GenTdSplayTreeRk< NodeType, Key, Compare >::search(), GenTdSplayTreeRk< NodeType, Key, Compare >::search_or_insert(), and GenTdSplayTreeRk< NodeType, Key, Compare >::splay().

◆ splay_max()

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

Node * GenTdSplayTreeRk< NodeType, Key, Compare >::splay_max ( Node * r )

inlineprivatenoexcept

Splay the maximum element to the root.

Uses the same zig-zig and zig rotations as standard splay to maintain the amortized O(log n) guarantee. Unlike splay(key), this function always brings the actual maximum to the root, which is needed for correct behavior when there are duplicate keys.

Parameters

r	root of the subtree

Returns: the new root (the maximum element)

Definition at line 348 of file tpl_splay_treeRk.H.

References Aleph::COUNT(), l, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), Aleph::rotate_to_left_xt(), sentinelCtor, and y.

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

◆ swap()

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

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

inline

Definition at line 232 of file tpl_splay_treeRk.H.

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

◆ verify()

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

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

inline

Definition at line 447 of file tpl_splay_treeRk.H.

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

Member Data Documentation

◆ cmp

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

Compare GenTdSplayTreeRk< NodeType, Key, Compare >::cmp

private

Definition at line 114 of file tpl_splay_treeRk.H.

Referenced by GenTdSplayTreeRk< NodeType, Key, Compare >::__insert(), GenTdSplayTreeRk< NodeType, Key, Compare >::key_comp(), GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl(), GenTdSplayTreeRk< NodeType, Key, Compare >::swap(), and GenTdSplayTreeRk< NodeType, Key, Compare >::verify().

◆ CmpEqual

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

constexpr signed char GenTdSplayTreeRk< NodeType, Key, Compare >::CmpEqual = 0

staticconstexprprivate

Definition at line 116 of file tpl_splay_treeRk.H.

Referenced by GenTdSplayTreeRk< NodeType, Key, Compare >::find_position(), GenTdSplayTreeRk< NodeType, Key, Compare >::insert(), GenTdSplayTreeRk< NodeType, Key, Compare >::position(), GenTdSplayTreeRk< NodeType, Key, Compare >::remove(), GenTdSplayTreeRk< NodeType, Key, Compare >::search(), GenTdSplayTreeRk< NodeType, Key, Compare >::search_or_insert(), and GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl().

◆ CmpGreater

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

constexpr signed char GenTdSplayTreeRk< NodeType, Key, Compare >::CmpGreater = 1

staticconstexprprivate

Definition at line 117 of file tpl_splay_treeRk.H.

Referenced by GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl().

◆ CmpLess

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

constexpr signed char GenTdSplayTreeRk< NodeType, Key, Compare >::CmpLess = -1

staticconstexprprivate

Definition at line 115 of file tpl_splay_treeRk.H.

Referenced by GenTdSplayTreeRk< NodeType, Key, Compare >::find_position(), and GenTdSplayTreeRk< NodeType, Key, Compare >::splay_impl().

◆ root

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

Node* GenTdSplayTreeRk< NodeType, Key, Compare >::root

private

Definition at line 113 of file tpl_splay_treeRk.H.

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

tpl_splay_treeRk.H

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ key_type

◆ Node

Constructor & Destructor Documentation

◆ GenTdSplayTreeRk()

◆ ~GenTdSplayTreeRk()

Member Function Documentation

◆ __insert()

◆ find_position()

◆ get_compare()

◆ getRoot()

◆ insert()

◆ insert_dup()

◆ is_empty()

◆ key_comp()

◆ position()

◆ remove()

◆ search()

◆ search_or_insert()

◆ select()

◆ size()

◆ splay()

◆ splay_impl()

◆ splay_max()

◆ swap()

◆ verify()

Member Data Documentation

◆ cmp

◆ CmpEqual

◆ CmpGreater

◆ CmpLess

◆ root