课程介绍

先修课：概率统计，程序设计实习，集合论与图论

后续课：算法分析与设计，编译原理，操作系统，数据库概论，人工智能，图形图像，Web信息处理

​ "数据结构和算法是衡量计算机科班出身的重要标准。值得花大功夫去学。"

课程特点：基础性+理论性+实践性+挑战性

教学要求：

​ 预习自学+可讨论不抄袭+加强训练+有效反馈

​ 书面作业：写学号名字，每次都在文本写上"我保证没有抄袭别人作业"；

课程网站：www.chinesemooc.org ;course.pku.edu.cn

课程评估：平时40（书面考勤15，慕课25），考试60（期中18，机考18，期末24）;

数据结构

数据结构 ：设计数据之间的逻辑关系、数据在计算机中的存储表示和在这种结构上的一组能执行的操作（运算）三个方面。

-逻辑结构： 从具体问题抽象出来的数学模型，反映了事物的组成结构和事物之间的逻辑关系。

• 线性结构： 亦称"前驱关系"。关系r有向，满足全序性（全部结点两两皆可比较前后）和单索性（每个结点皆有前驱和后继结点）等约束条件。
• 树形结构： 亦称"层次结构"，每个节点可有多于一个后继结点，但只有唯一的直接前驱。
• 图形结构： 有时称为结点互联的网络结构，对关系r没有加任何约束。

-存储结构： 也称物理结构，是逻辑结构在计算机中的物理存储表示。

• 四种基本存储映射方法：顺序、链接、索引、散列

自顶向下的逻辑结构分析设计方法

算法

​ 分类：穷举，回溯，贪心，递归，动态规划，分治

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。不同的出栈次序有几种?
我们可以这样想，假设k是最后一个出栈的数。比k早进栈且早出栈的有k-1个数，一共有h(k-1)种方案。比k晚进栈且早出栈的有n-k个数，一共有h(n-k)种方案。所以一共有h(k-1)h(n-k)种方案。显而易见，k取不同值时，产生的出栈序列是相互独立的，所以结果可以累加。k的取值范围为1至n，所以结果就为h(n)= h(0)h(n-1)+h(1)h(n-2) + ... + h(n-1)h(0)。
卡特兰数：h(n)=C(2n,n)/n+1=C(2n,n)-C(2n,n+1)=h(0)h(n-1)+...+h(n-1)h(0)

表达式求值：中缀表达式转后缀表达式并计算
先转换，输入操作数直接输出到序列，输入左括号时压栈，输入运算符时，如果大于当前栈顶运算发则压栈，不然出栈循环至栈非空栈顶不是左括号且栈中运算符优先级小于当前的优先级再压栈，输入有括号时弹至第一个左括号；再求值，把数字读进栈，碰到运算符就取出俩计算将结果压栈。

• 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];      //动态存储区开辟整数数组
    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值，优化步骤
        else next[i] = k;        
    }
    return next;
}

注意：书里面有挺多错的。P95第一行，如果p[i]≠p[k] 如果p[i]=p[k]。

算法导论17：摊还分析学习笔记-KMP复杂度证明

在摊还分析中，通过求数据结构的一系列的操作的平均时间，来评价操作的代价。这样，即使这些操作中的某个单一操作的代价很高，也可以证明平均代价很低。摊还分析不涉及概率，它可以保证最坏情况下每个操作的平均性能。

摊还分析有三种常用的技术：聚合分析，它确定$n$个操作的总代价的上界为$T(n)$，所以每个操作的平均代价为$\frac{{T(n)}}{n}$。每个操作都有相同的摊还代价。核算法：分析每个操作的摊还代价，不同于聚合分析，每种操作的摊还代价是不同的，核算法将序列中较早的操作的余额作为“信用”储存起来，与数据结构中的特定对象相关联，在随后的操作中，储存的信用可以用来进行支付。势能法：与核算法类似，也是分析每个操作的代价，但将势能作为一个整体存储，而与数据结构中的某个对象无关。

一、聚合分析

以栈操作为例：存在3种操作：1、$push$ 2、$pop$ 3、$multipop$直观地分析复杂度：因为栈的大小最大为$n$，所以$multipop$的最坏情况为$O(n)$，所以，由n个$push$,$pop$,$multipop$组成的操作序列的最坏代价为$O( n^2)$，因为序列可能包含$O(n)$个操作序列。

上面的分析给出的界并不是紧确界，实际上，在一个空栈上执行$n$个$push$, $pop$, $multipop$的操作序列，代价最多为$O(n)$。这是因为，当一个对象压入栈后，至多将其弹出一次。所以，对于一个非空的栈，可以执行的$pop$的次数（包含$multipop$中的$pop$）最多与$push$操作次数一样，即$n$次。所以，对任意的$n$，任意一个由$n$个$push$, $pop$, $multipop$组成的操作序列，最多花费$O(n)$。所以，每个操作的摊还代价为$O(1)$。

