xiv
Contents
9.5 Adaptable Priority Queues . . . . . . . . . . . . . . . . . . . . . . . 390
9.5.1 Location-Aware Entries . . . . . . . . . . . . . . . . . . . . . . 391
9.5.2 Implementin g a n Adaptable Priority Queue . . . . . . . . . . . 392
9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
10 Maps, Hash Tables, and Skip Lists 401
10.1 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
10.1.1 The Map ADT . . . . . . . . . . . . . . . . . . . . . . . . . . 403
10.1.2 Application: Counting Word Frequencies . . . . . . . . . . . . . 405
10.1.3 An AbstractMap Base Class . . . . . . . . . . . . . . . . . . . 406
10.1.4 A Simple Unsorted Map Implementation . . . . . . . . . . . . . 408
10.2 Hash Tab les . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
10.2.1 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 411
10.2.2 Collision-Handling Schemes . . . . . . . . . . . . . . . . . . . . 417
10.2.3 Load Factors, Rehashing, and Efficiency . . . . . . . . . . . . . 420
10.2.4 Java Hash Table Impl ementation . . . . . . . . . . . . . . . . . 422
10.3 Sorted Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
10.3.1 Sorted Search Tables . . . . . . . . . . . . . . . . . . . . . . . 429
10.3.2 Two Applications of Sorted Maps . . . . . . . . . . . . . . . . 433
10.4 Skip Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
10.4.1 Search and Update Operations in a Skip List . . . . . . . . . . 438
10.4.2 Probabilistic Analysis of Skip Lists
⋆ . . . . . . . . . . . . . . . 442
10.5 Sets, Multisets, and Multimaps . . . . . . . . . . . . . . . . . . . . 445
10.5.1 The Set ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
10.5.2 The Multis et ADT . . . . . . . . . . . . . . . . . . . . . . . . 447
10.5.3 The Multimap ADT . . . . . . . . . . . . . . . . . . . . . . . . 448
10.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
11 Search Trees 459
11.1 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
11.1.1 Searching Within a Binary Search Tree . . . . . . . . . . . . . . 461
11.1.2 Insertions and Deletions . . . . . . . . . . . . . . . . . . . . . . 463
11.1.3 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 466
11.1.4 Performance of a Binary Search Tree . . . . . . . . . . . . . . . 470
11.2 Balanced Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . 472
11.2.1 Java Framework for Balancing Search Trees . . . . . . . . . . . 475
11.3 AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
11.3.1 Update Operations . . . . . . . . . . . . . . . . . . . . . . . . 481
11.3.2 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 486
11.4 Splay Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
11.4.1 Splaying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
11.4.2 When to Splay . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
11.4.3 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 494
11.4.4 Amortized Analysis of Splaying
⋆ . . . . . . . . . . . . . . . . 495
11.5 (2,4) Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
11.5.1 Multiway Search Trees . . . . . . . . . . . . . . . . . . . . . . 500
11.5.2 (2,4)-Tree Operatio ns . . . . . . . . . . . . . . . . . . . . . . . 503
剩余737页未读，继续阅读
iammatlab
- 粉丝: 4
- 资源: 12
我的内容管理
展开
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析：故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全：高效编程的秘密武器
- 网页制作入门：常用代码详解
- TX2440A开发板网络远程监控系统移植教程：易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析：Socket基础与应用
- 掌握Struts1：Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全：字体、文本、列表样式详解
- Proteus元件库大全：从基础到高级组件
- 74HC08芯片：高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题：设置字符集为GB2312
- C语言的诞生与演进：从汇编到系统编程的革命
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
