The Efficiency of Red-Black Trees

Because a red-black tree is a type of binary search tree, the search operation is O(log N), as is true for all BSTs. As I discussed in Volume 1, Chapter 15, this is because there are log N levels in a BST, and at most, we will search one node from each level in the BST until we find the value we’re searching for. I also discussed there that insertion for a regular BST is O(log N), as we must first perform a search to find the appropriate spot to insert the new node, and the actual insertion is one step.

It turns out that insertion in a red-black tree is also O(log N). Now, there are certainly more steps involved with insertion into a red-black tree than there are with a regular BST. However, it’ll add up to roughly 2*log N steps at most. Here’s why.

You learned that there are two phases for insertion into a red-black tree: insertion and fixing. The insertion phase is identical to insertion in a BST, which takes log N steps. The fixing phase starts with the newly inserted node and works its way up the tree, performing color flips and rotations. Just as we took log N steps to get from the top of the tree to the bottom of the tree, it takes at most another log N steps to move from the bottom of the tree back up to the top of the tree.

In total, this is 2*log N steps, which boils down to O(log N).

It turns out that red-black trees are a win-win. They maintain the tree’s balance while keeping its operations swift and efficient.