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

Almost balanced trees

In the tree we just saw, every node's left and right subtrees are of the same height. This makes it a tree that is perfectly height-balanced. However, such trees are very rare; we come across them only when we have large trees with thousands of nodes.

Instead, we could try for trees that are either perfectly height-balanced or somewhere close to that. What do we mean by height-balanced? If the heights of any nodes, left or right subtrees, differ by at most 1, it is a height-balanced tree. The complexities of various operations would be almost the same as for a perfectly balanced tree.

Almost balanced trees

In the preceding diagram, the left tree ...

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