文件名称:
Advanced Data Structures
开发工具:
文件大小: 2mb
下载次数: 0
上传时间: 2008-11-28
详细说明： 里面讲述了许多特殊的索引树结构,推荐! Preface page xi 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 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
