The red-black tree and hash table

red-black tree

The even more advanced container we look at now is the red-black tree, which is a type of self-balancing binary search tree. Especially, interesting is the time complexity in big O notation:

Action/Subject       Average          Worst case
Space                          O(n)                O(n)
Search                        O(log n)         O(log n)
Insert                          O(log n)         O(log n)
Delete                         O(log n)         O(log n)

Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as real-time applications, but it makes them valuable building blocks in other data structures which provide worst-case guarantees.

The above statement should ring a bell for embedded software engineers that need manipulations on data sets in a time-deterministic and predictable manner. If a simple array (vector) or linked list does not handle it, consider the red-black tree instead of a simple binary tree which could become unbalanced. If however, the data is known beforehand (and constant), one could balance the tree at build time and do lookups with simpler and smaller code. Do not implement red-black trees yourself but use an existing robust and debugged implementation such as the one found in kazlib.

The “Home of Kazlib” has more data container goodies:
It has implementations for linked lists, red-black trees and hashes.

Hash tables

A hash table is a data structure that allows one to store – and find again – items at a particular memory space or “bucket”. The hash table uses a function to calculate an index which points at a specific “bucket”. In this bucket, we can find the element associated with the key we are searching for. If there are multiple elements in the visited bucket, we need to test all these elements in order to find the correct one.

So, in general, the efficiency of a hash table depends on

• the number of buckets,
• the number of elements in the hash table,
• and the distribution of these elements across the different buckets.
• the computing efficiency of the hashing function

There exist various kinds of different hash table variants using different hash functions and conflict resolve methods (when 2 or more elements land in the same bucket).

When to use

On larger datasets, the hash table approach is usually more efficient than the red black tree but again depending on the efficiency of the hash table (more – possibly empty – buckets means more memory usage/waste) and the calculation (and distribution) efficiency of the hash function itself on the embedded target. As always, the trade-off is memory versus speed.