Simple (unbalanced) binary search tree. More...

#include <tpl_binTree.H>

Inheritance diagram for Aleph::GenBinTree< NodeType, Key, Compare >:

Classes
struct	Iterator
	Iterator on nodes of the tree. More...

Public Types
using	Node = NodeType< Key >

Public Member Functions
	GenBinTree (const GenBinTree &)=delete

GenBinTree &	operator= (const GenBinTree &)=delete

void	swap (GenBinTree &tree) noexcept
	Swap `this` with `tree` in constant time.

Compare &	key_comp () noexcept
	return the comparison criteria

Compare &	get_compare () noexcept

	GenBinTree (Compare _cmp=Compare()) noexcept
	Initialize an empty tree with comparison criteria `__cmp`

Node *	search (const Key &key) const noexcept
	Search a key.

virtual	~GenBinTree ()=default

bool	verify () const
	Return `true` if the tree is a consistent (correct) binary search tree.

Node *&	getRoot () noexcept
	Return the root of tree.

Node *	getRoot () const noexcept
	Return the root of tree.

bool	verifyBin () const

Node *	insert (Node *p) noexcept
	Insert a node in the tree.

Node *	insert_dup (Node *p) noexcept
	Insert a node in the tree.

Node *	search_or_insert (Node *p) noexcept
	Search or insert a key.

bool	split (const Key &key, GenBinTree &l, GenBinTree &r) noexcept
	Split the tree according to a key.

void	split_dup (const Key &key, GenBinTree &l, GenBinTree &r) noexcept
	Split the tree according to a key that could be in the tree.

Node *	remove (const Key &key) noexcept
	Remove a key from the tree.

void	join (GenBinTree &tree, GenBinTree &dup) noexcept
	Join `tree` with `this`.

void	join_dup (GenBinTree &t) noexcept
	Join `this` with `t` independently of the presence of duplicated keys.

void	join_exclusive (GenBinTree &t) noexcept
	Join exclusive of `this` with `t`

Static Private Member Functions
template<class Inserter >
static void	move_all (Node *&src, Inserter inserter) noexcept

Private Attributes
Node	headNode
	The node.

Node *	head

Node *&	root

Compare	cmp

Detailed Description

template<template< typename > class NodeType, typename Key, class Compare>
requires StrictWeakOrder<Compare, Key>
class Aleph::GenBinTree< NodeType, Key, Compare >

Simple (unbalanced) binary search tree.

GenBinTree implements a basic binary search tree without any balancing operations. The tree's performance depends entirely on the insertion order of keys.

Performance Characteristics:

Random insertion order + few deletions: Operations trend toward O(log n) due to probabilistic balance. This is often the best choice for simplicity when insertion order is naturally random.
Many deletions: Performance degrades to approximately O(√n) as the tree becomes less balanced over time.
Sequential insertion order: Worst case O(n) - tree degenerates into a linked list. Do not use if insertion order is not random.

When to Use:: ✓ Insertion order is random or randomized ✓ Few deletions relative to insertions ✓ Simplicity and minimal overhead are priorities ✓ Testing/benchmarking against balanced trees

When NOT to Use:: ✗ Cannot guarantee random insertion order ✗ Frequent deletions ✗ Need guaranteed O(log n) worst-case performance ✗ Production code with adversarial inputs

WARNING**: If you cannot ensure random insertion order, use a balanced tree (Avl_Tree, Rb_Tree, Treap, etc.) instead.

Template Parameters

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

Complexity (assuming random insertion order):

Search: O(log n) expected, O(n) worst case
Insert: O(log n) expected, O(n) worst case
Delete: O(log n) expected, O(n) worst case
Space: O(n) - minimal overhead

Example:: BinTree<int> tree;

// Insert in random order (GOOD)

std::vector<int> keys = {50, 25, 75, 10, 30, 60, 90};

std::shuffle(keys.begin(), keys.end(), rng);

for (int k : keys)

tree.insert(new BinTree<int>::Node(k));

// Search

auto node = tree.search(30);

// Remove

auto removed = tree.remove(25);

delete removed;

// BAD: Sequential insertion (creates linked list)

// for (int i = 0; i < 1000; ++i)

// tree.insert(new BinTree<int>::Node(i)); // O(n²) total time!

Node
WeightedDigraph::Node Node
Definition bellman_ford_example.cc:140

Aleph::GenBinTree::insert
Node * insert(Node *p) noexcept
Insert a node in the tree.
Definition tpl_binTree.H:229

Aleph::GenBinTree::search
Node * search(const Key &key) const noexcept
Search a key.
Definition tpl_binTree.H:203

Aleph::GenBinTree::remove
Node * remove(const Key &key) noexcept
Remove a key from the tree.
Definition tpl_binTree.H:303

rng
static mt19937 rng
Definition disjoint_sparse_table_test.cc:148

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

Aleph::BinTree
Binary search tree with nodes without virtual destructors,.
Definition tpl_binTree.H:381

