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