文档介绍：Advanced Data Structures
PETER BRASS
City College of New York
CAMBRIDGE UNIVERSITY PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo
Cambridge University Press
The Edinburgh Building, Cambridge CB2 8RU, UK
Published in the United States of America by Cambridge University Press, New York
Information on this title: 0521880374
© Peter Brass 2008
This publication is in copyright. Subject to statutory exception and to the
provision of relevant collective licensing agreements, no reproduction of any part
may take place without the written permission of Cambridge University Press.
First published in print format 2008
ISBN-13 978-0-511-43685-7 eBook (EBL)
ISBN-13 978-0-521-88037-4 hardback
Cambridge University Press has no responsibility for the persistence or accuracy
of urls for external or third-party websites referred to in this publication,
and does not guarantee that any content on such websites is, or will remain,
accurate or appropriate.
Contents
Preface page xi
1 Elementary Structures 1
Stack 1
Queue 8
Double-Ended Queue 16
Dynamical Allocation of Nodes 16
Shadow Copies of Array-Based Structures 18
2 Search Trees 23
Two Models of Search Trees 23
General Properties and Transformations 26
Height of a Search Tree 29
Basic Find, Insert, and Delete 31
Dealing with Nonunique Keys 37
Queries for the Keys in an Interval 38
Building Optimal Search Trees 40
Converting Trees into Lists 47
Removing a Tree 48
3 Balanced Search Trees 50
Height-Balanced Trees 50
Weight-Balanced Trees 61
(a, b)- and B-Trees 72
Red-Black Trees and Trees of Almost Optimal Height 89
-DownRebalancingforRed-BlackTrees101
Trees with Constant Update Time at a Known Location 111
Finger Trees and Level Linking 114
vii
viii Contents
Trees with Partial Rebuilding: Amortized Analysi