二、核函数

核算法，对不同的操作赋予不同的费用，这个费用就是摊还代价。当一个操作的摊还代价超过实际代价的时候，将差额存入数据结构中的特定对象，存入的差额称为信用。对于后续操作中，摊还代价小于实际代价的情况，信用可以用来支付差额。因为希望通过分析摊还代价来说明每个操作的平均代价的很小，所以应该确保$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}} $，所以需要保持数据结构中的总信用永远为非负值。

依然以栈操作为例：下面证明，如果按照摊还代价进行缴费，则可以支付任意的$n$个栈操作序列。在$push$操作时，共缴费2美元，其中1美元支付$push$的实际代价，将剩余的1美元存入插入的元素，作为信用。这样，每个插入的元素都具有1美元的信用。这1美元的信用，实际上是用来支付$pop$操作的预付费。当执行一个$pop$的时候，并不缴额外的费用，而是使用信用来支付实际代价。$multipop$也一样。所以，对任意的n个PUSH, POP, MULTIPOP组成的序列，总摊还代价为实际代价的上界，总摊还代价为$O(n)$。

三、势能法

势能法与核算法类似，但是势能法并不将预付代价表示为数据结构中特定对象的信用，而是表示为“势能”。势能是与整个数据结构相关联，而不是某个特定的对象。将势能释放，就可以支付未来操作的代价。

势能法如下：对一个初始数据结构${D_0}$执行$n$个操作。对于i = 1, 2,...,n， ${c_i}$表示第i个操作的实际代价， ${D_i}$表示在数据结构${D_{i - 1}}$上执行第i个操作得到的数据结构。势函数$\varphi $将每个数据结构${D_i}$映射到一个实数 $\varphi ({D_i})$，这个值就是关联到数据结构的势。所以，第i个操作的摊还代价为${c'i} = {c_i} + \varphi ({D_i}) - \varphi ({D{i - 1}})$。每个操作的摊还代价等于其实际代价加上此操作引起的势能变化。

势能法其实就是核函数的总体分析。

再拿kmp算法失配回退时使用的摊还分析技术：

这个可以用势能分析法来分析：关于匹配指针的位置$cur$，操作A：匹配时，$cur + + $;操作B：失配时，$cur = next[cur - 1]$; (根据不同实现有所出入)这个 $next[cur - 1] < = cur - 1$ 是成立的。

根据势能分析($cur \ge 0$ 恒成立)，我们可以证明，操作A的执行次数一定比操作B要多，两个操作都是$O(1)$。而操作A的执行次数是很容易分析最坏上界是 $O(n)$；那么 $O(n) = T(A) \ge T(B)$，因此匹配时的时间复杂度$T(A + B) = O(n)$ 。

其实上述操作类似于栈操作，直接类比进行复杂度分析即可。

二叉树

二叉树由结点的有限集合构成，要么为空集，要么由一个根结点与两棵不相交的分别称作左子树和右子树的二叉树组成。（递归定义）

n个结点的二叉树有多少种？$f_0=f_1=1$,$f_n=\sum_{i=0}^{n-1}f_{n-i}f_i$

Catalan数：$f_n=\frac{C_{2n}^{n}{n+1}=C_{2n}}n-C_{2n}^{n+1}$

概念：父母parent，子女/孩子children，边edge，兄弟sibling，路径path，祖先ancester，子孙descendant，树叶leaf，内部结点/分支结点internal node，度数degree，层数/二叉树高度level，森林，深度/最长路径长度。

​ 带根的树称为有向树。
​ 如果一棵二叉树的结点或为树叶（0度结点）或E为两棵非空子树（2度结点），则称作满二叉树。
​ 如果一棵二叉树最多只有下面的两层结点度数可以小于2，最下面一层的结点都集中在该层最左边、连续位置上则称此二叉树为完全二叉树。完全二叉树的路径长度和（由根节点到各个结点的路径长度总和）最短。
​ 当二叉树结点出现空指针时，就增加一个特殊结点-空树叶。由此扩充的二叉树叫做扩充二叉树，它是满二叉树，新增加空树叶的个数等于原来二叉树结点个数加一，$Length\ Out=Length\ In+2\ Inner\ Node$。归纳法证明

图片3.png

左子树优先级最大，理解为从左向右为大儿子二儿子等。
树叶指的是没有儿子的结点。
根节点层数为0，其他结点层数等于父母层数加1。
森林即多个二叉树集合，通过引入虚拟结点把问题划归为单二叉树。

n个结点的树有多少条边？

性质

1. 满二叉树定理：非空满二叉树树叶数等于其分支结点数加1，即n₀ = n₂ + 1。
   推论：一个非空二叉树的孔子书数目等于其结点数加一。

   试证明：在具有n个结点的k叉数中，有n(k-1)+1个指针是空的。

2. 任何一棵二叉树度为0的结点n₀比度为2的结点n₂多1个。即n₀ = n₂+1。

3. 二叉树的第i层最多有2ⁱ个结点。高度为k的二叉树至多有2^k-1个结点。有n个结点的完全二叉树高度为[log₂(n+1)]。

周游

二叉树的结点存储所需数据信息，边保持二叉树的结构。操作运算集中在访问二叉树的结点信息上。

/*ADT of binary tree*/
template <class T>
class BinaryTreeNode  {
friend class BinaryTree<T>;                  // 声明二叉树类为友元类
private:
    T  info;                                 // 二叉树结点数据域
public:
    BinaryTreeNode();                        // 缺省构造函数
    BinaryTreeNode(const T& ele);            // 给定数据的构造
    BinaryTreeNode(const T& ele, BinaryTreeNode<T> *l, 
                  BinaryTreeNode<T> *r);     // 子树构造结点
    T  value() const;                       // 返回当前结点数据
    BinaryTreeNode<T>* leftchild() const;    // 返回左子树
    BinaryTreeNode<T>* rightchild() const;   // 返回右子树
    void  setLeftchild(BinaryTreeNode<T>*);  // 设置左子树
    void  setRightchild(BinaryTreeNode<T>*); // 设置右子树
    void  setValue(const T& val);           // 设置数据域
    bool  isLeaf() const;                  // 判断是否为叶结点
    BinaryTreeNode<T>& operator = 
        (const BinaryTreeNode<T>& Node);    // 重载赋值操作符
};
template <class T>
class BinaryTree  {
private:
     BinaryTreeNode<T>* root;                //二叉树根结点
public:
      BinaryTree() {root = NULL;};           //构造函数
      ~BinaryTree() {DeleteBinaryTree(root);};//析构函数
      bool isEmpty() const;                  //判定二叉树是否为空树
BinaryTreeNode<T>* Root() {return root;};     //返回根结点
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);  // 构造树
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); // 删除二叉树
}; 

