CONTENTS Preface vii PART 1. BASIC CONCEPTS AND ALGORITHMS 1 Chapter 1. TREES AND THEIR PROPERTIES 1 1.1. Introduction and Basic Definitions 1 1.2. Representations of Trees 18 1.3. Numbering and Calculation of Trees 39 1.4. Bibliographical Notes 46 References 46 Chapter 2. COMPUTA TIONAL MODELS. COMPLEXITY AND FUND AMENT AL ALGORITHMS 49 2.1. Introduction. Algorithm Representation Language 49 2.2. Depth-First and Breadth-First Traversals of Graphs and Trees 61 2.3. Generation of Trees 91 2.4. Bibliographical Notes 112 References 115 Chapter 3. SPANNING TREES 121 3.1. The Problem of Finding the Optimal Spanning Tree 121 3.2. Algorithms of Numbering of All Spanning Trees 140 3.3. Search of Spanning Trees with Given Properties 154 3.4. Bibliographical Notes 159 References 163 PART 2. TRANSLATION AND TRANSFORMATION OF PROGRAMS 175 Chapter 4. STRUCTURAL TREES 175 4.1. Introduction and Principal Definitions 175 4.2. Hierarchical Representations of Regularizable CF-Graphs 187 4.3. Hammock Representations of CF-Graphs 198 4.4. Exposure of the Dominance Relation 208 4.5. Bibliographical Notes 215 References 219 Chapter 5. ISOMORPHISM, UNIFICATION, AND TERM-REWRITING SYSTEMS 223 5.1. Isomorphisms of Trees 223 5.2. Problem of Unification 240 5.3. Term-Rewriting Systems 267 5.4. Bibliographical Notes 283 References 285 Chapter 6. SYNTAX TREES 293 6.1. Language Syntax and the Problem of Syntax Analysis 293 6.2. Generative Grammars 295 6.3. Syntax Analysis 302 6.4. Translation and Constructors of Analyzers 323 6.5. Bibliographical Notes 333 References 333 PART 3. SEARCH AND STORAGE OF INFORMATION 337 Chapter 7. INFORM1ATION TREES 337 7.1. Balanced Trees 337 7.2. Multidimensional Trees (k-d-Trees) 364 7.3. Bibliographical Notes 372 References 372 Chapter 8. TREES FOR MULTILEVEL MEMORY 375 8.1. B-Trees 375 8.2. Generalizations of B-Trees 385 8.3. Multidimensional B-Trees 393 8.4. Multiattribute Trees 406 8.5. Bibliographical Notes 418 References 419 ADDITIONAL LIST OF LITERATURE 423 SUBJECT INDEX 427
京公网安备 11010102004214号