tpl_tdRbTree.H File Reference

Top-down Red-Black tree implementation. More...

#include <functional>
#include <tpl_binNode.H>
#include <tpl_binNodeUtils.H>
#include <tpl_arrayStack.H>
#include <rbNode.H>

Include dependency graph for tpl_tdRbTree.H:

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

Go to the source code of this file.

Classes
class	Aleph::GenTdRbTree< NodeType, Key, Compare >
	Top-down red-black binary search tree implementation. More...
struct	Aleph::GenTdRbTree< NodeType, Key, Compare >::Iterator
	Iterator over tree nodes in sorted order. More...
class	Aleph::TdRbTree< Key, Compare >
	Top-down red-black tree without virtual destructor. More...
class	Aleph::TdRbTreeVtl< Key, Compare >
	Top-down red-black tree with virtual destructor. More...

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

Detailed Description

Top-down Red-Black tree implementation.

Red-Black tree with top-down single-pass insertion. Simpler code path than bottom-up variant.

Features

• Single pass from root to leaf
• No parent pointers needed
• Color flips during descent

Complexity: O(log n) for all operations

See also

tpl_rb_tree.H Bottom-up variant

tpl_tdRbTreeRk.H With rank support

Author

Leandro Rabindranath León

Definition in file tpl_tdRbTree.H.