logo
分类于: 计算机基础 职场办公

简介

Advanced Data Structures

Advanced Data Structures 8.8分

资源最后更新于 2020-07-26 15:37:52

作者:Peter Brass

出版社:Cambridge University Press

出版日期:2008-01

ISBN:9780521880374

文件格式: pdf

标签: 数据结构 算法 algorithm 计算机科学 计算机 算法与数据结构 data-structure 编程

简介· · · · · ·

Product Description

Advanced Data Structures presents a comprehensive look at the ideas, analysis, and implementation details of data structures as a specialized topic in applied algorithms. Data structures are how data is stored within a computer, and how one can go about searching for data within. This text examines efficient ways to search and update sets of numbers, interva...

想要: 点击会收藏到你的 我的收藏,可以在这里查看

已收: 表示已经收藏

Tips: 注册一个用户 可以通过用户中心得到电子书更新的通知哦

目录

1 Elementary Structures 1
1.1 Stack 1
1.2 Queue 8
1.3 Double-Ended Queue 16
1.4 Dynamical Allocation of Nodes 16
1.5 Shadow Copies of Array-Based Structures 18
2 Search Trees 23
2.1 Two Models of Search Trees 23
2.2 General Properties and Transformations 26
2.3 Height of a Search Tree 29
2.4 Basic Find, Insert, and Delete 31
2.5 Returning fromLeaf to Root 35
2.6 Dealing with Nonunique Keys 37
2.7 Queries for the Keys in an Interval 38
2.8 Building Optimal Search Trees 40
2.9 Converting Trees into Lists 47
2.10 Removing a Tree 48
3 Balanced Search Trees 50
3.1 Height-Balanced Trees 50
3.2 Weight-Balanced Trees 61
3.3 (a, b)- and B-Trees 72
3.4 Red-Black Trees and Trees of Almost Optimal Height 89
3.5 Top-Down Rebalancing for Red-Black Trees 101
3.6 Trees with Constant Update Time at a Known Location 111
3.7 Finger Trees and Level Linking 114
vii

3.8 Trees with Partial Rebuilding: Amortized Analysis 119
3.9 Splay Trees: Adaptive Data Structures 122
3.10 Skip Lists: Randomized Data Structures 135
3.11 Joining and Splitting Balanced Search Trees 143
4 Tree Structures for Sets of Intervals 148
4.1 Interval Trees 148
4.2 Segment Trees 154
4.3 Trees for the Union of Intervals 162
4.4 Trees for Sums of Weighted Intervals 169
4.5 Trees for Interval-Restricted Maximum Sum Queries 174
4.6 Orthogonal Range Trees 182
4.7 Higher-Dimensional Segment Trees 196
4.8 Other Systems of Building Blocks 199
4.9 Range-Counting and the Semigroup Model 202
4.10 kd-Trees and Related Structures 204
5 Heaps 209
5.1 Balanced Search Trees as Heaps 210
5.2 Array-Based Heaps 214
5.3 Heap-Ordered Trees and Half-Ordered Trees 221
5.4 Leftist Heaps 227
5.5 Skew Heaps 235
5.6 Binomial Heaps 239
5.7 Changing Keys in Heaps 248
5.8 Fibonacci Heaps 250
5.9 Heaps of Optimal Complexity 262
5.10 Double-Ended Heap Structures and Multidimensional
Heaps 267
5.11 Heap-Related Structures with Constant-Time Updates 271
6 Union-Find and Related Structures 278
6.1 Union-Find: Merging Classes of a Partition 279
6.2 Union-Find with Copies and Dynamic Segment Trees 293
6.3 List Splitting 303
6.4 Problems on Root-Directed Trees 306
6.5 Maintaining a Linear Order 317
7 Data Structure Transformations 321
7.1 Making Structures Dynamic 321
7.2 Making Structures Persistent 330

8 Data Structures for Strings 335
8.1 Tries and Compressed Tries 336
8.2 Dictionaries Allowing Errors in Queries 356
8.3 Suffix Trees 360
8.4 Suffix Arrays 367
9 Hash Tables 374
9.1 Basic Hash Tables and Collision Resolution 374
9.2 Universal Families of Hash Functions 380
9.3 Perfect Hash Functions 391
9.4 Hash Trees 397
9.5 Extendible Hashing 398
9.6 Membership Testers and Bloom Filters 402
10 Appendix 406
10.1 The Pointer Machine and Alternative Computation
Models 406
10.2 External Memory Models and Cache-Oblivious
Algorithms 408
10.3 Naming of Data Structures 409
10.4 Solving Linear Recurrences 410
10.5 Very Slowly Growing Functions 412
11 References 415
Author Index 441
Subject Index 455