高級數據結構

第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  二叉樹的形態(tài)
  2.3  二叉排序樹
  2.4  哈夫曼二叉樹
  2.5  字典樹
  2.6  本章習題
第3章  優(yōu)先隊列與二叉堆
  3.1  優(yōu)先隊列
  3.2  二叉堆
    3.2.1  Put操作
    3.2.2  Get操作
  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  用線段樹優(yōu)化動態(tài)規(guī)劃
    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  查詢任意區(qū)間和
    6.4.2  利用SHill數組求出原數組a的某個元素值
    6.4.3  找到某個前綴和對應的前綴下標index
    6.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章  Treap
  8.1  Treap的基本操作
  8.2  Treap的算法實現
  8.3  Treap的應用舉例
  8.4  本章習題
第9章  平衡樹
  9.1  AVL樹
  9.2  紅—黑樹
  9.3  SBT
    9.3.1  SBT的基本操作
    9.3.2  SBT的效率分析
    9.3.3  SBT的算法實現
  9.4  本章習題
第10章  塊狀鏈表與塊狀樹
  10.1  塊狀鏈表的基本思想
  10.2  塊狀鏈表的基本操作
  10.3  塊狀鏈表的擴張
    10.3.1  維護區(qū)間和以及區(qū)間最值
    10.3.2  維護局部數據有序化
    10.3.3  維護區(qū)間翻轉
  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  擴展規(guī)則約定
    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.4  DC3算法和DC算法
    11.7.4.1  DC3算法
    11.7.4.2  DC算法
  11.8  LCP的引入
  11.9  后綴數組的應用
    11.9.1  后綴排序的直接應用
    11.9.1.1  Burrows—Wheeler變換
    11.9.1.2  多模式串的匹配
    11.9.2  通過引入LCP優(yōu)化
    11.9.2.1  多模式串的匹配
    11.9.2.2  重復子串問題
    11.9.2.3  最長回文子串
    11.9.2.4  最長公共子串
    11.9.3  后綴數組的應用舉例
  11.10  本章習題
第12章  樹鏈剖分與動態(tài)樹
  12.1  樹鏈剖分的思想和性質
  12.2  樹鏈剖分的實現及應用
  12.3  動態(tài)樹的初探
    12.3.1  動態(tài)樹的常用功能
    12.3.2  動態(tài)樹的簡單情形
  12.4  動態(tài)樹的實現
    12.4.1  動態(tài)樹的基本操作及其實現
    12.4.1.1  動態(tài)樹的問題模型
    12.4.1.2  用Splay維護實路徑
    12.4.2  動態(tài)樹操作的時間復雜度分析
    12.4.2.1  動態(tài)樹操作的次數
    12.4.2.2  Splay操作的平攤時間
  12.5  動態(tài)樹的經典應用
    12.5.1  求最近公共祖先
    12.5.2  并查集操作
    12.5.3  求最大流
    12.5.4  求生成樹
  12.6  動態(tài)樹的應用舉例
  12.7  本章習題
致謝