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

Summary

We saw how a simple BST could degenerate into a linked list, for example, when we insert sorted data into the tree. In this case, instead of logarithmic lookup complexity, we should get a far slower, O(n) runtime complexity.

To make sure that the tree operations are logarithmic, we need to balance the tree. We learned about perfectly balanced trees, which are rare. Instead, height-balanced trees, which are almost balanced are good for us.

We touched upon some terms such as height of a node and internal nodes. Next, we looked at tree rotations, which are the basic building blocks for rebalancing a tree.

Red-Black trees are balanced BSTs, with every node colored in either red or black. There are two important invariants that need to be maintained. ...

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