Trees for algorithmics
type: Item
instance of: scholarly article
title: Trees for algorithmics
zbMATH Open document ID: 1427.68007
DOI: 10.1007/978-3-319-93725-0
author: Brigitte Chauvin
author: Julien Clément
author: Danièle Gardy
published in: Mathématiques \& Applications (Berlin)
publication date: 2018-07-24T00:00:00Z
review text: 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…
reviewed by: Irina Ioana Mohorianu
Mathematics Subject Classification ID: 68-02
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68W01
zbMATH DE Number: 6909998
zbMATH Keywords: trees
zbMATH Keywords: binary trees
zbMATH Keywords: Cayley trees
zbMATH Keywords: tree parameters
zbMATH Keywords: search trees
zbMATH Keywords: 2-3 trees
zbMATH Keywords: B-trees
zbMATH Keywords: Norlund-Rice formula
zbMATH Keywords: bivariate series
zbMATH Keywords: Mellin transform
zbMATH Keywords: Fourier transform
zbMATH Keywords: Laplace transform
zbMATH Keywords: Jensen inequality
zbMATH Keywords: Markov chains
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/978-3-319-93725-0
OpenAlex ID: W2788657954
description: scientific article; zbMATH DE number 6909998