高级数据结构 内容简介

本书在基本数据结构的基础上,围绕一些常用的高级数据结构,结合大量实战例题,深入分析“数据结构是如何服务于算法的”。内容包括:哈希表、树与二叉树、优先队列与堆、并查集、线段树、树状数组、伸展树、TREAP、AVL树等。

高级数据结构 本书特色

《高级数据结构》在基本数据结构的基础上，围绕一些常用的高级数据结构，结合大量实战例题，深入分析“数据结构是如何服务于算法的”。内容包括：哈希表、树与二叉树、优先队列与堆、并查集、线段树、树状数组、伸展树、TREAP、AVL树等。

高级数据结构 目录

第1章哈希表1.1哈希表的基本原理1.2哈希表的基本概念1.3哈希函数的构造1.4哈希表的基本操作1.5冲突的处理1.6哈希表的性能分析1.7哈希表的应用举例1.8本章习题第2章树与二叉树2.1树2.1.1树的存储结构2.1.2树的遍历2.2二叉树2.2.1普通树转换成二叉树2.2.2二叉树的遍历2.2.3二叉树的其他操作2.2.4二叉树的形态2.3二叉排序树2.4哈夫曼二叉树2.5字典树2.6本章习题第3章优先队列与二叉堆3.1优先队列3.2二叉堆3.2.1Put操作3.2.2Get操作3.3可并堆3.3.1左偏树的定义3.3.2左偏树的基本操作3.4本章习题第4章并查集4.1并查集的主要操作4.2并查集的实现4.2.1并查集的数组实现4.2.2并查集的链表实现4.2.3并查集的树实现4.3并查集的应用举例4.4本章习题第5章线段树5.1线段树的应用背景5.2线段树的初步实现5.2.1线段树的结构5.2.2线段树的性质5.2.3线段树的存储5.2.4线段树的常用操作5.2.4.1线段树的构造5.2.4.2线段树的查询5.2.4.3线段树的修改5.2.4.4线段树的延迟修改5.3线段树在一些经典问题中的应用5.3.1逆序对问题5.3.2矩形覆盖问题5.4线段树的扩展5.4.1用线段树优化动态规划5.4.2将线段树扩展到高维5.4.3线段树与平衡树的结合5.5线段树与其他数据结构的比较5.6线段树的应用举例5.7本章习题第6章树状数组6.1树状数组的问题模型6.2树状数组的基本思想6.3树状数组的实现6.3.1子集的划分方法6.3.2查询前缀和6.3.3修改子集和6.4树状数组的常用技巧6.4.1查询任意区间和6.4.2利用SHill数组求出原数组a的某个元素值6.4.3找到某个前缀和对应的前缀下标index6.4.4成倍扩张／缩减6.4.5初始化树状数组6.5树状数组与线段树的比较6.6树状数组扩展到高维的情形6.7树状数组的应用举例6.8本章习题第7章伸展树7.1伸展树的主要操作7.1.1伸展操作7.1.2伸展树的基本操作7.2伸展树的算法实现7.3伸展树的效率分析7.4伸展树的应用举例7.5本章习题第8章Treap8.1Treap的基本操作8.2Treap的算法实现8.3Treap的应用举例8.4本章习题第9章平衡树9.1AVL树9.2红—黑树9.3SBT9.3.1SBT的基本操作9.3.2SBT的效率分析9.3.3SBT的算法实现9.4本章习题第10章块状链表与块状树10.1块状链表的基本思想10.2块状链表的基本操作10.3块状链表的扩张10.3.1维护区间和以及区间*值10.3.2维护局部数据有序化10.3.3维护区间翻转10.4块状链表与其他数据结构的比较10.5分块思想在树上的应用——块状树10.6块状链表的应用举例10.7本章习题第11章后缀树与后缀数组11.1后缀树的简介11.2后缀树的定义11.3后缀树的构建11.3.1后缀树的朴素构建算法11.3.2后缀树的线性时间构建算法11.3.2.1隐式树的朴素构建11.3.2.2扩展规则约定11.3.2.3后缀链加速11.3.2.4进一步加速11.3.2.5后缀树拓展到多串的形式11.3.2.6代码实现11.3.2.7相关证明11.4后缀树的应用11.4.1字符串（集合）的精确匹配11.4.1.1情形一11.4.1.2情形二11.4.1.3情形三11.4.1.4情形四11.4.2公共子串问题11.4.2.1情形五11.4.2.2情形六11.4.2.3情形七11.4.2.4情形八11.4.2.5情形九11.4.3重复子串问题11.4.3.1情形十11.4.3.2情形十一11.4.3.3情形十二11.5后缀数组的简介11.6后缀数组的定义11.7后缀数组的构建11.7.1一种直接的构建算法11.7.2倍增算法11.7.2.1倍增算法描述11.7.2.2倍增算法代码11.7.3由后缀树得到后缀数组11.7.4DC3算法和DC算法11.7.4.1DC3算法11.7.4.2DC算法11.8LCP的引入11.9后缀数组的应用11.9.1后缀排序的直接应用11.9.1.1Burrows—Wheeler变换11.9.1.2多模式串的匹配11.9.2通过引入LCP优化11.9.2.1多模式串的匹配11.9.2.2重复子串问题11.9.2.3*长回文子串11.9.2.4*长公共子串11.9.3后缀数组的应用举例11.10本章习题第12章树链剖分与动态树12.1树链剖分的思想和性质12.2树链剖分的实现及应用12.3动态树的初探12.3.1动态树的常用功能12.3.2动态树的简单情形12.4动态树的实现12.4.1动态树的基本操作及其实现12.4.1.1动态树的问题模型12.4.1.2用Splay维护实路径12.4.2动态树操作的时间复杂度分析12.4.2.1动态树操作的次数12.4.2.2Splay操作的平摊时间12.5动态树的经典应用12.5.1求*近公共祖先12.5.2并查集操作12.5.3求*大流12.5.4求生成树12.6动态树的应用举例12.7本章习题致谢