treapNode.H File Reference

Treap node definition with BST key and heap priority. More...

#include <limits.h>
#include <tpl_binNode.H>

Include dependency graph for treapNode.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::TreapNode_Data
	Data portion of a treap node. More...
class	Aleph::TreapNode< Key >
	Declare TreapNode type with 80-byte pool allocation. More...
class	Aleph::TreapNodeVtl< Key >

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<class Node >
unsigned long &	Aleph::PRIO (Node *p) noexcept
	Access the priority of a treap node.
template<class Node >
bool	Aleph::is_treap (Node *root) noexcept
	Validate that a tree satisfies treap (heap) property.

Variables
const long	Aleph::Max_Priority = ULONG_MAX
	Maximum priority value (used for sentinel/leaves)
const long	Aleph::Min_Priority = 0
	Minimum priority value.

Detailed Description

Treap node definition with BST key and heap priority.

This file defines the TreapNode structure for treaps - a randomized data structure combining binary search tree and heap properties.

Treap Properties

A treap maintains two invariants simultaneously:

1. BST property: Left descendants < node < right descendants (keys)
2. Min-heap property: Parent priority ≤ child priorities

The random priorities ensure expected O(log n) height regardless of insertion order.

Why Treaps?

Feature	Treap	AVL/RB
Balance	Probabilistic	Guaranteed
Code complexity	Simple	Complex
Expected height	1.99 log n	1.44 log n
Worst case	O(n) unlikely	O(log n)

See also

tpl_treap.H Treap implementation

tpl_rand_tree.H Randomized BST

Author

Leandro Rabindranath León

Definition in file treapNode.H.