![](https://csdnimg.cn/release/download_crawler_static/10256219/bg10.jpg)
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