課程介紹

先修課：概率統(tǒng)計买猖，程序設(shè)計實習(xí)改橘，集合論與圖論

后續(xù)課：算法分析與設(shè)計，編譯原理玉控，操作系統(tǒng)飞主，數(shù)據(jù)庫概論，人工智能高诺，圖形圖像碌识，Web信息處理

? "數(shù)據(jù)結(jié)構(gòu)和算法是衡量計算機科班出身的重要標準。值得花大功夫去學(xué)虱而。"

課程特點：基礎(chǔ)性+理論性+實踐性+挑戰(zhàn)性

教學(xué)要求：

? 預(yù)習(xí)自學(xué)+可討論不抄襲+加強訓(xùn)練+有效反饋

? 書面作業(yè)：寫學(xué)號名字筏餐，每次都在文本寫上"我保證沒有抄襲別人作業(yè)"；

課程網(wǎng)站：www.chinesemooc.org ;course.pku.edu.cn

課程評估：平時40（書面考勤15牡拇，慕課25）魁瞪，考試60（期中18，機考18惠呼，期末24）;

數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu) ：設(shè)計數(shù)據(jù)之間的邏輯關(guān)系导俘、數(shù)據(jù)在計算機中的存儲表示和在這種結(jié)構(gòu)上的一組能執(zhí)行的操作（運算）三個方面。

-邏輯結(jié)構(gòu)： 從具體問題抽象出來的數(shù)學(xué)模型剔蹋，反映了事物的組成結(jié)構(gòu)和事物之間的邏輯關(guān)系旅薄。

• 線性結(jié)構(gòu)： 亦稱"前驅(qū)關(guān)系"。關(guān)系r有向泣崩，滿足全序性（全部結(jié)點兩兩皆可比較前后）和單索性（每個結(jié)點皆有前驅(qū)和后繼結(jié)點）等約束條件少梁。
• 樹形結(jié)構(gòu)： 亦稱"層次結(jié)構(gòu)"，每個節(jié)點可有多于一個后繼結(jié)點矫付，但只有唯一的直接前驅(qū)凯沪。
• 圖形結(jié)構(gòu)： 有時稱為結(jié)點互聯(lián)的網(wǎng)絡(luò)結(jié)構(gòu)，對關(guān)系r沒有加任何約束技即。

-存儲結(jié)構(gòu)： 也稱物理結(jié)構(gòu)著洼，是邏輯結(jié)構(gòu)在計算機中的物理存儲表示。

• 四種基本存儲映射方法：順序而叼、鏈接、索引豹悬、散列

自頂向下的邏輯結(jié)構(gòu)分析設(shè)計方法

算法

? 分類：窮舉葵陵，回溯，貪心瞻佛，遞歸脱篙，動態(tài)規(guī)劃娇钱，分治

Stack & Queue

Characters

1. Basic data structure
2. Limited operations

Both have many transformation.

• Stack (Last-In-First-Out LIFO)
  • push & pop: only one way in/out

• top, isEmpty, is Full (:arrow_right:depend on specific implement , like array or others)

