Functional and Concurrent Programming: Core Concepts and Features

Chapter 8

Case Study: Binary Search Trees

Ordered mappings can be implemented as binary search trees. In this case study, trees are immutable, and values are added or removed by building new trees. Trees are recursive—the children of a tree are themselves trees—and most tree operations are implemented recursively. Binary search trees are only efficient to the extent that they are well balanced—not too deep in height. This case study refines the initial code to implement AVL trees, a classic self-balancing strategy.

8.1 Binary Search Trees

Binary search trees are a form of rooted trees sometimes used to implement mappings from keys to values. Key–value pairs are stored in the nodes of the tree. Each node has up to two children, the left child ...