Top-down splay tree - Self-adjusting BST with amortized O(log n) operations. More...

#include <tpl_splay_tree.H>

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

Classes
struct	Iterator
	Iterator over the nodes. More...

Public Types
using	Node = NodeType< Key >

using	key_type = Key
	The key type stored in the node.

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

Compare &	get_compare () noexcept

void	splay (const Key &key) noexcept
	search key within tree and splay that node, if not found it return Node::NullPtr

	GenTdSplayTree (Compare __cmp=Compare()) noexcept
	Constructor.

void	swap (GenTdSplayTree &tree) noexcept

virtual	~GenTdSplayTree ()=default
	Destructor.

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

Node *	insert_dup (Node *p) noexcept

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

Node *	search_or_insert (Node *p) noexcept

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

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

bool	verify () const

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

Node *	__insert (Node *p) noexcept

Private Attributes
Node	headnode

Node *	head

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>
requires StrictWeakOrder<Compare, Key>
class GenTdSplayTree< NodeType, Key, Compare >

Top-down splay tree - Self-adjusting BST with amortized O(log n) operations.

GenTdSplayTree implements a splay tree, a self-adjusting binary search tree where every access operation (search, insert, delete) moves the accessed node to the root through a sequence of tree rotations called "splaying".

Key Characteristics:

Self-adjusting: Frequently accessed items migrate toward the root
Amortized O(log n): While individual operations may be O(n), sequences of m operations take O(m log n) time total
Cache-friendly: Recent accesses stay near the root for fast re-access
Simple implementation: No balance information or color bits needed
No worst-case guarantee: Individual operations can be O(n)

Splaying Rotations:

Zig: Single rotation when node is child of root
Zig-zig: Two rotations in same direction (child and parent on same side)
Zig-zag: Two rotations in opposite directions (child and parent on different sides)

These rotations ensure amortized efficiency by reducing tree depth.

When to Use Splay Trees:: ✓ Access patterns have locality (same items accessed repeatedly) ✓ Amortized complexity is acceptable (no hard real-time constraints) ✓ Simplicity preferred over guaranteed worst-case performance ✓ Cache performance is critical

When NOT to Use:: ✗ Need guaranteed O(log n) worst-case (use AVL or Red-Black instead) ✗ Hard real-time requirements ✗ Uniform random access patterns (no locality benefit)

Template Parameters

NodeType	Node template (BinNode or BinNodeVtl).
Key	The type of keys stored in the tree.
Compare	Comparison functor for ordering keys.

Complexity:

Search: O(log n) amortized
Insert: O(log n) amortized
Delete: O(log n) amortized
Individual operation worst case: O(n)
Space: O(n) - no extra balance information needed

Example:: Splay_Tree<int> tree;

// Insert nodes

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

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

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

// Search (splays node to root)

auto node = tree.search(42);

if (node != nullptr)

std::cout << "Found and splayed to root: " << node->get_key() << '\n';

// Subsequent access to 42 is now O(1)

node = tree.search(42); // Very fast - already at root

// Remove (splays then removes root)

auto removed = tree.remove(42);

delete removed;

GenTdSplayTree::Node
NodeType< Key > Node
Definition tpl_splay_tree.H:139

GenTdSplayTree::remove
Node * remove(const Key &key) noexcept
Remove a key from a top down splay tree.
Definition tpl_splay_tree.H:343

GenTdSplayTree::insert
Node * insert(Node *p) noexcept
Inserts a node in a top-down splay tree.
Definition tpl_splay_tree.H:271

GenTdSplayTree::search
Node * search(const Key &key) noexcept
Searches a key in a top-down splay tree.
Definition tpl_splay_tree.H:311

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Splay_Tree
Definition tpl_splay_tree.H:396

Note: This implementation does NOT support rank operations. For indexed access, use Splay_Tree_Rk instead.; Based on Danny Sleator's top-down splay tree implementation.; This is a low-level implementation managing raw nodes. For automatic memory management, use DynSetSplayTree.

See also: Splay_Tree Convenient typedef for Splay_Tree<Key, Compare>.; Splay_Tree_Rk Splay tree variant with rank support.; Avl_Tree Alternative with O(log n) worst-case guarantee.; DynSetSplayTree High-level wrapper with automatic memory management.

Author: Leandro Rabindranath León

Definition at line 136 of file tpl_splay_tree.H.

