The design of dynamic data structures (Q797269)

The author addresses himself to a number of techniques for turning static data structures into dynamic data structures. The techniques presented are generalised and provide a set of adaptable tools for those who have to design dynamic data structures for specific problems. This monograph extends the author's PhD thesis by incorporation results of other workers and a comprehensive bibliography is presented at the end. After a general introduction to problems involving multi-dimensional searching, the author devotes three chapters to tree balancing, covering established ground as well as introducing new approaches. Two chapters then address decomposable problems and then two chapters consider specific environments; one considers improvements which can be made when structure updates are batched and so known in advance, and the other imposes the constraint that all alterations to the structure must be ''remembered''. Finally, a short chapter presents a few open problems in this area. The author concentrates on the formal definition of structures and the book is largely a collection of theorems defining the formal properties of these structures. The techniques are not described algorithmically and no attempt is made to present programming aspects.- The text is aimed at the serious student of data structures and, in this context, should appeal.