tpl_hRbTreeRk.H File Reference

Hybrid top-down/bottom-up red-black tree with rank support. More...

#include <stdexcept>
#include <ah-errors.H>
#include <tpl_binNode.H>
#include <tpl_binNodeUtils.H>
#include <tpl_binNodeXt.H>
#include <tpl_binTreeOps.H>
#include <tpl_arrayStack.H>
#include <rbNodeRk.H>

Include dependency graph for tpl_hRbTreeRk.H:

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

Go to the source code of this file.

Classes
class	Aleph::HtdRbTreeRk< Key, Compare >
	Hybrid top-down/bottom-up red-black tree with rank support. More...
struct	Aleph::HtdRbTreeRk< Key, Compare >::Iterator
	In-order iterator. More...
class	Aleph::HtdRbTreeRkVtl< Key, Compare >
	Hybrid RB tree with rank and virtual destructor. More...

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

Detailed Description

Hybrid top-down/bottom-up red-black tree with rank support.

This file implements a red-black tree that uses:

• Top-down insertion with proactive color flipping
• Bottom-up deletion with stack-based ancestor tracking
• Subtree size counts for O(log n) rank operations

This hybrid approach achieves O(log n) for ALL operations including insert, remove, search, select, and position.

Definition in file tpl_hRbTreeRk.H.