深度优先周游

图片4.png

注意：已知二叉树的先序和后序序列，不能唯一确定二叉树。

给定先序和后序，二叉树的方案数有几种？约2ⁿ种，根据左右子树的可能来确定。

广度优先周游

#include <queue>
queue <TreeNode> q;

存储结构

• 链式存储(多为一般的树)——二/三叉链表表示法——指针

• 静态数组存储(多为完全二叉树)

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

• 广义的树的线性存储结构

应用

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

  概念 ：对于任意结点值为K，其左子树每一个结点的值都小于K；其右子树任意一个结点的值大于K;且其左右子树也分别为二叉搜索树。
  性质 ：按照中序周游将各个结点打印出来，将得到从小到大的排列。树中结点值唯一。
  评价 ：二叉树的效率就在于只需搜索两个子树之一。在树形比较平衡时，二叉树的搜索效率相当高。
  插入 ：成功的插入基于失败的查找。
  删除 ：: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:

堆与优先队列

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

• 一个关键码序列，满足$K_i\le K_{2i+1},K_i\le K_{2i+2}$ ；
• 堆中储存的数据==局部有序==；
• 是一个可用数组表示的完全二叉树，但不唯一；

建堆：
从堆的最后一个分支结点 heapArray[Size/2-1]开始，自底向上，自右向左逐步把以各分支结点为根的子树调整成堆；

template <class T>   
void MinHeap<T>::SiftDown(int position) {
    int i=position;           //标识父结点
    int j=2*i+1;              //标识关键值较小的子结点
    T   temp=heapArray[i];    //保存父结点
    while (j<CurrentSize){    //过筛
          if ((j<CurrentSize-1)&&(heapArray[j]>heapArray[j+1]))
              j++;           //j指向数值较小的子结点
          if (temp>heapArray[j]){
              heapArray[i]=heapArray[j];
              i=j;   j=2*j+1;//向下继续
          }  else break;
    }
    heapArray[i]=temp;
}

template<class T>   //从position向上开始调整，使序列成为堆
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;
}                  //从叶子节点

插入： 插到最后一个位置，再自底向上调整；

移出最小值： 用最后一个位置代替根结点，再向下调整；

删除元素：用最后一个位置代替待删元素，再向上向下调整；

建堆效率：树的高度是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)$；

优先队列： 可从一个集合中快速查找并移出具有最大值或最小值的元素。堆是优先队列的一种自然实现方法。

Huffman Tree

背景：通信中使用不等长的编码来表示不同使用频率的字符——保证任何字符的编码不是其他字符编码的前缀。可以把编码视为二叉树，叶子分别代表一个字符。往左赋值为0，往右赋值为1。

