FHQ Treap: A Non-Rotating Balanced Binary Tree Implementation
Data Structure DefinitionThe FHQ Treap (Fredman, Hendler, and Zhou Treap) relies on a randomized heap priority to maintain balance without requiring complex tree rotations. Each node in the structure maintains essential metadata: pointers to left and right children, the node's value, a random priority weight, and the size of the subtree rooted ...
Posted on Wed, 17 Jun 2026 17:45:38 +0000 by Backara_Drift
Competitive Programming Template Collection
Tarjan's Algorithm for Strongly Connnected Components
namespace TarjanSCC {
int dfn[N], low[N], index, colorCount;
int comp[N], size[N], value[N];
bool inStack[N];
stack<int> stk;
vector<int> graph[N];
void tarjan(int u) {
dfn[u] = low[u] = ++index;
stk.push(u);
inStack[u] = true;
...
Posted on Tue, 02 Jun 2026 18:01:50 +0000 by justgrafx
Implementing Balanced Trees: Rotational vs Non-rotational Treaps
P6136 Enhanced Balanced Tree Template
After struggling with rotational Treaps, I've concluded they're overly complex. FHQ Treaps offer a much cleaner implementation, with roughly half the code size.
Rotational Treap Implementation
Structure and data definitions:
const int INF=1e18;
struct TreeNode {
int left, right;
int value, priority; ...
Posted on Sun, 10 May 2026 18:15:42 +0000 by spaceknop