rbNode.H File Reference

Red-Black tree node definition and validation utilities. More...

#include <tpl_binNode.H>

Include dependency graph for rbNode.H:

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

Go to the source code of this file.

Classes
class	RbNode_Data
	Data portion of a Red-Black tree node. More...
class	RbNode< Key >
	Declare RbNode type with 128-byte pool allocation. More...
class	RbNodeVtl< Key >

Macros
#define	COLOR(p)   ((p)->getColor())
	Access the color of node p.
#define	RED   (0)
	Red color constant (newly inserted nodes are red)
#define	BLACK   (1)
	Black color constant.

Typedefs
typedef unsigned char	Color
	Color type for RB nodes.

Functions
template<class Node >
bool	test_black_condition (Node *p, int &max, int bh=0)
	Test the black-height property of an RB tree.
template<class Node >
bool	is_red_black (Node *node)
	Test all Red-Black tree properties for a node.
template<class Node >
bool	is_red_black_tree (Node *node)
	Test RB properties for entire subtree.
template<class Node , class Compare >
bool	is_red_black_bst (Node *node, Compare &cmp)
	Verify that tree is both a valid RB tree and valid BST.

Detailed Description

Red-Black tree node definition and validation utilities.

This file defines the RbNode structure for Red-Black trees, including the color attribute (RED or BLACK) and functions to validate RB tree properties.

Red-Black Tree Properties

1. Every node is either red or black
2. The root is black
3. All leaves (NIL) are black
4. Red nodes have only black children
5. All paths from a node to leaves have same black height

Validation Functions

• is_red_black(): Tests all RB properties
• test_black_condition(): Verifies black-height property
• is_red_black_bst(): Verifies RB + BST ordering

See also

tpl_rb_tree.H Bottom-up Red-Black tree

tpl_tdRbTree.H Top-down Red-Black tree

Author

Leandro Rabindranath León

Definition in file rbNode.H.

Macro Definition Documentation

BLACK

#define BLACK   (1)

Black color constant.

Definition at line 76 of file rbNode.H.

COLOR

#define COLOR

(

p

)

((p)->getColor())

Access the color of node p.

Definition at line 70 of file rbNode.H.

RED

#define RED   (0)

Red color constant (newly inserted nodes are red)

Definition at line 73 of file rbNode.H.

Typedef Documentation

Color

typedef unsigned char Color

Color type for RB nodes.

Definition at line 67 of file rbNode.H.

Function Documentation

is_red_black()

template<class Node >

bool is_red_black

(

Node *

node

)

Test all Red-Black tree properties for a node.

Validates that:

• Node color is valid (RED or BLACK)
• Red nodes don't have red children
• Black-height is consistent across all paths

Template Parameters

Node	RB node type

Parameters

node	Node to test

Returns

true if all RB properties are satisfied

Definition at line 157 of file rbNode.H.

References BLACK, COLOR, max(), RED, and test_black_condition().

Referenced by is_red_black_tree().

is_red_black_bst()

template<class Node , class Compare >

bool is_red_black_bst	(	Node *	node,
		Compare &	cmp
	)

Verify that tree is both a valid RB tree and valid BST.

Combines RB property validation with BST ordering validation.

Template Parameters

Node	RB node type
Compare	Comparison functor for keys

Parameters

node	Root of tree to validate
cmp	Comparison function object

Returns

true if tree is a valid RB-BST

Definition at line 208 of file rbNode.H.

References cmp(), and is_red_black_tree().

Referenced by Aleph::HtdRbTree< Key, Compare >::verify(), and Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::verify().

is_red_black_tree()

template<class Node >

bool is_red_black_tree

(

Node *

node

)

Test RB properties for entire subtree.

Recursively validates RB properties for node and all descendants.

Template Parameters

Node	RB node type

Parameters

node	Root of subtree to test

Returns

true if entire subtree is a valid RB tree

Definition at line 185 of file rbNode.H.

References is_red_black().

Referenced by is_red_black_bst().

test_black_condition()

template<class Node >

bool test_black_condition	(	Node *	p,
		int &	max,
		int	bh = 0
	)

Test the black-height property of an RB tree.

Verifies that all paths from node p to leaves have the same number of black nodes (black-height).

Template Parameters

Node	RB node type

Parameters

p	Root of subtree to test
max	Reference to store/compare black heights (-1 initially)
bh	Current black height along this path (default 0)

Returns

true if all leaf paths have equal black height

Definition at line 124 of file rbNode.H.

References BLACK, COLOR, max(), and test_black_condition().

Referenced by is_red_black(), and test_black_condition().