Member Typedef Documentation

◆ key_type

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

using GenTdSplayTree< NodeType, Key, Compare >::key_type = Key

The key type stored in the node.

Definition at line 213 of file tpl_splay_tree.H.

◆ Node

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

using GenTdSplayTree< NodeType, Key, Compare >::Node = NodeType<Key>

Definition at line 139 of file tpl_splay_tree.H.

Constructor & Destructor Documentation

◆ GenTdSplayTree()

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

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

inlinenoexcept

Constructor.

Definition at line 229 of file tpl_splay_tree.H.

◆ ~GenTdSplayTree()

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

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

virtualdefault

Destructor.

Member Function Documentation

◆ __insert()

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

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

inlineprivatenoexcept

Definition at line 245 of file tpl_splay_tree.H.

References GenTdSplayTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, RLINK, and GenTdSplayTree< NodeType, Key, Compare >::root.

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

◆ get_compare()

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

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

inlinenoexcept

Definition at line 219 of file tpl_splay_tree.H.

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

◆ getRoot()

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

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

inlinenoexcept

Get the top-down splay tree's root.

Definition at line 370 of file tpl_splay_tree.H.

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

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

◆ insert()

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

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

inlinenoexcept

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 271 of file tpl_splay_tree.H.

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

Referenced by main(), and write_splay().

◆ insert_dup()

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

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

inlinenoexcept

Definition at line 290 of file tpl_splay_tree.H.

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

◆ key_comp()

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

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

inlinenoexcept

Returns 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 216 of file tpl_splay_tree.H.

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

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

◆ remove()

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

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

inlinenoexcept

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 343 of file tpl_splay_tree.H.

References GenTdSplayTree< NodeType, Key, Compare >::CmpEqual, Aleph::divide_and_conquer_partition_dp(), LLINK, RLINK, GenTdSplayTree< NodeType, Key, Compare >::root, and GenTdSplayTree< NodeType, Key, Compare >::splay_impl().

Referenced by main(), and TEST().

◆ search()

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

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

inlinenoexcept

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 311 of file tpl_splay_tree.H.

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

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

◆ search_or_insert()

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

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

inlinenoexcept

Definition at line 321 of file tpl_splay_tree.H.

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

◆ splay()

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

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

inlinenoexcept

search key within tree and splay that node, if not found it return Node::NullPtr

Definition at line 223 of file tpl_splay_tree.H.

References Aleph::divide_and_conquer_partition_dp(), and GenTdSplayTree< NodeType, Key, Compare >::splay_impl().

◆ splay_impl()

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

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

inlineprivatenoexcept

◆ swap()

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

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

inlinenoexcept

Definition at line 235 of file tpl_splay_tree.H.

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

◆ verify()

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

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

inline

Definition at line 375 of file tpl_splay_tree.H.

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

Referenced by TEST().

Member Data Documentation

◆ cmp

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

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

private

Definition at line 144 of file tpl_splay_tree.H.

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

◆ CmpEqual

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

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

staticconstexprprivate

Definition at line 146 of file tpl_splay_tree.H.

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

◆ CmpGreater

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

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

staticconstexprprivate

Definition at line 147 of file tpl_splay_tree.H.

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

◆ CmpLess

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

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

staticconstexprprivate

Definition at line 145 of file tpl_splay_tree.H.

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

◆ head

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

Node* GenTdSplayTree< NodeType, Key, Compare >::head

private

Definition at line 143 of file tpl_splay_tree.H.

◆ headnode

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

Node GenTdSplayTree< NodeType, Key, Compare >::headnode

private

Definition at line 142 of file tpl_splay_tree.H.

◆ root

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

Node *& GenTdSplayTree< NodeType, Key, Compare >::root

private

Definition at line 143 of file tpl_splay_tree.H.

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

tpl_splay_tree.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

◆ GenTdSplayTree()

◆ ~GenTdSplayTree()

Member Function Documentation

◆ __insert()

◆ get_compare()

◆ getRoot()

◆ insert()

◆ insert_dup()

◆ key_comp()

◆ remove()

◆ search()

◆ search_or_insert()

◆ splay()

◆ splay_impl()

◆ swap()

◆ verify()

Member Data Documentation

◆ cmp

◆ CmpEqual

◆ CmpGreater

◆ CmpLess

◆ head

◆ headnode

◆ root