Huffman Tree： 具有最小带权路径长度的二叉树称作哈夫曼树/最优二叉树。

建立过程： 按照权重把字母排为有序序列，拿走前两个（权最小）标记为Huffman树树叶，将这两个树叶标为一个分支结点的两个子女，而该节点的权即两树叶的权之和。将所得“权”放回序列中适当位置，使“权”顺序保持。重复上述步骤直至序列中剩一个元素，则建立完毕。

习题课

动态规划

适用范围：重叠子问题+最优子结构

例子：最大路径，背包问题，字符串编辑距离

递归转非递归

尾递归：函数的最后一个动作是调用函数本身的递归函数，本质即自动累积。
:arrow_right: 尾递归仅占用常量栈空间。命令式语言可对其优化，不会出现栈溢出；而函数式语言可靠尾递归来实现循环。

机械的递归转换

设置工作栈保存工作记录；设置(t+2)个语句标号；增加非递归入口；替换规则；为所有出口增加语句goto；多的语句；改写循环和嵌套中的递归；优化处理(消除冗余，消去goto)；

二叉树访问应用

• 前序

  看到一个结点，访问它，并把非空右子结点压栈，然后深度遍历其左子树。
  左子树遍历完毕，弹出结点并访问，继续遍历（左子树完毕就出栈）。
  开始时推入一个空指针作为监视哨，即历结束标志。

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

• 中序

  遇到一个结点则入栈并遍历其左子树，遍历完左子树后入栈并访问之，最后遍历右子树。

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

• 后序

  遇到一个结点，将其入栈，遍历其左子树；左子树遍历结束后，还不能马上去办访问栈顶结点，而是按照其右链去遍历其右子树。右子树遍历后才能从栈顶托出该结点访问。

  需要给栈的每个元素附上一个特征位，一边从栈顶托出一个结点时区分是从左回来还是从右回来。

  while (!aStack.empty() || pointer) {
      if (pointer != NULL) {      //沿非空指针压栈，并左路下降
           element.pointer = pointer; 
           element.tag = Left;   
           aStack.push(element);    //把标志位为Left的结点压入栈
           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);    //如果从右子树回来, 访问当前结点
               pointer = NULL;    //置point指针为空，以继续弹栈
                 }
         }
  

• 总结：在各种遍历，每个结点都只被访问1次，时间代价是O(1)。

树

数据库的有关算法和树高度相关。B+树解决的是集合的排序问题。由于树的复杂度一般为O(logn)，能够提高搜索的性能，因而广泛应用。

基本术语：
有序树：兄弟间有大小关系（左大右小）；度为2且严格区分左右两个子结点的有序树才是二叉树。
森林：一些树的集合，一般加入一个结点作为根，将森林转换成树。

Note: 树或森林与二叉树一一对应。树所对应的二叉树中，一个结点的左子结点是它在原来树里的第一个子结点；右子结点是它在原来的树里的下一个兄弟。==左孩子，右兄弟==;(兄弟拉拉手，父亲和非大儿子断绝关系，以根为轴旋转得到树)

图片5.png

树的周游

1. 先根次序深度周游：访问根结点，从左到右依次遍历根结点的每一棵子树。周游树正好对应相应二叉树的前序周游。

   树的前序访问某根结点：1. 先访问大儿子 2. 再访问大儿子的儿子兄弟们 3. 最后访问大儿子的兄弟

   ​ :black_circle: //看图自己对应一下
   ​ / |
   :white_circle: :white_circle: :white_circle:
   :small_red_triangle: :small_red_triangle: :small_red_triangle:

2. 后根次序深度周游：从左到右依次后根遍历根结点的每一棵子树，访问根结点。周游树正好对应相应二叉树的中序周游。

   template <class T>
   void Tree<T>::RootLastTraverse (TreeNode<T>* root){
    while (root !=NULL) {           //周游头一棵树树根的子树   
        RootLastTraverse(root>LeftMostChild());         
            Visit (root->Value());     //访问当前结点
        root=root->RightSibling(); //周游其他的树
    }
   }
   

3. 宽度周游：BFS层次周游。

Note: 没有中序，因为子树个数不定，无法定义行为。

链式存储

• 子结点表示法
  结点数组顺序储存，按索引存储父亲结点，引出孩子链表。
  优点：查孩子个数的结点的值容易；
• 动态节点表示法
  指针数组法
  指针链表法
• 静态”左孩子/右兄弟”表示法

Note: 建议自己实现相应ADT。

父指针表示法及在并查集中的应用

父指针表示法：用数组存储树的所有结点，同时在每个结点中附设一个“指针”指示其父结点的位置。

==并查集==
一种特殊集合，由不相交子集构成。(解决等价类问题)
基本操作有Find(){判断两个结点是否在同一个集合中}和Union(){归并两个集合}
优点：寻找父结点只需要O(1)时间，求树根结点也很方便。
缺点：寻兄弟结点需查询整个树结构，无序。

