RTL_RB_TREE

The RTL_RB_TREE structure has pointers to the root node and left-most node of a Red-Black Tree.

Availability

The RTL_RB_TREE structure looks to have been introduced for version 6.2 in both the kernel and NTDLL.DLL. As many as three exported functions work specifically with the RTL_RB_TREE:

• RtlRbInsertNodeEx;
• RtlRbRemoveNode;
• RtlRbReplaceNode (10.0 and higher, kernel only).

From public symbol files it is also knowable that Microsoft has an inline routine RtlRbInitialize whose whole work is of course to initialise an RTL_RB_TREE. There are also inline routines that work with nodes in Red-Black trees, but which work also for AVL trees: RtlTreeDelete; RtlTreeFindInsertLocation; RtlTreeFindFirstNode; and RtlTreeFindFirstMatchingNode.

Documentation Status

The RTL_RB_TREE structure is not documented.

Layout

The RTL_RB_TREE is 0x08 and 0x10 bytes, respectively, in 32-bit and 64-bit Windows.

RTL_BALANCED_NODE *Root;

RTL_BALANCED_NODE *Min;

Nodes are ordered in the tree according to some abstract key. The Root is a starting point for searching the tree, moving left or right at successive nodes according to whether the desired node has a lower or higher key. The Min is a starting point for enumerating the tree in increasing order of the key.