知識點梳理：資料結構與算法——進階資料結構

特殊矩陣

壓縮思想：二維->一維

• 三角矩陣（對角線上/下為常數（不一定0））
• 稀疏矩陣：鍊式：十字連結清單；順序：三元組表（一個元素：i,j,Aij；記錄整體行數、列數、非0元個數T）

廣義表

基本概念

線性表每個元素具有相同的資料類型

廣義表：一個線性表中還包括一個或多個子表；一般記作 L = ( x 0 , x 1 , ⋯   , x n − 1 ) L=(x_0, x_1, \cdots, x_{n-1}) L=(x0​,x1​,⋯,xn−1​)

名稱：L；長度：n

每個 x i x_i xi​是L的成員（ x i x_i xi​可以是單個元素：原子/廣義表：子表）

廣義表深度：表中元素都化解為原子後的括号層數

表頭head= x 0 x_0 x0​；表尾tail= ( x 1 , ⋯   , x n − 1 ) (x_1, \cdots, x_{n-1}) (x1​,⋯,xn−1​)（表頭是元素，表尾是表！！！）

分類

純表：根結點到葉結點隻有一條路徑；任何元素（原子、子表）隻能出現一次 【廣義表的表示與latex中的forest表示相似】

可重入表（再入表）：表中元素可多次出現

循環表（遞歸表）：含回路，深度無窮大

線性表 ⊆ \subseteq ⊆純表（樹） ⊆ \subseteq ⊆再入表 ⊆ \subseteq ⊆圖

廣義表存儲ADT：

tag=0(單元素)/1 (子表)	data/sublist(子表頭指針)	next(後繼結點)

增加頭指針簡化删除、插入（tag=-1）

Trie結構

消除BST的不平衡->改變關鍵碼的劃分方式

Trie（字首樹、字典樹）:基于關鍵碼分解的資料結構；有序樹（與插入順序無關）

關鍵碼集合固定；對結點分層标記

時間複雜度隻與表達這些元素的關鍵碼長度有關，與元素個數無關（開始時就已确定可能出現的位置）

根結點不含字元

除根結點外每個結點一個字元，各不相同

根結點到某一結點路徑經過字元連成結點對應的字元串

查找關鍵字效率與結點數無關，而取決于關鍵字字元數

Trie結構不是平衡的

應用：詞頻統計、字首比對、排序

PAT-tree：二叉Trie樹，有壓縮

最佳BST

基于使用者通路習慣

普通的二叉搜尋樹：n個關鍵碼不同排列BST樹可能相同，有 C 2 n n − C 2 n n − 1 = 1 n + 1 C 2 n n C_{2 n}^{n}-C_{2 n}^{n-1}=\frac{1}{n+1} C_{2 n}^{n} C2nn​−C2nn−1​=n+11​C2nn​（Catalan數）種二叉搜尋樹

擴充二叉搜尋樹：每個外部結點代表其值處于原二叉搜尋樹的兩個相鄰結點關鍵碼值之間的可能關鍵碼的集合

最佳BST：

根據使用者通路頻率尋找ASL最小的二叉搜尋樹

構造方法：

任何子樹都是最佳二叉搜尋樹->動态規劃從下至上；逐漸構造含i個關鍵碼的最佳二叉搜尋樹

• 樹定義T(i,j)：關鍵碼： ( k e y i + 1 , k e y i + 2 , … , k e y j ) \left(ke y_{{i}+1}, {key}_{{i}+2}, \ldots, {key}_{{j}}\right) (keyi+1​,keyi+2​,…,keyj​)；

  内、外結點權值： ( q i , p i + 1 , q i + 1 , … , p j , q j ) \left({q}_{{i}}, {p}_{{i}+{1}}, {q}_{{i}+{1}}, \ldots, {p}_{{j}}, {q}_{{j}}\right) (qi​,pi+1​,qi+1​,…,pj​,qj​)

  查詢代價（平均比較次數）：(根結點為第0層)

  C(i,j)= ∑ x = i + 1 j p x ( l x + 1 ) + ∑ x = i j q x l x ′ \sum_{x=i+1}^{j}p_x(l_x+1)+\sum^{j}_{x=i}q_xl'_x ∑x=i+1j​px​(lx​+1)+∑x=ij​qx​lx′​

• 對于子樹T(i,j)：

  左子樹：C(i,j)=W(i,j)+min(C(i,k-1)+C(k,j))（以k為根）(W(i,j)的意思是相當于每個結點加一層)

平衡BST（AVL）

基于樹高平衡限制： ∣ h R − h L ∣ ≤ 1 |h_R-h_L|\leq 1 ∣hR​−hL​∣≤1

插入後失衡

• LL/RR

  單旋轉（LL：-1結點轉到-2位置；RR：1結點到2位置）

  

• LR/RL

  雙旋/提升（最後那個不平衡結點提升到2位置（LR：-1；RL：1））

  

删除

與後繼交換再删除

沿着被删除結點到根結點的路徑調整變化（可能要向上回溯很多次）

情況：最下層不平衡發生在結點root開始的子樹中；删除的是root左子樹中的結點

初始時modified=true（意思是初始時每個結點在子樹高度變化時失衡都會向上傳遞）

• b f ( r o o t ) = 0 bf(root)=0 bf(root)=0:bf改為1/-1，同時modified=false

  以root為根的子樹高度不變，不影響祖先bf，調整結束

• b f ( r o o t ) ≠ 0 bf(root)\not=0 bf(root)​=0
  • 較高子樹縮短：bf改為0，modified=true，繼續向上修改
  • 較低子樹縮短：root失衡
    • b f ( r i g h t ) = 0 bf(right)=0 bf(right)=0:單旋恢複root平衡，modified=false（子樹高度未變，失衡不會向上傳遞）

      

    • b f ( r i g h t ) = b f ( r o o t ) bf(right)=bf(root) bf(right)=bf(root):單旋恢複root平衡，modified=true

      

    • b f ( r i g h t ) ≠ b f ( r o o t ) bf(right)\not=bf(root) bf(right)​=bf(root):雙旋恢複root平衡，modified=true

      

      • right-left左重：

        

      • right-left右重：

        

      • right-left平衡：則最後root, right,right-left皆平衡，modified=true
    （right-left決定的是調整後左偏/右偏的結果，對操作沒什麼影響）

AVL Tree的擴充

放寬 Δ h \Delta h Δh的限制，使得調整次數變少

伸展樹（splaying）

基于使用者動态通路特征

不保證樹高平衡

（據說這個東西多半是考應用（給出splaying tree的函數））

插入x：x移到根結點

删除x：x的父結點移到根結點

=>經常通路的結點就會在根結點附近活動

展開包括一系列旋轉：（單、雙，每次最多轉兩個，最後到根結點/根結點子結點（此時再單旋））

雙旋轉：

• 一字形（同構調整）：直接暴力轉，調子樹

  不會降低樹結構高度

• 之字形（異構調整）：相當于提升

  使子樹結構高度-1

伸展樹不能保證每單個操作有效率（偶爾進行不常用的通路）

每次通路操作平均代價：O(log n)

比較