tpl_rb_tree.H File Reference

Red-Black tree implementation (bottom-up balancing). More...

#include <ahFunction.H>
#include <tpl_arrayStack.H>
#include <tpl_binNodeUtils.H>
#include <rbNode.H>

Include dependency graph for tpl_rb_tree.H:

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

Go to the source code of this file.

Classes
class	Aleph::Gen_Rb_Tree< NodeType, Key, Compare >
	Red-black binary search tree implementation (bottom-up). More...
struct	Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::Iterator
	Iterator over tree nodes in sorted order. More...
struct	Aleph::Rb_Tree< Key, Compare >
	Red-black tree with nodes without virtual destructor. More...
struct	Aleph::Rb_Tree_Vtl< Key, Compare >
	Red-black tree with virtual destructor in nodes. More...

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

Detailed Description

Red-Black tree implementation (bottom-up balancing).

Self-balancing BST with color constraints ensuring O(log n) height. Uses bottom-up insertion with post-insertion rebalancing.

Properties

• Every node is red or black
• Root is black
• No two adjacent red nodes
• All paths have same black-height

Complexity: O(log n) for all operations

See also

tpl_tdRbTree.H Top-down variant

tpl_rbRk.H With rank support

Author

Leandro Rabindranath León

Definition in file tpl_rb_tree.H.