What is a red black tree?
A red black tree is a self-balancing binary tree that provides scalable (logarithmic) performance for adding, removing, and finding an object.
What is the purpose of a red black tree?
A red black tree implements an associative array, which is similar to C++'s std::map, C#'s Dictionary, Java's java.util.Map, Python's [] dictionary, Lua's [] table, and JavaScript's {} Object.
What are the specifications of this red black tree?
- Every algorithm is iterative.
- Each node is 32 bytes in size.
- Each tree is static in size.
- Nodes are stored in an array.
- Nodes are referenced by index.
- NIL is represented by zero.
Why are the nodes stored in an array and reference by index?
To allow the node array to be stored and shared in a memory-mapped file.