• Phisical Implement:

  • Array-based

    template <class T>
    class arrStack :public Stack <T>{
          private:
              int mSize,top;
           T *st;
          public:
              arrStack(int size){
              mSize=size;
              st=new T[msize];
              top=-1;
            }
              arrStack(){top=-1;}
              ~arrStack(){delete []st;}
              void clear(){top=-1;}
              bool arrStack<T>::push(const T item) {
              if (top == mSize-1) {return false;}
              else {                      
                  st[++top] = item;   
                  return true;
              }
          }
              bool arrStack<T>::pop(T & item) {
              if (top == -1) {return false;}
              else {
                  item = st[top--];   
                  return true;
                  }
              };
    

    //Pay attention to overflow and underflow.

  • Linked.

  template <class T> 
  class  InkStack : public Stack <T>{
    ...
      bool InkStack<T>::push(const T item){
          Link<T>*tmp=newLink<T>(item,top);
          top=tmp;
          size++;
          return true;
      }
      bool InStack<T>::pop(T&item){
          Link<T>*tmp; 
          if(size==0){return false;}
          item =top->data; //think of holding a rope
          tmp=top->next;
          delete top;
          top=tmp;
          size--;
          return true;
      }
  };
  

  comparation:

  ? Time: Both O(1)；

  ? Space: Array stack must state its set length.
  ? Linked stack has changeable length but increase cost of
  ? its structure.

  • Application - DPS, recursion, management of subprograme.

• Allocation of memory when executing programme

圖片1.png

• • static

  • dynamic

    • heap (like pointer, need to delete)

- stack

• Postfix Expression

  No brackets!

出棧次序：一個棧的進棧次序為1绊困、2文搂、3……n。不同的出棧次序有幾種?
我們可以這樣想秤朗，假設(shè)k是最后一個出棧的數(shù)煤蹭。比k早進棧且早出棧的有k-1個數(shù)，一共有h(k-1)種方案取视。比k晚進棧且早出棧的有n-k個數(shù)硝皂，一共有h(n-k)種方案。所以一共有h(k-1)h(n-k)種方案作谭。顯而易見稽物，k取不同值時，產(chǎn)生的出棧序列是相互獨立的折欠，所以結(jié)果可以累加贝或。k的取值范圍為1至n，所以結(jié)果就為h(n)= h(0)h(n-1)+h(1)h(n-2) + ... + h(n-1)h(0)锐秦。
卡特蘭數(shù)：h(n)=C(2n,n)/n+1=C(2n,n)-C(2n,n+1)=h(0)h(n-1)+...+h(n-1)h(0)

表達式求值：中綴表達式轉(zhuǎn)后綴表達式并計算
先轉(zhuǎn)換傀缩，輸入操作數(shù)直接輸出到序列，輸入左括號時壓棧农猬，輸入運算符時赡艰，如果大于當前棧頂運算發(fā)則壓棧，不然出棧循環(huán)至棧非空棧頂不是左括號且棧中運算符優(yōu)先級小于當前的優(yōu)先級再壓棧斤葱，輸入有括號時彈至第一個左括號慷垮；再求值，把數(shù)字讀進棧揍堕，碰到運算符就取出倆計算將結(jié)果壓棧料身。

• Queue

  First In First Out (FIFO)

  Applied in message processing, BPS, communication inside computer

  • Basic operation:　enQueue, deQueue, ...

  • Storage

    • Sequencial Queue
      Using vector to store elements in queue, and let two variables point to its front and rear.
      Often fix the front part, and let the rear one point to the "empty position", making insert O(n), delete O(1).
      Another approach is to make Q.front and Q.rear point to the first and last element dynamically, but this lead to false overflow. However, by introducing round-robin queue this problem can be solved. Sacrifice of an element makes judging full possible and module helps to circulate. Then both insert and delete are O(1).

    • Linked Queue

      Biggest problem: limited direct access

Q: How to simulate a queue using two stacks? And what about the opposite?

A: Actually the push() is same for both, for the first question, when the first element need to pop out of queue, we only need to get each elements under it to the other stack and repush them back one by one.

String

A sequencial linear list with limited content

Note that a pointer is larger than a char, it's not cost-efficient to make linked string.

Its complexity is due to the dynamic change of its length.

Character Encoding:

? Type: ASCII, UNICODE, charset, GB2312
? Standard String: char S[M] with set length, not an OOP data type
? String class: an encapsulation of standard string
? Rule: partial order encoding rules

Substring - NLP

Operation

? ==, find, =, substr, strcpy...
? +，...

Pattern Matching

The oldest and most widely researched problem.
Applied in bioinfomatics, information retrieval, spell check, data compressino test and so on.

• A target object T plus a pattern P, where T&P are both string.

• Mission
  Based on template P, search the substring which is completely near to P in target objects, and return the address of the matched substring. And the pattern is always with wildcard character.

• Classification

  Approximate String Matching
  $distance = least\ sum\ of\ steps\ to \ convert $

• Method

  • Brute Force: compare characters one by one :arrow_right:O(n*m)

  • ==KMP== (Knuth-Morrit-Pratt) :arrow_right: O(n)

    Target: To make it possible for target pointer never goes back.
    Solution: Make use of "next" array to ascertain steps for target pointer to move. Break the pattern string into max prefix together with max postfix. And hence "next" array is acquired.

    $$next[i]=\begin{cases}-1&\text{i=0}\max\ k:0<k<i \land P(0,...,k-1)=P(i-k,...,i-1)&{\exists k}\0&\text{else}\end{cases}$$

圖片2.png

  $$better\_next[i]=\begin{cases}next[i]&\text{pattern[i]≠ pattern[better[i+1]]}\\next[next[i]]&\text{else}\end{cases}$$ 

int findNext*(string P) {
    int i, k;
    int m = P.length( );          //m為模板P的長度
    int *next = new  int[m];      //動態(tài)存儲區(qū)開辟整數(shù)數(shù)組
    next[0] = -1;   
    i = 0;  k = -1;
    while (i < m-1) {             //若寫成i < m 會越界
        while (k >= 0 && P[k] != P[i]) //找首尾子串
              k = next[k];        //k遞歸地向前找
        i++;   k++; 
        if (P[k] == P[i])   
              next[i] = next[k];  //前面找k值衩茸，優(yōu)化步驟
        else next[i] = k;        
    }
    return next;
}

注意：書里面有挺多錯的芹血。P95第一行，如果p[i]≠p[k] 如果p[i]=p[k]楞慈。

算法導(dǎo)論17：攤還分析學(xué)習(xí)筆記-KMP復(fù)雜度證明

在攤還分析中幔烛，通過求數(shù)據(jù)結(jié)構(gòu)的一系列的操作的平均時間，來評價操作的代價囊蓝。這樣饿悬，即使這些操作中的某個單一操作的代價很高，也可以證明平均代價很低聚霜。攤還分析不涉及概率狡恬，它可以保證最壞情況下每個操作的平均性能珠叔。

攤還分析有三種常用的技術(shù)：聚合分析，它確定$n$個操作的總代價的上界為$T(n)$弟劲，所以每個操作的平均代價為$\frac{{T(n)}}{n}$祷安。每個操作都有相同的攤還代價。核算法：分析每個操作的攤還代價兔乞，不同于聚合分析汇鞭，每種操作的攤還代價是不同的，核算法將序列中較早的操作的余額作為“信用”儲存起來报嵌，與數(shù)據(jù)結(jié)構(gòu)中的特定對象相關(guān)聯(lián)虱咧，在隨后的操作中，儲存的信用可以用來進行支付锚国。勢能法：與核算法類似腕巡，也是分析每個操作的代價，但將勢能作為一個整體存儲血筑，而與數(shù)據(jù)結(jié)構(gòu)中的某個對象無關(guān)绘沉。

一、聚合分析

以棧操作為例：存在3種操作：1豺总、$push$ 2车伞、$pop$ 3、$multipop$直觀地分析復(fù)雜度：因為棧的大小最大為$n$喻喳，所以$multipop$的最壞情況為$O(n)$另玖，所以，由n個$push$,$pop$,$multipop$組成的操作序列的最壞代價為$O( n^2)$表伦，因為序列可能包含$O(n)$個操作序列谦去。

上面的分析給出的界并不是緊確界，實際上蹦哼，在一個空棧上執(zhí)行$n$個$push$, $pop$, $multipop$的操作序列鳄哭，代價最多為$O(n)$。這是因為纲熏，當一個對象壓入棧后妆丘，至多將其彈出一次。所以局劲，對于一個非空的棧勺拣，可以執(zhí)行的$pop$的次數(shù)（包含$multipop$中的$pop$）最多與$push$操作次數(shù)一樣，即$n$次容握。所以宣脉，對任意的$n$，任意一個由$n$個$push$, $pop$, $multipop$組成的操作序列剔氏，最多花費$O(n)$塑猖。所以，每個操作的攤還代價為$O(1)$谈跛。

二羊苟、核函數(shù)

核算法，對不同的操作賦予不同的費用感憾，這個費用就是攤還代價蜡励。當一個操作的攤還代價超過實際代價的時候，將差額存入數(shù)據(jù)結(jié)構(gòu)中的特定對象阻桅，存入的差額稱為信用凉倚。對于后續(xù)操作中，攤還代價小于實際代價的情況嫂沉，信用可以用來支付差額稽寒。因為希望通過分析攤還代價來說明每個操作的平均代價的很小，所以應(yīng)該確保$n$個操作序列的攤還代價是實際代價的上界趟章。如果${c_i}$ 表示第i個操作的真實代價杏糙，而${c'i}$表示攤還代價，則對于任意的$n$蚓土，有：$\sum\limits{i = 1}^n {{c_i}^\prime } \ge \sum\limits_{i = 1}^n {{c_i}} $宏侍。因為信用就是攤還代價和實際代價的差值，即 $\sum\limits_{i = 1}^n {{c_i}^\prime } - \sum\limits_{i = 1}^n {{c_i}} $蜀漆，所以需要保持數(shù)據(jù)結(jié)構(gòu)中的總信用永遠為非負值谅河。

依然以棧操作為例：下面證明，如果按照攤還代價進行繳費确丢，則可以支付任意的$n$個棧操作序列绷耍。在$push$操作時，共繳費2美元蠕嫁，其中1美元支付$push$的實際代價锨天，將剩余的1美元存入插入的元素，作為信用剃毒。這樣病袄，每個插入的元素都具有1美元的信用。這1美元的信用赘阀，實際上是用來支付$pop$操作的預(yù)付費益缠。當執(zhí)行一個$pop$的時候，并不繳額外的費用基公，而是使用信用來支付實際代價幅慌。$multipop$也一樣。所以轰豆，對任意的n個PUSH, POP, MULTIPOP組成的序列胰伍，總攤還代價為實際代價的上界齿诞，總攤還代價為$O(n)$。

三骂租、勢能法

勢能法與核算法類似祷杈，但是勢能法并不將預(yù)付代價表示為數(shù)據(jù)結(jié)構(gòu)中特定對象的信用，而是表示為“勢能”渗饮。勢能是與整個數(shù)據(jù)結(jié)構(gòu)相關(guān)聯(lián)但汞，而不是某個特定的對象。將勢能釋放互站，就可以支付未來操作的代價私蕾。

勢能法如下：對一個初始數(shù)據(jù)結(jié)構(gòu)${D_0}$執(zhí)行$n$個操作。對于i = 1, 2,...,n胡桃， ${c_i}$表示第i個操作的實際代價踩叭， ${D_i}$表示在數(shù)據(jù)結(jié)構(gòu)${D_{i - 1}}$上執(zhí)行第i個操作得到的數(shù)據(jù)結(jié)構(gòu)。勢函數(shù)$\varphi $將每個數(shù)據(jù)結(jié)構(gòu)${D_i}$映射到一個實數(shù) $\varphi ({D_i})$标捺，這個值就是關(guān)聯(lián)到數(shù)據(jù)結(jié)構(gòu)的勢懊纳。所以，第i個操作的攤還代價為${c'i} = {c_i} + \varphi ({D_i}) - \varphi ({D{i - 1}})$亡容。每個操作的攤還代價等于其實際代價加上此操作引起的勢能變化嗤疯。

勢能法其實就是核函數(shù)的總體分析。

再拿kmp算法失配回退時使用的攤還分析技術(shù)：

這個可以用勢能分析法來分析：關(guān)于匹配指針的位置$cur$闺兢，操作A：匹配時茂缚，$cur + + $;操作B：失配時，$cur = next[cur - 1]$; (根據(jù)不同實現(xiàn)有所出入)這個 $next[cur - 1] < = cur - 1$ 是成立的屋谭。

根據(jù)勢能分析($cur \ge 0$ 恒成立)脚囊，我們可以證明，操作A的執(zhí)行次數(shù)一定比操作B要多桐磁，兩個操作都是$O(1)$悔耘。而操作A的執(zhí)行次數(shù)是很容易分析最壞上界是 $O(n)$；那么 $O(n) = T(A) \ge T(B)$我擂，因此匹配時的時間復(fù)雜度$T(A + B) = O(n)$ 衬以。

其實上述操作類似于棧操作，直接類比進行復(fù)雜度分析即可校摩。

二叉樹

二叉樹由結(jié)點的有限集合構(gòu)成看峻，要么為空集，要么由一個根結(jié)點與兩棵不相交的分別稱作左子樹和右子樹的二叉樹組成衙吩。（遞歸定義）

n個結(jié)點的二叉樹有多少種互妓？$f_0=f_1=1$,$f_n=\sum_{i=0}^{n-1}f_{n-i}f_i$

Catalan數(shù)：$f_n=\frac{C_{2n}^{n}{n+1}=C_{2n}}n-C_{2n}^{n+1}$

概念：父母parent，子女/孩子children，邊edge冯勉，兄弟sibling澈蚌，路徑path，祖先ancester珠闰，子孫descendant惜浅，樹葉leaf瘫辩，內(nèi)部結(jié)點/分支結(jié)點internal node伏嗜，度數(shù)degree，層數(shù)/二叉樹高度level伐厌，森林承绸，深度/最長路徑長度。

? 帶根的樹稱為有向樹挣轨。
? 如果一棵二叉樹的結(jié)點或為樹葉（0度結(jié)點）或E為兩棵非空子樹（2度結(jié)點）军熏，則稱作滿二叉樹。
? 如果一棵二叉樹最多只有下面的兩層結(jié)點度數(shù)可以小于2卷扮，最下面一層的結(jié)點都集中在該層最左邊荡澎、連續(xù)位置上則稱此二叉樹為完全二叉樹。完全二叉樹的路徑長度和（由根節(jié)點到各個結(jié)點的路徑長度總和）最短晤锹。
? 當二叉樹結(jié)點出現(xiàn)空指針時摩幔，就增加一個特殊結(jié)點-空樹葉。由此擴充的二叉樹叫做擴充二叉樹鞭铆，它是滿二叉樹或衡，新增加空樹葉的個數(shù)等于原來二叉樹結(jié)點個數(shù)加一，$Length\ Out=Length\ In+2\ Inner\ Node$车遂。歸納法證明

圖片3.png

左子樹優(yōu)先級最大封断，理解為從左向右為大兒子二兒子等。
樹葉指的是沒有兒子的結(jié)點舶担。
根節(jié)點層數(shù)為0坡疼，其他結(jié)點層數(shù)等于父母層數(shù)加1。
森林即多個二叉樹集合衣陶，通過引入虛擬結(jié)點把問題劃歸為單二叉樹柄瑰。

n個結(jié)點的樹有多少條邊？

性質(zhì)

1. 滿二叉樹定理：非空滿二叉樹樹葉數(shù)等于其分支結(jié)點數(shù)加1祖搓，即n₀ = n₂ + 1狱意。
   推論：一個非空二叉樹的孔子書數(shù)目等于其結(jié)點數(shù)加一。

   試證明：在具有n個結(jié)點的k叉數(shù)中拯欧，有n(k-1)+1個指針是空的详囤。

2. 任何一棵二叉樹度為0的結(jié)點n₀比度為2的結(jié)點n₂多1個。即n₀ = n₂+1。

3. 二叉樹的第i層最多有2ⁱ個結(jié)點藏姐。高度為k的二叉樹至多有2^k-1個結(jié)點隆箩。有n個結(jié)點的完全二叉樹高度為[log₂(n+1)]。

周游

二叉樹的結(jié)點存儲所需數(shù)據(jù)信息羔杨，邊保持二叉樹的結(jié)構(gòu)捌臊。操作運算集中在訪問二叉樹的結(jié)點信息上。

/*ADT of binary tree*/
template <class T>
class BinaryTreeNode  {
friend class BinaryTree<T>;                  // 聲明二叉樹類為友元類
private:
    T  info;                                 // 二叉樹結(jié)點數(shù)據(jù)域
public:
    BinaryTreeNode();                        // 缺省構(gòu)造函數(shù)
    BinaryTreeNode(const T& ele);            // 給定數(shù)據(jù)的構(gòu)造
    BinaryTreeNode(const T& ele, BinaryTreeNode<T> *l, 
                  BinaryTreeNode<T> *r);     // 子樹構(gòu)造結(jié)點
    T  value() const;                       // 返回當前結(jié)點數(shù)據(jù)
    BinaryTreeNode<T>* leftchild() const;    // 返回左子樹
    BinaryTreeNode<T>* rightchild() const;   // 返回右子樹
    void  setLeftchild(BinaryTreeNode<T>*);  // 設(shè)置左子樹
    void  setRightchild(BinaryTreeNode<T>*); // 設(shè)置右子樹
    void  setValue(const T& val);           // 設(shè)置數(shù)據(jù)域
    bool  isLeaf() const;                  // 判斷是否為葉結(jié)點
    BinaryTreeNode<T>& operator = 
        (const BinaryTreeNode<T>& Node);    // 重載賦值操作符
};
template <class T>
class BinaryTree  {
private:
     BinaryTreeNode<T>* root;                //二叉樹根結(jié)點
public:
      BinaryTree() {root = NULL;};           //構(gòu)造函數(shù)
      ~BinaryTree() {DeleteBinaryTree(root);};//析構(gòu)函數(shù)
      bool isEmpty() const;                  //判定二叉樹是否為空樹
BinaryTreeNode<T>* Root() {return root;};     //返回根結(jié)點
BinaryTreeNode<T>* Parent(BinaryTreeNode<T> *current);     //返回父
BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T> *current);//左兄
BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T>*current);//右兄
void CreateTree(const T& info, 
     BinaryTree<T>& leftTree, BinaryTree<T>&  rightTree);  // 構(gòu)造樹
void PreOrder(BinaryTreeNode<T> *root);     // 前序遍歷二叉樹
void InOrder(BinaryTreeNode<T> *root);      // 中序遍歷二叉樹
void PostOrder(BinaryTreeNode<T> *root);    // 后序遍歷二叉樹
void LevelOrder(BinaryTreeNode<T> *root);   // 按層次遍歷二叉樹
void DeleteBinaryTree(BinaryTreeNode<T> *root); // 刪除二叉樹
}; 

深度優(yōu)先周游

圖片4.png

注意：已知二叉樹的先序和后序序列兜材，不能唯一確定二叉樹理澎。

給定先序和后序，二叉樹的方案數(shù)有幾種曙寡？約2ⁿ種糠爬，根據(jù)左右子樹的可能來確定。

廣度優(yōu)先周游

#include <queue>
queue <TreeNode> q;

存儲結(jié)構(gòu)

• 鏈式存儲(多為一般的樹)——二/三叉鏈表表示法——指針

• 靜態(tài)數(shù)組存儲(多為完全二叉樹)

  $linknode_tree(level,row)=array_tree[2^{level}-1+row]$

• 廣義的樹的線性存儲結(jié)構(gòu)

應(yīng)用

• 二叉搜索/排序樹 Binary Search Tree

  概念 ：對于任意結(jié)點值為K举庶，其左子樹每一個結(jié)點的值都小于K执隧；其右子樹任意一個結(jié)點的值大于K;且其左右子樹也分別為二叉搜索樹。
  性質(zhì) ：按照中序周游將各個結(jié)點打印出來户侥，將得到從小到大的排列镀琉。樹中結(jié)點值唯一。
  評價 ：二叉樹的效率就在于只需搜索兩個子樹之一蕊唐。在樹形比較平衡時屋摔，二叉樹的搜索效率相當高。
  插入 ：成功的插入基于失敗的查找刃泌。
  刪除 ：:white_circle:-:white_circle:-:white_large_square: :arrow_right: :white_circle:-:white_large_square:

  ? :black_circle: :black_circle:
  ? / \ /
  ? :black_large_square: :white_circle: (delete) :black_large_square: :star2:
  ? / \ /
  ? :small_red_triangle: :black_large_square: :small_red_triangle: :black_large_square:
  ? \
  ? :star2: :eight_pointed_black_star:
  ? /
  ? :eight_pointed_black_star:

堆與優(yōu)先隊列

概念：（以最小值堆為例）

• 一個關(guān)鍵碼序列凡壤，滿足$K_i\le K_{2i+1},K_i\le K_{2i+2}$ ；
• 堆中儲存的數(shù)據(jù)==局部有序==耙替；
• 是一個可用數(shù)組表示的完全二叉樹亚侠，但不唯一昼伴；

建堆：
從堆的最后一個分支結(jié)點 heapArray[Size/2-1]開始吨枉，自底向上羹应，自右向左逐步把以各分支結(jié)點為根的子樹調(diào)整成堆纯衍；

template <class T>   
void MinHeap<T>::SiftDown(int position) {
    int i=position;           //標識父結(jié)點
    int j=2*i+1;              //標識關(guān)鍵值較小的子結(jié)點
    T   temp=heapArray[i];    //保存父結(jié)點
    while (j<CurrentSize){    //過篩
          if ((j<CurrentSize-1)&&(heapArray[j]>heapArray[j+1]))
              j++;           //j指向數(shù)值較小的子結(jié)點
          if (temp>heapArray[j]){
              heapArray[i]=heapArray[j];
              i=j;   j=2*j+1;//向下繼續(xù)
          }  else break;
    }
    heapArray[i]=temp;
}

template<class T>   //從position向上開始調(diào)整辫诅，使序列成為堆
void MinHeap<T>::SiftUp(int position) {    
    int temppos=position;
    T temp=heapArray[temppos];
    while ((temppos>0)&&(heapArray[parent(temppos)]>temp)) {
           heapArray[temppos]=heapArray[parent(temppos)];
           temppos=parent(temppos);
    }
    heapArray[temppos]=temp;
}                  //從葉子節(jié)點

插入： 插到最后一個位置吁讨，再自底向上調(diào)整省古；

移出最小值： 用最后一個位置代替根結(jié)點锁保，再向下調(diào)整除抛；

刪除元素：用最后一個位置代替待刪元素狮杨，再向上向下調(diào)整；

建堆效率：樹的高度是log₂n到忽，delete, insert都是O(logn)的橄教；建堆的計算時間為 $\sum_{i=0}^{log_2n}2i(log_2n-i)=\sum_{j=0}^{{log_2n}n\frac{j}{2}j}<2n \ \ (let \ j=log_2n-i)$清寇；

優(yōu)先隊列： 可從一個集合中快速查找并移出具有最大值或最小值的元素。堆是優(yōu)先隊列的一種自然實現(xiàn)方法护蝶。

Huffman Tree

背景：通信中使用不等長的編碼來表示不同使用頻率的字符——保證任何字符的編碼不是其他字符編碼的前綴华烟。可以把編碼視為二叉樹持灰，葉子分別代表一個字符盔夜。往左賦值為0，往右賦值為1堤魁。

Huffman Tree： 具有最小帶權(quán)路徑長度的二叉樹稱作哈夫曼樹/最優(yōu)二叉樹喂链。

建立過程： 按照權(quán)重把字母排為有序序列，拿走前兩個（權(quán)最幸涛小）標記為Huffman樹樹葉衩藤，將這兩個樹葉標為一個分支結(jié)點的兩個子女，而該節(jié)點的權(quán)即兩樹葉的權(quán)之和涛漂。將所得“權(quán)”放回序列中適當位置，使“權(quán)”順序保持检诗。重復(fù)上述步驟直至序列中剩一個元素匈仗，則建立完畢。

習(xí)題課

動態(tài)規(guī)劃

適用范圍：重疊子問題+最優(yōu)子結(jié)構(gòu)

例子：最大路徑逢慌，背包問題悠轩，字符串編輯距離

遞歸轉(zhuǎn)非遞歸

尾遞歸：函數(shù)的最后一個動作是調(diào)用函數(shù)本身的遞歸函數(shù)，本質(zhì)即自動累積攻泼。
:arrow_right: 尾遞歸僅占用常量椈鸺埽空間。命令式語言可對其優(yōu)化忙菠，不會出現(xiàn)棧溢出何鸡；而函數(shù)式語言可靠尾遞歸來實現(xiàn)循環(huán)。

機械的遞歸轉(zhuǎn)換

設(shè)置工作棧保存工作記錄牛欢；設(shè)置(t+2)個語句標號骡男；增加非遞歸入口；替換規(guī)則傍睹；為所有出口增加語句goto隔盛；多的語句；改寫循環(huán)和嵌套中的遞歸拾稳；優(yōu)化處理(消除冗余吮炕，消去goto)；

二叉樹訪問應(yīng)用

• 前序

  看到一個結(jié)點访得，訪問它龙亲，并把非空右子結(jié)點壓棧，然后深度遍歷其左子樹。
  左子樹遍歷完畢俱笛，彈出結(jié)點并訪問捆姜，繼續(xù)遍歷（左子樹完畢就出棧）。
  開始時推入一個空指針作為監(jiān)視哨迎膜，即歷結(jié)束標志泥技。

  while(pointer){
      visit(pointer);
        if(pointer->rightson!=NULL) 
        tempStack.push(pointer->rightson);
        if(pointer->leftson!=NULL) 
        pointer=pointer->leftson;
        else pointer=tempStack.pop();
  }
  

• 中序

  遇到一個結(jié)點則入棧并遍歷其左子樹，遍歷完左子樹后入棧并訪問之磕仅，最后遍歷右子樹珊豹。

  while(!tempStack.empty()||pointer){   //attention
      if(pointer){
          tempStack.push(pointer);
          pointer=pointer->leftchild;
      }
        else{
          pointer=tempStack.pop();
            visit(pointer);
          pointer=pointer->rightson();
      }
  }
  

• 后序

  遇到一個結(jié)點，將其入棧榕订，遍歷其左子樹店茶；左子樹遍歷結(jié)束后，還不能馬上去辦訪問棧頂結(jié)點劫恒，而是按照其右鏈去遍歷其右子樹贩幻。右子樹遍歷后才能從棧頂托出該結(jié)點訪問。

  需要給棧的每個元素附上一個特征位两嘴，一邊從棧頂托出一個結(jié)點時區(qū)分是從左回來還是從右回來丛楚。

  while (!aStack.empty() || pointer) {
      if (pointer != NULL) {      //沿非空指針壓棧，并左路下降
           element.pointer = pointer; 
           element.tag = Left;   
           aStack.push(element);    //把標志位為Left的結(jié)點壓入棧
           pointer = pointer->leftchild;
       }
       else{  
           element = aStack.pop(); //獲得棧頂元素憔辫，并退棧
           pointer = element.pointer;
           if(element.tag == Left){//如果從左子樹回來
            element.tag = Right; 
            aStack.push(element);//置標志位為Right
              pointer = pointer->rightchild;
            }
            else { 
            Visit(pointer);    //如果從右子樹回來, 訪問當前結(jié)點
               pointer = NULL;    //置point指針為空趣些，以繼續(xù)彈棧
                 }
         }
  

• 總結(jié)：在各種遍歷，每個結(jié)點都只被訪問1次贰您，時間代價是O(1)坏平。

樹

數(shù)據(jù)庫的有關(guān)算法和樹高度相關(guān)。B+樹解決的是集合的排序問題锦亦。由于樹的復(fù)雜度一般為O(logn)舶替，能夠提高搜索的性能，因而廣泛應(yīng)用孽亲。

基本術(shù)語：
有序樹：兄弟間有大小關(guān)系（左大右锌泊）；度為2且嚴格區(qū)分左右兩個子結(jié)點的有序樹才是二叉樹返劲。
森林：一些樹的集合玲昧，一般加入一個結(jié)點作為根，將森林轉(zhuǎn)換成樹篮绿。

Note: 樹或森林與二叉樹一一對應(yīng)孵延。樹所對應(yīng)的二叉樹中，一個結(jié)點的左子結(jié)點是它在原來樹里的第一個子結(jié)點亲配；右子結(jié)點是它在原來的樹里的下一個兄弟尘应。==左孩子惶凝，右兄弟==;(兄弟拉拉手，父親和非大兒子斷絕關(guān)系犬钢，以根為軸旋轉(zhuǎn)得到樹)

圖片5.png

樹的周游

1. 先根次序深度周游：訪問根結(jié)點苍鲜，從左到右依次遍歷根結(jié)點的每一棵子樹。周游樹正好對應(yīng)相應(yīng)二叉樹的前序周游玷犹。

   樹的前序訪問某根結(jié)點：1. 先訪問大兒子 2. 再訪問大兒子的兒子兄弟們 3. 最后訪問大兒子的兄弟

   ? :black_circle: //看圖自己對應(yīng)一下
   ? / |
   :white_circle: :white_circle: :white_circle:
   :small_red_triangle: :small_red_triangle: :small_red_triangle:

2. 后根次序深度周游：從左到右依次后根遍歷根結(jié)點的每一棵子樹混滔，訪問根結(jié)點。周游樹正好對應(yīng)相應(yīng)二叉樹的中序周游歹颓。

   template <class T>
   void Tree<T>::RootLastTraverse (TreeNode<T>* root){
    while (root !=NULL) {           //周游頭一棵樹樹根的子樹   
        RootLastTraverse(root>LeftMostChild());         
            Visit (root->Value());     //訪問當前結(jié)點
        root=root->RightSibling(); //周游其他的樹
    }
   }
   

3. 寬度周游：BFS層次周游坯屿。

Note: 沒有中序，因為子樹個數(shù)不定巍扛，無法定義行為领跛。

鏈式存儲

• 子結(jié)點表示法
  結(jié)點數(shù)組順序儲存，按索引存儲父親結(jié)點撤奸，引出孩子鏈表吠昭。
  優(yōu)點：查孩子個數(shù)的結(jié)點的值容易；
• 動態(tài)節(jié)點表示法
  指針數(shù)組法
  指針鏈表法
• 靜態(tài)”左孩子/右兄弟”表示法

Note: 建議自己實現(xiàn)相應(yīng)ADT寂呛。

父指針表示法及在并查集中的應(yīng)用

父指針表示法：用數(shù)組存儲樹的所有結(jié)點怎诫，同時在每個結(jié)點中附設(shè)一個“指針”指示其父結(jié)點的位置。

==并查集==
一種特殊集合贷痪，由不相交子集構(gòu)成。(解決等價類問題)
基本操作有Find(){判斷兩個結(jié)點是否在同一個集合中}和Union(){歸并兩個集合}
優(yōu)點：尋找父結(jié)點只需要O(1)時間蹦误，求樹根結(jié)點也很方便劫拢。
缺點：尋兄弟結(jié)點需查詢整個樹結(jié)構(gòu)，無序强胰。

優(yōu)化算法
同時使用時舱沧，F(xiàn)ind()和Union()都是$O(\alpha(n))$的。
這是一個增長緩慢的Ackermann函數(shù)偶洋，可認為$\alpha(n)$是一個小于5的常數(shù)熟吏。

• 重量權(quán)衡合并規(guī)則
  把size小的加入size大的樹中，以把樹的整體深度控制在O(logn)
  當然這是在node里面有size屬性的前提下...

• 路徑壓縮算法
  尋找根結(jié)點的時候順便把父親設(shè)置成最老根（代表元）玄窝。

順序存儲

出發(fā)點：硬盤存儲鏈表需要多次隨機訪問牵寺，時間開銷大，因而需要一個順序存儲來提高訪問效率恩脂。

• 帶右鏈的<u>先根次序</u>表示法 ltag info rlink

• 帶雙標記位的先根次序表示法 ltag info rtag
  用棧的結(jié)構(gòu)帽氓，有兄弟就入棧，無孩子就出棧俩块。

• 帶<u>度數(shù)</u>的<u>后根次序</u>表示法 info degree
  用棧的結(jié)構(gòu)黎休，從左往右遇到度為零的入棧浓领，遇到度非零的出棧再入棧生成樹。

• 帶度數(shù)的先根次序

• 帶度數(shù)的層次次序

• 帶雙標記的層次次序

  用隊列的結(jié)構(gòu)势腮，有左兒子入隊列联贩，無右兒子的元素的下一個是隊頂元素的兒子，出隊列捎拯。關(guān)鍵是處理ltag=0的情況泪幌。

K叉樹

略

擴展閱讀：[Kd-tree](file:///D:/course/grade%20two/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/PPT/kd-tree.pdf); [Quadtree](file:///D:/course/grade%20two/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/PPT/quad-tree.pdf);[Unionfind](file:///D:/course/grade%20two/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/PPT/quad-tree.pdf);[Treemining](file:///D:/course/grade%20two/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/PPT/treemining.pdf) 并查集課程

圖

定義：G(V,E) Graph, Edge, Vertex, |X|:sum of X;

/*ADT*/
 class edge{};
 class graph{};

分類：稀疏圖/密集圖，完全圖玄渗，無向圖/有向圖座菠，標號圖(with names)，帶權(quán)圖

相關(guān)概念：neighbours, degree (in degree, out degree...), leaf, subgraph, path藤树；

連通性：有根圖 (存在可達其他頂點的頂點的有向圖)浴滴，連通圖 (任意兩個頂點都連通的無向圖)，連通分量 (無向圖的最大連通子圖)岁钓，強連通性 (任意兩個頂點都有有向路徑的有向圖)升略，強連通分量 (有向圖強連通的最大子圖)，網(wǎng)絡(luò) (帶權(quán)的連通圖)屡限，自由樹 (不帶簡單回路的連通無向圖品嚣，具有|V|-1條邊)

圖的存儲結(jié)構(gòu)：

• 相鄰矩陣
  空間代價O(|V|²)，不適合稀疏圖钧大；
  ?A[i][j]=k :left_right_arrow: i到j(luò)有一條權(quán)為k的有向路徑翰撑，行表示出度，列表示入度啊央；
  易于判斷任意元素的連通性眶诈；
• 鄰接表
  頂點表+邊鏈表，無向圖空間代價O(|V|+2|E|)瓜饥，有向圖空間代價O(|V|+|E|)分為出邊表和入邊表逝撬；
• 十字鏈表
  頂點表：對應(yīng)圖的頂點，由data域,first_in_arc,first_out_arc組成乓土；
  邊鏈表：對應(yīng)有向圖的每一條邊宪潮，由from_vex,to_vex的定點序號,邊權(quán)值的info域,from_next_arc指針指向下一個以from_vex為起點的邊，to_next_arc指針指向下一條以to_vex為終點的邊趣苏；

圖的周游

周游(graph traversal)是求解圖的連通性狡相、拓撲排序和關(guān)鍵路徑等問題的基礎(chǔ)。

典型算法：從一個頂點出發(fā)拦键，訪問其余頂點谣光，考慮<u>非連通圖</u>和<u>存在回路</u>的圖，設(shè)置標志位芬为。

• 深度優(yōu)先(DFS)

  每一條邊處理一次萄金，每個頂點訪問一次（無向圖的每條邊從兩個方向處理）
  鄰接表：有向圖O(|V|+|E|)蟀悦，無向圖O(|V|+2|E|)
  相鄰矩陣：O(|V|²)

• 廣度優(yōu)先(BFS)
  隊列處理，與DFS的區(qū)別僅僅在于訪問順序

• 拓撲排序
  先決條件：以某種線性順序來組織多項任務(wù)氧敢，以便能夠在滿足先決條件的情況下逐個完成各項任務(wù)(<u>有向無環(huán)圖</u>DAG可以模擬先決條件)
  拓撲排序：將一個有向無環(huán)圖中所有頂點在不違反先決條件關(guān)系的前提下排成線性序列的過程稱為拓撲排序日戈，其形成的序列稱為拓撲序列，不唯一
  方法：從圖中選擇一個入度為０的頂點并輸出孙乖，在圖中刪掉此頂點及其所有的出邊(出邊關(guān)聯(lián)頂點的入度減一)浙炼，迭代；環(huán)路存在時仍有頂點沒有被輸出但找不到入度為0的頂點

  • BFS-TopSort()
    建立“入度表”輔助唯袄，表示各節(jié)點入度弯屈；取出所有入度為0的（當父親）入隊，隨著pop()恋拷，更改pop()出元素的相鄰元素入度
    廣度優(yōu)先排序可以判定環(huán)是否存在

  • DFS-TopSort()
    先訪問子孫资厉，再訪問父親，使用類似后根遍歷的算法來實現(xiàn)蔬顾。缺點就是DFS無法看出環(huán)宴偿，用backward_edge來判斷

最短路徑問題

帶權(quán)圖的最短路徑問題：求兩個頂點間長度最短的路徑；

廣度優(yōu)先遍歷本質(zhì)上就是單位權(quán)重圖的最短路徑搜索問題诀豁；

稀疏圖反復(fù)做Dijkstra算法來求每對頂點的最短距離其實比較合適窄刘；

• Dijkstra算法(單元最短路徑，邊權(quán)非負下的最好算法)

  貪心思想：每次都選最優(yōu)的
  具體操作：每次從距離已生成最短路徑的結(jié)點集“一步之遙”的節(jié)點中選擇據(jù)原點最近的邊進行延伸
  證明算法的正確性：否定其他可能性

  這門課的算法和上機作業(yè)的都是基于數(shù)據(jù)是一種內(nèi)存的數(shù)據(jù)結(jié)構(gòu)（存在連接鏈表的）舷胜。實際情況下圖太大了娩践，必須用文件來存。文件是線性的烹骨。無論是連接鏈表還是矩陣欺矫，都不能直接有。不能保證鄰居在該行附近展氓，對于文件執(zhí)行Dijkstra效率會異常低。

  鄒磊研究組：大圖數(shù)據(jù)管理

• Floyd算法(O(n³)脸爱，適合稠密圖)

  基本想法：adj^k[i][j]=從V_i到V_j中間頂點序號不大于k的最短路徑長度遇汞，最后adjⁿ將包括任意兩點間的最短路徑；
  動歸思想：中間不經(jīng)過V_k簿废，則adj^k[i][j]=adj^k-1[i][j]空入，中間經(jīng)過V_k ，則adj^k[i][j]=adj^k-1[i][k]+adj^k-1[k][j]族檬；那么循環(huán)時使adj^k取二者最小值即可歪赢；滿足遞推公式的最優(yōu)子結(jié)構(gòu)和可重復(fù)利用的重疊子結(jié)構(gòu)；
  確定路徑：路徑矩陣单料，只記錄A到B的倒數(shù)第二步走哪個結(jié)點埋凯，否則置-1点楼；

最小生成樹

亦稱最小支撐樹-Minimum-cost Spanning Tree，對于帶權(quán)的連通無向圖G白对，其最小支撐樹是一個包括G的所有頂點和部分邊的圖掠廓，這部分的邊使圖具有連通性且邊權(quán)值綜合最小甩恼；

實際例子如城市間修公路使各個城市連通蟀瞧；

之所以是樹，是‘因為如果存在環(huán)結(jié)構(gòu)則打掉一條邊亦滿足連通性条摸；

• Prim算法(類似Dijkstra)

  步驟：從圖中任意一個頂點開始把它包括在MST中悦污，然后把端點一個在MST一個不在MST的==邊==中找權(quán)最小的任一條邊，并把邊和另一個端點也拉進MST钉蒲，如此迭代至所有點生成

  證明：反證法
  

  圖片6.png

• Kruskal算法(O(|E|ln|E|)切端，適合稀疏圖)

  步驟：開始時將頂點集分為[V]個等價類，每個等價類包括一個頂點子巾；然后以權(quán)的大小順序處理各邊帆赢，如果某條邊鏈接兩個不同等價類的頂點則其加到MST并把兩個等價類合并為一個；反復(fù)執(zhí)行直到剩下一個等價類线梗；

可以參考《算法導(dǎo)論》來看圖論相關(guān)內(nèi)容椰于；比較復(fù)雜；

內(nèi)排序

• 內(nèi)部排序(Internal Sorting) 待排序記錄少仪搔，放在內(nèi)存瘾婿，排序過程在內(nèi)存進行；
• 外部排序(External Sorting) 待排序記錄數(shù)大烤咧，內(nèi)存無法容納所有記錄偏陪，排序過程中還需要訪問外存。后序課程如數(shù)據(jù)庫概論會涉及這樣的問題煮嫌。核心問題就是如何減少io次數(shù)笛谦；

簡單排序 O(n²) - 插入排序，基于二分查找的插入排序昌阿，選擇排序(不穩(wěn)定)饥脑，冒泡排序(穩(wěn)定)

對于循環(huán)體的i，插入排序就是排好前i-1個然后插入第i個懦冰；冒泡排序是依次讓第i個元素成為i~n里面最小的灶轰；選擇排序是找到最小的和第i個直接交換。

基本概念：記錄 Record,關(guān)鍵碼 Key...

穩(wěn)定算法與不穩(wěn)定算法：若記錄序列中的任意兩個記錄R_x,R_y的關(guān)鍵字K_x,K_y刷钢，如果在排序之前和排序之后的<u>相對位置</u>保持不變笋颤，則這種排序方法是穩(wěn)定的，否則是不穩(wěn)定的内地。

時間代價：記錄的比較合交換次數(shù)伴澄；空間代價：所需附加空間的大小

Shell 排序

又稱縮小增量排序赋除，用逆置換的個數(shù)來確定排序；

1959年由D.L.Shell提出秉版，插入排序每次只能改變一個逆序贤重，但是Shell排序一次可以改變好幾個逆序——這說明它是不穩(wěn)定的；

Shell最初提出的增量序列是d₁=[n/2],d_i+1=[d_i/2]清焕；這個做法不大好并蝗，因為很有可能奇偶的下標有一定規(guī)律；因此用互質(zhì)的增量序列效果可能會更好秸妥；Hibbard增量序列{2^k-1,2^k-1-1,...,1}滚停，如此效率可達$\Theta(n^{\frac3 2})$，當然還有其他的粥惧；

1. 選定一個間隔增量序列(n>d₁>...>d_t=1)
2. 將文件按d₁分組（彼此間距為d₁的記錄劃為一組）键畴，在各組采用直接插入法進行排序。
3. 分別按d₂,...,d_t重復(fù)上述分組和排序工作突雪。

分治算法

• 快速排序

基于分治思想起惕，類似二叉搜索樹，最佳性能是O(nlnn)->此時二叉樹高度最低咏删，最差性能是O(n²)->此時二叉樹是一條鏈惹想；

具有普適性的算法分析應(yīng)該如下：

$T_n=\frac 1 n \sum^{n-1}{i=0}(T_i+T{n-1-i}+cn)=\frac 2 n \sum^{n-1}{i=0}T_i+cn \nT_n-(n-1)T{n-1}=2T_{n-1}+2cn-c\\frac {T_n } {n-1}=\frac {T_{n-1}} {n} +\frac {2c} {n+1} $

1. 軸值選擇-pivot，舉手督函；
2. 序列劃分-參考課件
3. 遞歸排序-對子序列進行遞歸劃分直到僅含1/0個元素嘀粱；

• 歸并算法

  先劃分再歸并

  歸并——兩個有序的數(shù)組，只需兩個指針從頭往后跑辰狡；有一定的空間代價锋叨；

  穩(wěn)定

• 堆排序

非穩(wěn)定排序，理論上時間代價$\Theta (nlnn)$

1. 對所有記錄建立最大堆
2. 取出堆頂元素放到數(shù)組末尾宛篇，然后把堆尾的丟到堆頭再調(diào)整娃磺；

分配排序

這些算法的基本想法都是比較和交換；這種想法的排序方法不能再低于nlnn了叫倍；另一種idea是分配和收集豌鸡；前提是必須知道所有記錄值固定在某區(qū)間；

• 桶排序 Bucket Sorting : 先分配段标，再收集
  注意桶計數(shù)和排序序列的映射關(guān)系——需要把計數(shù)器簡單處理為下標指示，再從后往前把蘿卜填坑炉奴；這一點是因為排序規(guī)則可以自定義逼庞，從后往前排序能夠保持穩(wěn)定性，可以有更多的操作空間瞻赶；
  O(m+n)赛糟，只適合m比較小的情況派任；

• 基數(shù)排序
  高位優(yōu)先法(MSD)
  低位優(yōu)先法(LSD) 同上，更易為計算機接受璧南；

  基于數(shù)組的基數(shù)排序空間開銷比較大掌逛，可以用靜態(tài)鏈來改進。這樣子不需要移動記錄本身司倚，只需要修改記錄的next指針豆混，O(d(n+r))——實際上是O(nlogn)。

• 索引排序/地址排序
  記錄規(guī)模很大時动知，減少記錄移動次數(shù)以降低排序時間皿伺。例子：pagerank；
  關(guān)鍵點就是基于index直接在原有數(shù)組上排序盒粮。取一個tmp流出一個空鸵鸥，再順著空當對應(yīng)index來塞。

排序問題的界

Lower Bound: 解決排序問題能達到的最佳效率丹皱，即使尚未設(shè)計出算法妒穴。

Upper Bound: 已知最快算法所達到的最佳漸進效率。

排序問題的下限應(yīng)該在$\Omega(n)-\Omega(nlogn)$之前摊崭。

外排序

引言： 內(nèi)存是一種有限的存儲資源讼油，需要解決外存文件的排序問題。

比賽： Sort Benchmark 100TB in 134s

訪問外存比訪問內(nèi)存慢5~6個數(shù)量級爽室，(10^-3,10^-9)汁讼；

核心思想是減少IO；

外存訪問分為定位和存取兩個階段阔墩；內(nèi)存被劃分為長度固定的存儲空間嘿架；數(shù)據(jù)訪問以block塊為單位進行，從而減少外存的定位次數(shù)啸箫，進而減少外存讀寫的時間耗費耸彪。

基本過程：

1. 置換選擇排序（目的是把外存初始化為盡可能長的有序順串集，手法為堆排序）忘苛；
2. 歸并排序（目的是把順串集合逐趟歸并排序蝉娜，形成全局有序的外存文件，手法是k叉哈夫曼樹）扎唾；

m順串個數(shù)召川，每次對k個順串歸并，歸并趟數(shù)[log_km]胸遇，n-1 個元素荧呐，做k-1次比較，

勝者樹，敗者樹

檢索

在記錄中找到“A[key]==value”倍阐，主要操作就是關(guān)鍵碼的比較概疆。

平均搜索長度(average search length,AVL)

提高檢索效率的方法 - 預(yù)排序，建立索引峰搪，散列技術(shù)

分類 - 線性表（順序岔冀，二分），關(guān)鍵碼值（下標）概耻，樹索引（二叉使套，B樹），屬性（倒排表咐蚯，倒排文件）

哈希方法

用一個確定的函數(shù)H和待檢索的關(guān)鍵碼K確定記錄的存儲地址 $Address=Hash(Key)$

負載： $\alpha=\frac n M$ , n:散列表中已有結(jié)點數(shù)童漩，M散列表空間大小

沖突： 將不同的關(guān)鍵碼映射到相同的散列地址（實際應(yīng)用中不產(chǎn)生沖突的極少存在）

同義詞： 產(chǎn)生沖突的關(guān)鍵值碼

兩個重要問題：

1. 散列函數(shù)的構(gòu)造 - 使結(jié)點“均勻分布”，盡可能降低沖突現(xiàn)象發(fā)生的概率
2. 沖突解決的方法

散列函數(shù)的選取原則：

1. 運算簡單
2. 函數(shù)值在散列表范圍內(nèi)[0,M-1]
3. 關(guān)鍵碼不同時，盡可能使其散列值也不相同
4. 圖片7.png

常用方法：取余法(缺點在其連續(xù)性導(dǎo)致沖突處理性能下降)，乘余取整(亂湊)屹耐，平方取中(比較均勻)，數(shù)字分析侧馅，基數(shù)轉(zhuǎn)換，折疊呐萌，ELFhash字符串散列函數(shù) - 可參考《算導(dǎo)》

• 沖突的解決方法

  1. 內(nèi)存：開散列方法（拉鏈法）——所有同義詞鏈接在同一個鏈表馁痴。
  2. 外存：閉散列方法（開地址法）——把發(fā)生沖突的關(guān)鍵碼存儲在散列表中另一個空地址。

  探測序列-由探測函數(shù)決定：線性肺孤，二次罗晕，偽隨機數(shù);

索引

主碼(primary key)：數(shù)據(jù)庫中每條記錄的唯一標志

輔碼：數(shù)據(jù)庫中可出現(xiàn)重復(fù)值的碼；輔碼索引把一個輔碼值與具有這個輔碼值的多條記錄的主碼值關(guān)聯(lián)起來

主要思想：通過索引文件去訪問主文件的數(shù)據(jù)

• 線性索引 - 按照==索引碼值==的順序進行排序的文件
  缺點在于不適合動態(tài)分析（大量插入刪除時可能有O(n)）

• 靜態(tài)索引 - 文件創(chuàng)建時固定赠堵，后面的插入刪除操作單獨放在溢出區(qū)處理

  實際上是二叉樹轉(zhuǎn)換為多叉樹 small | large => binary tree

• 倒排索引 - 從==屬性值==到記錄(attr,ptrList)
  支持基于屬性的高效檢索小渊，但花費了保存倒排表的存儲代價，降低了更新運算的效率

  正文索引

  • [詞索引] 對正文文件的倒排 - 正文索引 =>詞索引茫叭，全文索引

    1. 對文檔集中的所有文件都進行分割處理酬屉，把正文分成多條記錄文檔；

    2. 給每條記錄賦關(guān)鍵詞

       以人工或自動的方式從記錄中抽取關(guān)鍵詞揍愁，利用stopword呐萨，抽詞干和切詞。
       3. 建立正文倒排表莽囤、倒排文件

       得到各個關(guān)鍵詞的集合谬擦，對于每個關(guān)鍵詞得到其倒排表，然后把所有的倒排表存入文件朽缎。

  • [正文索引] n-gram(commonly n=3)

• 動態(tài)索引

  信息檢索處理文檔怯屉，數(shù)據(jù)庫處理表格

  • B樹
    m階B樹是一顆m路查找樹/空樹蔚舀，2-3樹是它的一個特殊情況，m是由io時能得到的page決定的锨络。
  • B+樹

• 位索引技術(shù) bitmap

  對屬性值定類(取值范圍)建立一個向量記錄"是否取某個取值"s
  也可以應(yīng)用于文本 Signature file,性能不如倒排索引

  按列存儲

紅黑樹

出發(fā)點: 建立一個保證插入/搜索/刪除都是log(n)的；

定義：只有紅色和黑色狼牺，首尾都是黑色羡儿，紅的兒子都是黑，對任意子樹的根black_height都一樣是钥；

性質(zhì)：滿二叉樹掠归；k階紅黑樹簡單路徑長度介于[k,2k]；內(nèi)部結(jié)點最少時是完全滿二叉樹(全黑)悄泥，最少時是2^k-1的內(nèi)部結(jié)點數(shù)虏冻；<u>n個內(nèi)部結(jié)點的紅黑樹的最大高度是2log₂(n+1)+1</u>;

旋轉(zhuǎn)操作不改變black_height

? B A

? A $\delta$ $\alpha$ B

? $\alpha$ $\beta$ $\beta$ $\delta$

idea: 當插入一個結(jié)點(默認為紅)，如果其父親是紅弹囚，則矛盾厨相，通過旋轉(zhuǎn)和重新著色來調(diào)整。此時因為父親是紅鸥鹉，爺爺肯定是黑蛮穿，需要考慮的是z / z.p.p / z.p.p.r / z.p.p.l

插入 (基于檢索失敗的搜索)算法步驟:

while 考察結(jié)點(固定是紅)的爸爸是紅色的且不是根

1. if(叔叔紅)——爸爸輩兩個紅的拱著一個黑的——換一下上下顏色，再往上調(diào)整毁渗，考察爺爺践磅；continue；
2. 扭曲"<,>"兩紅爺爺黑——不用理叔叔——旋轉(zhuǎn)變成case3灸异，讓z上移府适，考察z的原生爸爸；
3. 單邊"/,"兩紅爺爺黑——不用理叔叔——旋轉(zhuǎn)爺爺爸爸肺樟，讓爸爸變黑爺爺變紅檐春；break;

把根涂黑；

刪除 (前驅(qū)和后繼)

case 1: 待刪除的結(jié)點沒有兒子——直接刪除儡嘶，y=待刪結(jié)點

case 2: 待刪除結(jié)點只有一個兒子——調(diào)換后繼和父親喇聊，y=待刪結(jié)點，x=兒子

case 3: 待刪除結(jié)點有兩個兒子——用后繼來代替它蹦狂，相應(yīng)調(diào)整誓篱，y=后繼，x=后繼兄弟

對一個后繼就是右子樹的左盡頭

紅黑樹的葉子結(jié)點都是補充了兩個黑色NIL兒子的

紅黑樹性質(zhì)保持：

1. y.color == RED √
2. y.color == BLACK
   1. y是root凯楔，y的紅色兒子有可能成為root
   2. x == RED && y.p == RED
   3. 路徑少了1個黑

出口: ① x指向一個 R-B窜骄，把這個點設(shè)為黑；

? ② x指向一個root摆屯，直接把root設(shè)為黑邻遏；

while(y.color==BLACK)

1. x.bro==R, 旋轉(zhuǎn)兄弟和父親糠亩，轉(zhuǎn)到以下情況

2. x.bro==B

   1. x.bro有兩個黑兒子
      ① x.p==R -> x指向R-B，將x設(shè)為黑准验，結(jié)束

   ② x.p==B -> "雙黑"赎线，轉(zhuǎn)到以下情況

   2. x.bro左紅右黑——紅侄子旋轉(zhuǎn)壓制兄弟，原兄弟變黑糊饱，轉(zhuǎn)到3

   3. x.bro左黑右紅——

高級數(shù)據(jù)結(jié)構(gòu)

• 最佳(基于用戶訪問習(xí)慣垂寥，靜態(tài))
• 平衡(基于樹高平衡約束，經(jīng)常修改)
• 伸展樹(基于用戶動態(tài)訪問特征)

一個擁有n個關(guān)鍵碼的集合另锋，只有Catalan(n)種前序排列可以構(gòu)成二叉搜索樹滞项。

root:=k, cnt(k)=f(k-1)f(n-k) -> S(n)=cnt(1)+...+cnt(n)=Catalan(n)

最優(yōu)搜索樹

$ASL(n)=\frac {\sum_i p_i(l_i+1)+\sum_iq_il_i'}W$

p_i：檢索第i個內(nèi)部結(jié)點的的頻率
q_i：檢索關(guān)鍵碼處于第i和第i+1內(nèi)部結(jié)點間的頻率
l_i：第i個內(nèi)部結(jié)點的層數(shù)
l_i'：第i個內(nèi)部結(jié)點的層數(shù)

最佳BST樹構(gòu)造方法(靜態(tài))
利用性質(zhì): 最佳的BST樹任意子樹都是最佳二叉搜索樹
DP: C(i,j)=W(i,j)+min_i<k≤j(C(i,k-1)+C(k,j))

AVL樹

$\forall T_i \in T, bf(T_i)=|h_{R(T_i)}-h_{L(T_i)}|\le1 \Rightarrow h_T=O(logn)$

bf(x): 結(jié)點x的平衡因子
N_h=min(|node| in AVL with height=h) => N₁=1,N_h=1+N_h-1+N_h-2
=> $h<log_{\frac{1+\sqrt 5} 2} n≈1.44\ O(logn)$

建樹

不斷插入，必要時平衡化

插入

1. 維持AVL性質(zhì)(雖一大一小但沒有犯規(guī)/正好填坑)
2. 破壞AVL性質(zhì)——從新加入的結(jié)點向根往上搜索夭坪，直到發(fā)現(xiàn)==最近的不平衡祖先==
   1. LL,RR——單旋轉(zhuǎn)——直接轉(zhuǎn)
   2. LR,RL——雙旋轉(zhuǎn)——提升中間結(jié)點兩次

AVL sorting O(nlogn) -> f(){build_AVL_tree(); in_order_traversal();}

刪除

初步和BST類似文判，與后繼交換再刪除。但是刪除會導(dǎo)致樹高和平衡因子變化室梅，需要沿著被刪除結(jié)點到根節(jié)點的路徑來調(diào)整戏仓。

1. bf(root)==0——不用管
2. bf(root)!=0
   1. 砍高個兒——更新bf(root)=0，向上修改
   2. 砍矮個兒
      1. 陣亡兄弟平衡——轉(zhuǎn)陣亡兄弟和爸爸
      2. root另一邊和自己左右情況一樣——轉(zhuǎn)陣亡兄弟和爸爸竞惋，向上修改
      3. root另一邊和自己左右情況不一樣——轉(zhuǎn)陣亡兄弟的矮兒子到root

伸展樹

數(shù)據(jù)訪問“28原則”：80%的人只會用到20%的數(shù)據(jù)柜去；

伸展樹提供一個新的規(guī)則，保證訪問總代價不高拆宛，O(mlogn)嗓奢，但不保證樹的平衡。訪問誰就轉(zhuǎn)誰浑厚。轉(zhuǎn)到根股耽。

半伸展樹——把根到訪問結(jié)點路徑上的結(jié)點從下到上雙旋轉(zhuǎn)

注意：外部結(jié)點

多維數(shù)組

廣義表

L=（x₀,x₁,...,x_n-1)，每個x_i是L的成員钳幅，可以是單個元素(原子)物蝙，也可以是一個廣義表（字表)。廣義表是一種嵌套結(jié)構(gòu)敢艰，本質(zhì)上是樹诬乞，廣義表深度指所有元素都化解為原子后的括號層數(shù)，也就是數(shù)的層數(shù)钠导。

圖 -> 再入表 -> 純表 -> 線性表

表頭：第一個元素震嫉；表尾：整個表刪去表頭元素(保留外層括號)

純表：從根節(jié)點到任何葉節(jié)點只有一條路徑。是一棵樹牡属。

可重入表(再入表)：元素可能在表中多次出現(xiàn)票堵，對應(yīng)于一個有向無環(huán)圖。

圖片8.png

循環(huán)表：包含回路逮栅，深度∞悴势。

圖片9.png

Trie樹

基于比較的搜索樹窗宇。讓<u>搜索空間的劃分與元素本身無關(guān)</u>√叵耍基于兩個原則：關(guān)鍵碼集合固定军俊，對結(jié)點分層標記。這樣子捧存，查找一個關(guān)鍵字的時間僅與組成關(guān)鍵字的字符數(shù)有關(guān)蝇完。

葉子都是'$',NULL亦可。

變種：PATRICIA樹-以二進制來劃分矗蕊。