Trees for algorithmics (Q723893)

The book comprises of nine chapters organised in two parts; the first part focuses on the theoretical concepts while the latter emphasises particular types of trees for which the theoretical background and examples are presented. Following an overview of general properties of trees presented in the first chapter (such as planar trees, binary (search) trees, digital trees), the authors focus in the second chapter on the random component that can be implemented for trees, emphasising the Catalan model, the Galton-Watson trees and random binary search trees. In the third chapter more algorithms are presented, covering approaches for key searches (tries are also discussed at length). The second part of the book contains six chapters; it commences with definitions and examples of trees that illustrate the combinatorial approach, e.g., the number and lengths of paths for binary trees are discussed alongside other simple tree families; 2-3 trees and B-trees are also presented. The fifth chapter focuses on probabilistic approaches, with the Galton-Watson trees and the Catalan model discussed in detail. Next, the binary search trees are presented from various angles, such as lengths of the maximum paths, properties of recursive trees and algorithmically efficient trees (balanced trees). This trend continues in Chapter 7, where the authors present exact and asymptotic approaches for evaluating parameters. The generalization of trees examined in the previous chapters is summarised in the eighth chapter which focuses on \(m\)-ary search trees (all problems discussed for binary search trees are reiterated for the general \(m\)-ary trees). This part concludes with a chapter on Polya urns for which both the combinatorial and the probabilistic definitions are overviewed. The book is written in French; the level of detail recommends it to a wide audience of undergraduate, graduate and postgraduate researchers. The concepts are presented thoroughly, with a significant level of detail invested in examples. Each chapter concludes with a series of exercises aimed at reinforcing the concepts presented throughout the chapter. The authors also include five appendices. In Appendix A, on algorithmic concepts, an overview of definitions related to binary trees and binary search trees as well as B-trees and tries is presented. In Appendix B elements of combinatorics are discussed (including the concepts of labelled and unlabelled classes, complex cultures on bivariate series, and Mellin transform). In the third appendix probability concepts are presented, such as probability laws, Fourier and Laplace transform, Jensen inequality and Markov chains. Following a brief overview of the history of tree-based algorithms (Appendix D) the book concludes with Appendix E comprising of a summary of tree-related definitions (e.g., types of trees and corresponding parameters).