This is an implementation of a Red-Black Tree provided as a single include "library".

As this is a CMake project, installation should be as easy as putting this directory into your project tree and adding a single line

add_subdirectory(<path-to>/redblacktree)

Finally, to be able to include the data structure in your sources, you need to add the library to the correct target in your cmake project.

target_link_libraries(<your-project> RedBlackTree)

All that is necessary to have full access to all functionality is this line:

#include <RedBlackTree.h>

This header contains the full implementation of the data structure. The public interface looks like this:

template <typename T>
class RedBlackTree
{
public:
	         RedBlackTree ();

	bool     Insert       (const T& item);
	bool     Delete       (const T& item);
	bool     DeleteAt     (size_t index);
	void     Clear        ();

	std::pair<size_t, std::reference_wrapper<const T>> Find (const T& item) const;
	const T& At           (size_t index)  const;
	bool     Contains     (const T& item) const;

	bool     Empty        () const;
	size_t   Size         () const;
};

Adds an element to the tree, if there already is one, the insertion is ignored. Returns true if item was inserted and false otherwise.

Deleted the element from the data structure, provided it is contained within. Returns true if item was deleted and false otherwise.

Deletes the k-th element from the data-structure, provided it is in bounds. Returns true if item was inserted and false otherwise.

Completely empties the data structure.

Tries to find the specified element. Returns a pair of an index and a const & to it. If the item isn't contained, returns the max value of size_t and a reference to a default constructed item.

Returns the element contained at the provided index, or the default value, if the index is out of bounds.

Returns true if the element is contained, or false if it isn't.

Returns true if the tree is empty.

Returns the count of the elements contained in the tree.

There are also some tools provided for debugging. They can be enabled with these flags:

Gives access to the FORCE_CHECKS() macro, which executes consistency checks on the tree provided as parameter. In case it's necessary to check either only invariant consistency or internal data consistency, those checks are available as these functions:

bool ForceCheckInvariants(const RedBlackTree<T>& tree);
bool ForceCheckContent(const RedBlackTree<T>& tree);

Gives access to the DumpTreeToFile(filename, tree) function, which serializes the tree into a format which can be visualized with e.g. https://dreampuf.github.io/GraphvizOnline/

There are a few more flags, which are not recommended for use, either because they slow the program down way too much, or because they are not completely finished.