第一部分　改进基本数据结构

在这一部分，我们旨在为稍后即将讨论的更高级的内容奠定基础。我们将重点关注那些能为更基础的数据结构提供改进的高级数据结构。例如，其中会提到应该如何改进二叉堆（让树变得平衡），以及应该如何解决像跟踪一个或一组事物这样的问题。

这部分内容将通过各种示例来证明对数据进行操作的方法其实有很多种。开发人员需要明白，可以选择的最佳方法取决于上下文和需求。因此，我们需要查看需求、检查上下文，并在解决问题时学会质疑我们已掌握的知识，进而针对所面临的具体问题找到最佳解决方案。

第2章介绍二叉堆的高级变体d叉堆（d-way heap），以及这一部分剩余各章中用来介绍各种主题的编撰结构。

第3章通过树堆（treap）进一步探讨堆的高级用法。树堆是二叉搜索树和堆的混合体，可以在不同的上下文中为你提供帮助。

第4章将主题切换到了布隆过滤器（Bloom filter）。这是哈希表的一种高级形式，可在节省内存的同时，将查找操作的平摊时间复杂度维持在常数。

第5章介绍一些用来跟踪不交集（disjoint set）的替代数据结构。不交集是构建无数高级算法所必需的基石，已被用在若干实际的应用中。

第6章展示了两种在存储和查找字符串方面都优于通用容器的数据结构：trie以及被称为压缩前缀树的基数树。

第7章将基于前6章介绍的数据结构，构建一个能有效处理缓存的组合数据结构——LRU缓存（LRU-cache），还将详细讨论LRU缓存的变体——LFU缓存（LFU-cache），以及如何在多线程环境中同步共享容器的问题。