优化算法
同时使用时，Find()和Union()都是$O(\alpha(n))$的。
这是一个增长缓慢的Ackermann函数，可认为$\alpha(n)$是一个小于5的常数。

• 重量权衡合并规则
  把size小的加入size大的树中，以把树的整体深度控制在O(logn)
  当然这是在node里面有size属性的前提下...

• 路径压缩算法
  寻找根结点的时候顺便把父亲设置成最老根（代表元）。

顺序存储

出发点：硬盘存储链表需要多次随机访问，时间开销大，因而需要一个顺序存储来提高访问效率。

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

• 带双标记位的先根次序表示法 ltag info rtag
  用栈的结构，有兄弟就入栈，无孩子就出栈。

• 带<u>度数</u>的<u>后根次序</u>表示法 info degree
  用栈的结构，从左往右遇到度为零的入栈，遇到度非零的出栈再入栈生成树。

• 带度数的先根次序

• 带度数的层次次序

• 带双标记的层次次序

  用队列的结构，有左儿子入队列，无右儿子的元素的下一个是队顶元素的儿子，出队列。关键是处理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)，带权图

相关概念：neighbours, degree (in degree, out degree...), leaf, subgraph, path；

连通性：有根图 (存在可达其他顶点的顶点的有向图)，连通图 (任意两个顶点都连通的无向图)，连通分量 (无向图的最大连通子图)，强连通性 (任意两个顶点都有有向路径的有向图)，强连通分量 (有向图强连通的最大子图)，网络 (带权的连通图)，自由树 (不带简单回路的连通无向图，具有|V|-1条边)

图的存储结构：

• 相邻矩阵
  空间代价O(|V|²)，不适合稀疏图；
  ​A[i][j]=k :left_right_arrow: i到j有一条权为k的有向路径，行表示出度，列表示入度；
  易于判断任意元素的连通性；
• 邻接表
  顶点表+边链表，无向图空间代价O(|V|+2|E|)，有向图空间代价O(|V|+|E|)分为出边表和入边表；
• 十字链表
  顶点表：对应图的顶点，由data域,first_in_arc,first_out_arc组成；
  边链表：对应有向图的每一条边，由from_vex,to_vex的定点序号,边权值的info域,from_next_arc指针指向下一个以from_vex为起点的边，to_next_arc指针指向下一条以to_vex为终点的边；

图的周游

周游(graph traversal)是求解图的连通性、拓扑排序和关键路径等问题的基础。

典型算法：从一个顶点出发，访问其余顶点，考虑<u>非连通图</u>和<u>存在回路</u>的图，设置标志位。

• 深度优先(DFS)

  每一条边处理一次，每个顶点访问一次（无向图的每条边从两个方向处理）
  邻接表：有向图O(|V|+|E|)，无向图O(|V|+2|E|)
  相邻矩阵：O(|V|²)

• 广度优先(BFS)
  队列处理，与DFS的区别仅仅在于访问顺序

• 拓扑排序
  先决条件：以某种线性顺序来组织多项任务，以便能够在满足先决条件的情况下逐个完成各项任务(<u>有向无环图</u>DAG可以模拟先决条件)
  拓扑排序：将一个有向无环图中所有顶点在不违反先决条件关系的前提下排成线性序列的过程称为拓扑排序，其形成的序列称为拓扑序列，不唯一
  方法：从图中选择一个入度为０的顶点并输出，在图中删掉此顶点及其所有的出边(出边关联顶点的入度减一)，迭代；环路存在时仍有顶点没有被输出但找不到入度为0的顶点

  • BFS-TopSort()
    建立“入度表”辅助，表示各节点入度；取出所有入度为0的（当父亲）入队，随着pop()，更改pop()出元素的相邻元素入度
    广度优先排序可以判定环是否存在

  • DFS-TopSort()
    先访问子孙，再访问父亲，使用类似后根遍历的算法来实现。缺点就是DFS无法看出环，用backward_edge来判断

最短路径问题

带权图的最短路径问题：求两个顶点间长度最短的路径；

广度优先遍历本质上就是单位权重图的最短路径搜索问题；

稀疏图反复做Dijkstra算法来求每对顶点的最短距离其实比较合适；

• Dijkstra算法(单元最短路径，边权非负下的最好算法)

  贪心思想：每次都选最优的
  具体操作：每次从距离已生成最短路径的结点集“一步之遥”的节点中选择据原点最近的边进行延伸
  证明算法的正确性：否定其他可能性

  这门课的算法和上机作业的都是基于数据是一种内存的数据结构（存在连接链表的）。实际情况下图太大了，必须用文件来存。文件是线性的。无论是连接链表还是矩阵，都不能直接有。不能保证邻居在该行附近，对于文件执行Dijkstra效率会异常低。

  邹磊研究组：大图数据管理

