Complexity
What is the runtime complexity of node insertion? A Red-Black tree of n internal nodes has height at 2*log(n+1).
This means that operations, such as searching for a node, have logarithmic time. The insertion operation we just saw is also proportional to the height of the tree.
When we insert a new node and violate the second invariant, we fix it and always color the subtree's root red. This could create further invariant violation upward in the tree.
However, as the height is at most 2*log(n+1), the insertion operation has a runtime complexity of O(logn). So, for example, for a tree with 4294967296 nodes, which is 232, we have to perform up to 32 invariant fixes. This is a very good number, making Red-Black trees one of the most popular ...
Get Learning Functional Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
