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

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.