A **red-black tree** (aka RBT) is a type of self-balancing Binary Search Tree using an
ingenious algorithm for balancing too complex to be described here (search on Wiki for more info), so complex in fact that all implementations, regardless of
programming language, just transliterate recipes from "the Holy Book of Algorithms", Introduction to Algorithms by Thomas Cormen, Charles Leiserson & Ronald Rivest.
Each edition comes with a different implementation: STL@C++ & Collections API@Java uses RBT recipes from 2nd edition, this API uses RBT recipes from 3rd edition.

As any Binary Search Tree, red-black tree comes with one special requirement from developers that use it:

- a
*comparator function*able to compare two nodes (left and right) in tree based on value they hold. This function should return a signed number:- a negative value, if value held by left node is smaller than that of right node
- zero, if if value held by left node equals that of right node
- a positive value, if value held by left node is greater than that of right node

Apart of implementing operations required by Tree abstract data type, following operations are added by red-black tree:

Operation |
Arguments |
Returns |
Description |

getNodeValue | DATA | DATA | Gets value in red-black tree matching that of input |

insertNode | DATA | void | Adds node to red-black tree by value or modifies it if found already. |

hasNode | DATA | boolean | Checks if red-black tree contains node by value. |

hasMatches | DATA, COMPARATOR | boolean | Checks if red-black tree contains node by value and special comparator. |

deleteNode | DATA | Removes node from red-black tree by value. | |

deleteMatches | DATA, COMPARATOR | Removes node from red-black tree by value and special comparator. | |

getNextNode | NODE | NODE | Gets next node in red-black tree after input node for iteration. |

And a NODE whose coordinates are:

*data*: value node holds (requirement of any Tree)*left*: left smaller descendant or null (requirement of Binary Search Tree)*right*: right greater/equal descendant or null (requirement of Binary Search Tree)*parent*: direct ancestor or null (requirement of Red-Black Tree algorithm)*color*: can be RED or BLACK (requirement of Red-Black Tree algorithm)

Just by seeing how much information is required in NODE, one understands that, whenever used, Red-Black Tree comes with significant memory consumption and performance loss by having to maintain so many coordinates in order to fulfil its goals as a self-balancing Binary Search Tree. It is many times slower and more memory hungry than a Hash Table, so why use it after all?

Despite its recognized problems, Red-Black Tree is widely used by data structures whose requirements are to keep data inside self-sorted on insertions/deletions and predictably iterated. Let us take its Associative Array implementation as an example to understand how it works:

Operation |
Description |

clear | Loops through all NODES and deallocates them. |

containsKey | Runs hasNode RBT method. navigating from ROOT node and recursing among descendants until a NODE key matches via comparator function. |

containsValue | Runs hasMatches RBT method, looping through all NODES until a NODE value matches via custom COMPARATOR |

get | Runs getNodeValue RBT method, navigating from ROOT node and recursing among descendants until a NODE key matches via comparator function then returns matching NODE value. |

set | Runs insertNode RBT method, navigating from ROOT node and recursing among descendants until a NODE key matches via comparator function. If found, it changes matching NODE value, otherwise a new NODE is added to tree, also incrementing SIZE.Then, in order to stay self-sorted, it needs to partially rebalance the tree according to value of NODE key, which will in turn set the new left/right/parent coordinates. |

removeKey | Runs deleteNode RBT method, navigating from ROOT node and recursing among descendants until a NODE key matches via comparator function. If found, it deletes NODE, also decrementing SIZE.Then, in order to remain balanced and keep depth minimal, it must partially rebalance the tree. |

removeValue | Runs deleteMatches RBT method, looping through all NODES and deleting all those whose value matches via custom COMPARATOR, also decrementing SIZE.Then, in order to remain balanced and keep depth minimal, it must partially rebalance the tree. |

isEmpty | Runs getSize RBT method and checks if SIZE returned equals zero |

size | Runs getSize RBT method and returns value of SIZE (number of nodes in tree) |