• Floyd算法(O(n³)，适合稠密图)

  基本想法：adj^k[i][j]=从V_i到V_j中间顶点序号不大于k的最短路径长度，最后adjⁿ将包括任意两点间的最短路径；
  动归思想：中间不经过V_k，则adj^k[i][j]=adj^k-1[i][j]，中间经过V_k ，则adj^k[i][j]=adj^k-1[i][k]+adj^k-1[k][j]；那么循环时使adj^k取二者最小值即可；满足递推公式的最优子结构和可重复利用的重叠子结构；
  确定路径：路径矩阵，只记录A到B的倒数第二步走哪个结点，否则置-1；

最小生成树

亦称最小支撑树-Minimum-cost Spanning Tree，对于带权的连通无向图G，其最小支撑树是一个包括G的所有顶点和部分边的图，这部分的边使图具有连通性且边权值综合最小；

实际例子如城市间修公路使各个城市连通；

之所以是树，是‘因为如果存在环结构则打掉一条边亦满足连通性；

• Prim算法(类似Dijkstra)

  步骤：从图中任意一个顶点开始把它包括在MST中，然后把端点一个在MST一个不在MST的==边==中找权最小的任一条边，并把边和另一个端点也拉进MST，如此迭代至所有点生成

  证明：反证法
  

  图片6.png

• Kruskal算法(O(|E|ln|E|)，适合稀疏图)

  步骤：开始时将顶点集分为[V]个等价类，每个等价类包括一个顶点；然后以权的大小顺序处理各边，如果某条边链接两个不同等价类的顶点则其加到MST并把两个等价类合并为一个；反复执行直到剩下一个等价类；

可以参考《算法导论》来看图论相关内容；比较复杂；

内排序

• 内部排序(Internal Sorting) 待排序记录少，放在内存，排序过程在内存进行；
• 外部排序(External Sorting) 待排序记录数大，内存无法容纳所有记录，排序过程中还需要访问外存。后序课程如数据库概论会涉及这样的问题。核心问题就是如何减少io次数；

简单排序 O(n²) - 插入排序，基于二分查找的插入排序，选择排序(不稳定)，冒泡排序(稳定)

对于循环体的i，插入排序就是排好前i-1个然后插入第i个；冒泡排序是依次让第i个元素成为i~n里面最小的；选择排序是找到最小的和第i个直接交换。

基本概念：记录 Record,关键码 Key...

稳定算法与不稳定算法：若记录序列中的任意两个记录R_x,R_y的关键字K_x,K_y，如果在排序之前和排序之后的<u>相对位置</u>保持不变，则这种排序方法是稳定的，否则是不稳定的。

时间代价：记录的比较合交换次数；空间代价：所需附加空间的大小

Shell 排序

又称缩小增量排序，用逆置换的个数来确定排序；

1959年由D.L.Shell提出，插入排序每次只能改变一个逆序，但是Shell排序一次可以改变好几个逆序——这说明它是不稳定的；

Shell最初提出的增量序列是d₁=[n/2],d_i+1=[d_i/2]；这个做法不大好，因为很有可能奇偶的下标有一定规律；因此用互质的增量序列效果可能会更好；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重复上述分组和排序工作。

分治算法

• 快速排序

基于分治思想，类似二叉搜索树，最佳性能是O(nlnn)->此时二叉树高度最低，最差性能是O(n²)->此时二叉树是一条链；

具有普适性的算法分析应该如下：

$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个元素；

• 归并算法

  先划分再归并

  归并——两个有序的数组，只需两个指针从头往后跑；有一定的空间代价；

  稳定

• 堆排序

非稳定排序，理论上时间代价$\Theta (nlnn)$

1. 对所有记录建立最大堆
2. 取出堆顶元素放到数组末尾，然后把堆尾的丢到堆头再调整；

分配排序

这些算法的基本想法都是比较和交换；这种想法的排序方法不能再低于nlnn了；另一种idea是分配和收集；前提是必须知道所有记录值固定在某区间；

• 桶排序 Bucket Sorting : 先分配，再收集
  注意桶计数和排序序列的映射关系——需要把计数器简单处理为下标指示，再从后往前把萝卜填坑；这一点是因为排序规则可以自定义，从后往前排序能够保持稳定性，可以有更多的操作空间；
  O(m+n)，只适合m比较小的情况；

• 基数排序
  高位优先法(MSD)
  低位优先法(LSD) 同上，更易为计算机接受；

  基于数组的基数排序空间开销比较大，可以用静态链来改进。这样子不需要移动记录本身，只需要修改记录的next指针，O(d(n+r))——实际上是O(nlogn)。