keys
int keys[]
Definition testArrayHeap.C:34

k
static int * k
Definition testOpBinTree.C:49

Note: This is a low-level implementation managing raw nodes. For automatic memory management, use DynSetBinTree.; No balancing overhead - fastest when insertion order is favorable.; Use as a baseline for benchmarking balanced tree implementations.

See also: BinTree Convenient typedef for BinTree<Key, Compare>.; Avl_Tree Balanced alternative with O(log n) worst-case guarantee.; Treap Randomized alternative with O(log n) expected (simpler than AVL).; DynSetBinTree High-level wrapper with automatic memory management.

Definition at line 137 of file tpl_binTree.H.

Member Typedef Documentation

◆ Node

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

using Aleph::GenBinTree< NodeType, Key, Compare >::Node = NodeType<Key>

Definition at line 141 of file tpl_binTree.H.

Constructor & Destructor Documentation

◆ GenBinTree() [1/2]

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

Aleph::GenBinTree< NodeType, Key, Compare >::GenBinTree ( const GenBinTree< NodeType, Key, Compare > & )

delete

◆ GenBinTree() [2/2]

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

Aleph::GenBinTree< NodeType, Key, Compare >::GenBinTree ( Compare _cmp = Compare() )

inlinenoexcept

Initialize an empty tree with comparison criteria __cmp

Definition at line 191 of file tpl_binTree.H.

◆ ~GenBinTree()

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

virtual Aleph::GenBinTree< NodeType, Key, Compare >::~GenBinTree ( )

virtualdefault

Member Function Documentation

◆ get_compare()

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

Compare & Aleph::GenBinTree< NodeType, Key, Compare >::get_compare ( )

inlinenoexcept

Definition at line 188 of file tpl_binTree.H.

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

◆ getRoot() [1/2]

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

Node * Aleph::GenBinTree< NodeType, Key, Compare >::getRoot ( ) const

inlinenoexcept

Return the root of tree.

Definition at line 217 of file tpl_binTree.H.

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

◆ getRoot() [2/2]

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

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

inlinenoexcept

Return the root of tree.

Definition at line 214 of file tpl_binTree.H.

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

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

◆ insert()

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

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

inlinenoexcept

Insert a node in the tree.

Parameters

[in] p pointer to the node to insert

Returns: if p->get_key() is not in the tree, then the pointer p is returned (it was inserted); otherwise, nullptr is returned

Definition at line 229 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenBinTree< NodeType, Key, Compare >::root.

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

◆ insert_dup()

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

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

inlinenoexcept

Insert a node in the tree.

This method does not fail. It always inserts.

  @param[in] p pointer to the node to insert
  @return the `p` pointer

Definition at line 241 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenBinTree< NodeType, Key, Compare >::root.

◆ join()

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

void Aleph::GenBinTree< NodeType, Key, Compare >::join	(	GenBinTree< NodeType, Key, Compare > &	tree,
		GenBinTree< NodeType, Key, Compare > &	dup
	)

inlinenoexcept

Join tree with this.

Duplicated keys of tree are put in dup parameter.

  @param[in,out] tree to join with `this`
  @param[out] dup tree where the duplicated key belonging to
  `tree` are put.

Definition at line 315 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenBinTree< NodeType, Key, Compare >::move_all().

Referenced by TEST().

◆ join_dup()

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

void Aleph::GenBinTree< NodeType, Key, Compare >::join_dup ( GenBinTree< NodeType, Key, Compare > & t )

inlinenoexcept

Join this with t independently of the presence of duplicated keys.

join(t) produces a random tree result of join of this and t. The resulting tree is stored in this.

Parameters

[in] t tree to join with this keys are inserted

Definition at line 333 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenBinTree< NodeType, Key, Compare >::move_all().

Referenced by TEST().

◆ join_exclusive()

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

void Aleph::GenBinTree< NodeType, Key, Compare >::join_exclusive ( GenBinTree< NodeType, Key, Compare > & t )

inlinenoexcept

Join exclusive of this with t

Exclusive means that all the keys of this are lesser than all the keys of t. This knowledge allows a more effcient way for joining that when the keys ranks are overlapped. However, use very carefully because the algorithm does not perform any check and the result would be incorrect.

Parameters

[in] t tree to exclusively join with this keys are inserted

Definition at line 350 of file tpl_binTree.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::GenBinTree< NodeType, Key, Compare >::root.

Referenced by TEST().

◆ key_comp()

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

Aleph::GenBinTree< NodeType, Key, Compare >::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 185 of file tpl_binTree.H.

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

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

◆ move_all()

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

template<class Inserter >

static void Aleph::GenBinTree< NodeType, Key, Compare >::move_all	(	Node *&	src,
		Inserter	inserter
	)

inlinestaticprivatenoexcept

Definition at line 151 of file tpl_binTree.H.

References Aleph::divide_and_conquer_partition_dp(), l, LLINK, r, and RLINK.

