《高级数据结构及算法》目录

《《高级数据结构及算法》目录》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《高级数据结构及算法》目录第一部分.用于索引的数据结构A.AVL树B.B+树C.2-3-4树D.红黑树第二部分.用于优先队列的数据结构A.堆B.左偏树与动态树C.斐波那契堆D.Treap树堆第三部分用于在线动态区间处理的数据结构A.树状数组（BinaryIndexTree）B.线段树（SegmentTree)C.伸展树（SplayTree)D.跳跃表（SkipList)E.划分树第四部分.用于离线区间处理的数据结构A.单调队列B.单调栈第五部分.用于集合操作的数据结构A.并查集B.哈希表第六部分.用于字符串处理的数据结构A.字典树B.后缀树

2、C.后缀数组D.Trie树E.AC自动机第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.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

4、矩形覆盖问题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树状数组与线

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

6、块状链表的基本操作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后缀树拓展到多串的形式

7、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.

8、2.1倍增算法描述11.7.2.2倍增算法代码11.7.3由后缀树得到后缀数组11.7.4DC3算法和DC算法11.7.4.1DC3算法11.7.4.2DC算法11.8LCP的引