Data Structures: Red Black Trees

What is a Red-Black Tree?

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:

What are the operations it requires?

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:

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?

When to use Red-Black Tree?

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)

Share