This is a VBA implementation of a red–black tree. We support insertion only.

The nodes are kept in an array. RedBlackInsert inserts a prepared node into the tree at a given location. RedBlackFindPosition searches for a node in the tree; if the node does not exist in the tree, it provides the location at which the node would have to be inserted.

The implementation is meant to serve as a template, which can be customized by adjusting the NodeTypeTemplate type and replacing the call to RedBlackComparatorTemplate in RedBlackFindPosition by an appropriate comparison. For an example on how to use the code, have a look at the subroutine RunTest in test/RedBlackTreeTest.bas.

An explanation of the algorithm can be found on Wikipedia and Wikibooks. The variable names we use are similar to the ones used in the code examples there.