• 索引排序/地址排序
  记录规模很大时，减少记录移动次数以降低排序时间。例子：pagerank；
  关键点就是基于index直接在原有数组上排序。取一个tmp流出一个空，再顺着空当对应index来塞。

排序问题的界

Lower Bound: 解决排序问题能达到的最佳效率，即使尚未设计出算法。

Upper Bound: 已知最快算法所达到的最佳渐进效率。

排序问题的下限应该在$\Omega(n)-\Omega(nlogn)$之前。

外排序

引言： 内存是一种有限的存储资源，需要解决外存文件的排序问题。

比赛： Sort Benchmark 100TB in 134s

访问外存比访问内存慢5~6个数量级，(10^-3,10^-9)；

核心思想是减少IO；

外存访问分为定位和存取两个阶段；内存被划分为长度固定的存储空间；数据访问以block块为单位进行，从而减少外存的定位次数，进而减少外存读写的时间耗费。

基本过程：

1. 置换选择排序（目的是把外存初始化为尽可能长的有序顺串集，手法为堆排序）；
2. 归并排序（目的是把顺串集合逐趟归并排序，形成全局有序的外存文件，手法是k叉哈夫曼树）；

m顺串个数，每次对k个顺串归并，归并趟数[log_km]，n-1 个元素，做k-1次比较，

胜者树，败者树

检索

在记录中找到“A[key]==value”，主要操作就是关键码的比较。

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

提高检索效率的方法 - 预排序，建立索引，散列技术

分类 - 线性表（顺序，二分），关键码值（下标），树索引（二叉，B树），属性（倒排表，倒排文件）

哈希方法

用一个确定的函数H和待检索的关键码K确定记录的存储地址 $Address=Hash(Key)$

负载： $\alpha=\frac n M$ , n:散列表中已有结点数，M散列表空间大小

冲突： 将不同的关键码映射到相同的散列地址（实际应用中不产生冲突的极少存在）

同义词： 产生冲突的关键值码

两个重要问题：

1. 散列函数的构造 - 使结点“均匀分布”，尽可能降低冲突现象发生的概率
2. 冲突解决的方法

散列函数的选取原则：

1. 运算简单
2. 函数值在散列表范围内[0,M-1]
3. 关键码不同时，尽可能使其散列值也不相同
4. 图片7.png

常用方法：取余法(缺点在其连续性导致冲突处理性能下降)，乘余取整(乱凑)，平方取中(比较均匀)，数字分析，基数转换，折叠，ELFhash字符串散列函数 - 可参考《算导》

• 冲突的解决方法

  1. 内存：开散列方法（拉链法）——所有同义词链接在同一个链表。
  2. 外存：闭散列方法（开地址法）——把发生冲突的关键码存储在散列表中另一个空地址。

  探测序列-由探测函数决定：线性，二次，伪随机数;

索引

主码(primary key)：数据库中每条记录的唯一标志

辅码：数据库中可出现重复值的码；辅码索引把一个辅码值与具有这个辅码值的多条记录的主码值关联起来

主要思想：通过索引文件去访问主文件的数据

• 线性索引 - 按照==索引码值==的顺序进行排序的文件
  缺点在于不适合动态分析（大量插入删除时可能有O(n)）

• 静态索引 - 文件创建时固定，后面的插入删除操作单独放在溢出区处理

  实际上是二叉树转换为多叉树 small | large => binary tree

• 倒排索引 - 从==属性值==到记录(attr,ptrList)
  支持基于属性的高效检索，但花费了保存倒排表的存储代价，降低了更新运算的效率

  正文索引

  • [词索引] 对正文文件的倒排 - 正文索引 =>词索引，全文索引

    1. 对文档集中的所有文件都进行分割处理，把正文分成多条记录文档；

    2. 给每条记录赋关键词

       以人工或自动的方式从记录中抽取关键词，利用stopword，抽词干和切词。
       3. 建立正文倒排表、倒排文件

       得到各个关键词的集合，对于每个关键词得到其倒排表，然后把所有的倒排表存入文件。

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

• 动态索引

  信息检索处理文档，数据库处理表格

  • B树
    m阶B树是一颗m路查找树/空树，2-3树是它的一个特殊情况，m是由io时能得到的page决定的。
  • B+树

• 位索引技术 bitmap

  对属性值定类(取值范围)建立一个向量记录"是否取某个取值"s
  也可以应用于文本 Signature file,性能不如倒排索引

  按列存储

红黑树

出发点: 建立一个保证插入/搜索/删除都是log(n)的；

定义：只有红色和黑色，首尾都是黑色，红的儿子都是黑，对任意子树的根black_height都一样；

性质：满二叉树；k阶红黑树简单路径长度介于[k,2k]；内部结点最少时是完全满二叉树(全黑)，最少时是2^k-1的内部结点数；<u>n个内部结点的红黑树的最大高度是2log₂(n+1)+1</u>;

