PreviousUpNext

Red-Black Trees

There are many flavors of balanced binary tree. In general they are largely interchangeable; the particular choice of tree seldom makes much difference.

The Mythryl codebase has settled on the Red-Black tree as its standard flavor of balanced binary tree. It contains a number of standard Red-Black tree implementations specialized to various needs, including:

The codebase also provides two generic packages which may be used to generate your own specialized Red-Black tree variants:

More specialized Red-Black tree implementations include:

You do not need to understand the internals of these tree variants, but you will find it useful to know how to use the most common ones.

The Mythryl tree variants need to know how to compare their keys in order to keep the tree ordered, but they don’t need to know anything about the values they are storing because they never do anything with them except accept and return them. Consequently these trees are in general typeagnostic in their values but specialized to work with only one type of key.


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext