O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required