旋转操作不改变black_height

​ B A

​ A $\delta$ $\alpha$ B

​ $\alpha$ $\beta$ $\beta$ $\delta$

idea: 当插入一个结点(默认为红)，如果其父亲是红，则矛盾，通过旋转和重新着色来调整。此时因为父亲是红，爷爷肯定是黑，需要考虑的是z / z.p.p / z.p.p.r / z.p.p.l

插入 (基于检索失败的搜索)算法步骤:

while 考察结点(固定是红)的爸爸是红色的且不是根

1. if(叔叔红)——爸爸辈两个红的拱着一个黑的——换一下上下颜色，再往上调整，考察爷爷；continue；
2. 扭曲"<,>"两红爷爷黑——不用理叔叔——旋转变成case3，让z上移，考察z的原生爸爸；
3. 单边"/,"两红爷爷黑——不用理叔叔——旋转爷爷爸爸，让爸爸变黑爷爷变红；break;

把根涂黑；

删除 (前驱和后继)

case 1: 待删除的结点没有儿子——直接删除，y=待删结点

case 2: 待删除结点只有一个儿子——调换后继和父亲，y=待删结点，x=儿子

case 3: 待删除结点有两个儿子——用后继来代替它，相应调整，y=后继，x=后继兄弟

对一个后继就是右子树的左尽头

红黑树的叶子结点都是补充了两个黑色NIL儿子的

红黑树性质保持：

1. y.color == RED √
2. y.color == BLACK
   1. y是root，y的红色儿子有可能成为root
   2. x == RED && y.p == RED
   3. 路径少了1个黑

出口: ① x指向一个 R-B，把这个点设为黑；

​ ② x指向一个root，直接把root设为黑；

while(y.color==BLACK)

1. x.bro==R, 旋转兄弟和父亲，转到以下情况

2. x.bro==B

   1. x.bro有两个黑儿子
      ① x.p==R -> x指向R-B，将x设为黑，结束

   ② x.p==B -> "双黑"，转到以下情况

   2. x.bro左红右黑——红侄子旋转压制兄弟，原兄弟变黑，转到3

   3. x.bro左黑右红——

高级数据结构

• 最佳(基于用户访问习惯，静态)
• 平衡(基于树高平衡约束，经常修改)
• 伸展树(基于用户动态访问特征)

一个拥有n个关键码的集合，只有Catalan(n)种前序排列可以构成二叉搜索树。

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

最优搜索树

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

p_i：检索第i个内部结点的的频率
q_i：检索关键码处于第i和第i+1内部结点间的频率
l_i：第i个内部结点的层数
l_i'：第i个内部结点的层数

最佳BST树构造方法(静态)
利用性质: 最佳的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): 结点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性质(虽一大一小但没有犯规/正好填坑)
2. 破坏AVL性质——从新加入的结点向根往上搜索，直到发现==最近的不平衡祖先==
   1. LL,RR——单旋转——直接转
   2. LR,RL——双旋转——提升中间结点两次

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

删除

初步和BST类似，与后继交换再删除。但是删除会导致树高和平衡因子变化，需要沿着被删除结点到根节点的路径来调整。

1. bf(root)==0——不用管
2. bf(root)!=0
   1. 砍高个儿——更新bf(root)=0，向上修改
   2. 砍矮个儿
      1. 阵亡兄弟平衡——转阵亡兄弟和爸爸
      2. root另一边和自己左右情况一样——转阵亡兄弟和爸爸，向上修改
      3. root另一边和自己左右情况不一样——转阵亡兄弟的矮儿子到root

伸展树

数据访问“28原则”：80%的人只会用到20%的数据；

伸展树提供一个新的规则，保证访问总代价不高，O(mlogn)，但不保证树的平衡。访问谁就转谁。转到根。

半伸展树——把根到访问结点路径上的结点从下到上双旋转

注意：外部结点

多维数组

广义表

L=（x₀,x₁,...,x_n-1)，每个x_i是L的成员，可以是单个元素(原子)，也可以是一个广义表（字表)。广义表是一种嵌套结构，本质上是树，广义表深度指所有元素都化解为原子后的括号层数，也就是数的层数。

图 -> 再入表 -> 纯表 -> 线性表

表头：第一个元素；表尾：整个表删去表头元素(保留外层括号)

纯表：从根节点到任何叶节点只有一条路径。是一棵树。

可重入表(再入表)：元素可能在表中多次出现，对应于一个有向无环图。

图片8.png

循环表：包含回路，深度∞。

图片9.png

Trie树

基于比较的搜索树。让<u>搜索空间的划分与元素本身无关</u>。基于两个原则：关键码集合固定，对结点分层标记。这样子，查找一个关键字的时间仅与组成关键字的字符数有关。

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

变种：PATRICIA树-以二进制来划分。