O'Reilly logo

The Functional Approach to Programming by K. Callaway, Michel Mauny, Guy Cousineau

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

Chapter 6

Balanced Trees

 

 

 

This chapter defines a group of functions to manage large-scale data sets. These functions use trees as data structures because they are so well adapted to representing data sets that evolve dynamically, that is, data sets where the size can grow or shrink during computations.

The specific data structure we use is a binary tree. The algorithms we propose make it possible to keep these binary trees balanced, and this property ensures the efficiency of operations we want to carry out.

The main operations for managing a data set are these:

•   searching for an element in the data set;

•   adding an element to the data set;

•   removing an element from the data set.

To search naively for an element in a data set, ...

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