Referenced by Aleph::GenBinTree< NodeType, Key, Compare >::join(), and Aleph::GenBinTree< NodeType, Key, Compare >::join_dup().

◆ operator=()

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

GenBinTree & Aleph::GenBinTree< NodeType, Key, Compare >::operator= ( const GenBinTree< NodeType, Key, Compare > & )

delete

◆ remove()

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

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

inlinenoexcept

Remove a key from the tree.

Parameters

[in] key to remove

Returns: a valid pointer to the removed node if key was found in the tree, nullptr otherwise

Definition at line 303 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenBinTree< NodeType, Key, Compare >::root.

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

◆ search()

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

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

inlinenoexcept

Search a key.

Parameters

[in] key to be searched

Returns: a pointer to the containing key if this was found; otherwise nullptr

Definition at line 203 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenBinTree< NodeType, Key, Compare >::root.

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

◆ search_or_insert()

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

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

inlinenoexcept

Search or insert a key.

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

Parameters

[in] p node containing a key to be searched and eventually inserted

Returns: if the key contained in p is found, then a pointer to the containing key in the tree is returned. Otherwise, p is inserted and returned

Definition at line 258 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenBinTree< NodeType, Key, Compare >::root.

Referenced by TEST().

◆ split()

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

bool Aleph::GenBinTree< NodeType, Key, Compare >::split	(	const Key &	key,
		GenBinTree< NodeType, Key, Compare > &	l,
		GenBinTree< NodeType, Key, Compare > &	r
	)

inlinenoexcept

Split the tree according to a key.

split(key, l, r) splits the tree according to key. That is, if key is not present in the tree, then the tree is split in two trees l which contains the key lesser than key and r which contains the keys greater than key. If key is found in the tree, then the split is not done

Parameters

[in]	key	for splitting
[out]	l	resulting tree with the keys lesser than `key`
[out]	r	resulting tree with the keys greater than `key`

Returns: true if the tree was split. false otherwise

Definition at line 276 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), l, r, Aleph::GenBinTree< NodeType, Key, Compare >::root, and Aleph::split_key_rec().

Referenced by TEST(), and TEST().

◆ split_dup()

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

void Aleph::GenBinTree< NodeType, Key, Compare >::split_dup	(	const Key &	key,
		GenBinTree< NodeType, Key, Compare > &	l,
		GenBinTree< NodeType, Key, Compare > &	r
	)

inlinenoexcept

Split the tree according to a key that could be in the tree.

split_dup(key, l, r) splits the tree according to key in two trees l which contains the key lesser than key and r which contains the keys greater or equal than key.

Parameters

[in]	key	for splitting
[out]	l	resulting tree with the keys lesser than `key`
[out]	r	resulting tree with the keys greater or equal than `key`

Definition at line 292 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), l, r, and Aleph::GenBinTree< NodeType, Key, Compare >::root.

Referenced by TEST().

◆ swap()

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

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

inlinenoexcept

Swap this with tree in constant time.

Definition at line 178 of file tpl_binTree.H.

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

Referenced by TEST().

◆ verify()

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

Aleph::GenBinTree< NodeType, Key, Compare >::verify ( ) const

inline

Return true if the tree is a consistent (correct) binary search tree.

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 211 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenBinTree< NodeType, Key, Compare >::root.

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

◆ verifyBin()

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

bool Aleph::GenBinTree< NodeType, Key, Compare >::verifyBin ( ) const

inline

Definition at line 220 of file tpl_binTree.H.

References Aleph::GenBinTree< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenBinTree< NodeType, Key, Compare >::root.

Referenced by main().

Member Data Documentation

◆ cmp

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

Compare Aleph::GenBinTree< NodeType, Key, Compare >::cmp

private

Definition at line 148 of file tpl_binTree.H.

◆ head

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

Node* Aleph::GenBinTree< NodeType, Key, Compare >::head

private

Definition at line 146 of file tpl_binTree.H.

◆ headNode

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

Node Aleph::GenBinTree< NodeType, Key, Compare >::headNode

private

The node.

Definition at line 145 of file tpl_binTree.H.

◆ root

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

Node*& Aleph::GenBinTree< NodeType, Key, Compare >::root

private

Definition at line 147 of file tpl_binTree.H.

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

tpl_binTree.H

Classes

Public Types

Public Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Node

Constructor & Destructor Documentation

◆ GenBinTree() [1/2]

◆ GenBinTree() [2/2]

◆ ~GenBinTree()

Member Function Documentation

◆ get_compare()

◆ getRoot() [1/2]

◆ getRoot() [2/2]

◆ insert()

◆ insert_dup()

◆ join()

◆ join_dup()

◆ join_exclusive()

◆ key_comp()

◆ move_all()

◆ operator=()

◆ remove()

◆ search()

◆ search_or_insert()

◆ split()

◆ split_dup()

◆ swap()

◆ verify()

◆ verifyBin()

Member Data Documentation

◆ cmp

◆ head

◆ headNode

◆ root