数据结构和算法（上）

2017-08-27 本文已影响420人 RichardJieChen

1 序

2016年6月25日夜，帝都，天下着大雨，拖着行李箱和同学在校门口照了最后一张合照，搬离寝室打车去了提前租好的房子，算来工作刚满一年。在过去的一年里，很庆幸刚迈出校门的我遇见了现在的这一群同事，这一帮朋友，虽然工作之初经历波折，还是很开心有现在的工作环境。其实走在这条路上在同学眼中我抛弃了很多，但是因为热爱，所以我相信我能在这条路上走的更远。可能是由于刚到一个节点吧，回顾过去的工作和学习方式，认为还是应该把所学到的知识记录下来，留待和人交流以及将来自己回顾。
可能是作为我在简书上写的第一篇文章，总想留下点什么有纪念意义的东西。作为一名移动端开发人员，尽管在工作中对于数据结构和算法的要求被无限弱化，但其作为计算机科学基础，很大程度决定了在开发技能上所能到达的高度。最近决定从头看C++数据结构与算法一书，这篇文章便是在看这本书时记下的笔记，由于目前还是主要以移动端开发为主，因此只记下基本的知识。

2 算法复杂度

根据算法中每个操作之间的关系，算法分为以下两类：

决定性算法：对于给定的输入只有一种方式能确定下一步采取的操作，如求一个集合的合只需要逐个相加并不需要进行猜测。
非决定性算法：非决定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。如查找算法会先猜测数组中某个数，再验证其是否是需要查找的那个数。

另外可以将需要解决的判定问题问题分为三类：

P问题：能够用决定性算法在多项式时间内解决的问题。
NP问题：能够用非决定性算法在多项式时间内解决的问题。
NPC问题：这里P类问题一定属于NP类问题。如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题，该问题则成为NP完整性，也成为NPC问题。

所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，于是就猜想，是否这类问题存在一个确定性算法，可以在多项式时间内直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。
算法效率指的是评估描述文件或数组尺度n同所需逻辑计算时间的关系，表示算法复杂度的方法有三种。

O表示法 表最小上界
Ω表示法 表最大下界
Θ表示法 当最小上界和最大下界相等时

表示算法可以通过以下两种方式，每一类都可用上述三种表示方式。

平均复杂度：将处理每个输入所执行的步骤数乘以改输入数的概率数。
摊销复杂度：当某个操作执行时会影响下一步操作所执行的时间时，考虑这种相互影响关系的复杂度表示方法。

例如向一个向量中连续插入单个元素，当向量容积满是便分配双倍空间并复制原数据。摊销成本可以用函数amCost(opi)=cost(opi)+potential(dsi)-potential(dsi-1)表示，其中ds为数据结构的容量。

3 链表

单向链表：删除和查找某个节点的最好情况复杂度为O(1)，最坏情况为O(n)，平均为O(n)。
双向链表：链表中的每个节点同时包含前置节点及其后继节点的指针变量。
循环链表：分为循环单向链表和循环双向链表，链表中每个节点都有后置节点，对于链表current节点标识当前节点。
跳跃链表：根据节点数量将链表分为多级，每个节点包含自身级数的指针数组，其中的元素分别指向同级的下一个节点。从最低的0级到最高级分别可以形成一个独立的子链。

跳跃链表一定是有序的，通常使用Root数组保存每一级的根节点，每一级子链中的元素都存在于其下一级的子链中，其中0级节点包含所有的元素。链表的级数maxLevel于链表节点数n之间的关系为maxLevel = [lg 2 n] + 1。为了避免在插入和删除节点的时候重新够着链表，放弃对不同级上节点的位置要求，仅保留不同级上的节点数目要求，这样的链表又称为随机跳跃链表。通过choosePowers()函数生成powers数组，然后通过chooseLeves()函数确定当前插入节点的级数。

void choosePowers() {
    powers[maxLevel-1] = (2 << (maxLevel - 1)) - 1;
    for (int i = maxLevel - 2, j = 0; i >= 0; i--, j++) {
        powers[i] = powers[i+1] - (2 << j);
    }
}
//
int chooseLevel() {
    int i, r = rand() % powers[maxLevel - 1] + 1;
    for (i = 1; i < maxLevel; i++) {
        if (r < powers[i]) {
            return i - 1;
        } 
    } 
    return i - 1;
}

当对跳跃链表进行插入操作的时候，需要将被插入节点的前置preNodes数组的各个元素对应级的指针指向该节点，同时将该节点的对应各级指针指向对应级的currentNodes数组。该类链表的删除操作类似。查询操作需要从最高级子链开始查询，如找到则返回，当当前节点的值小于时继续查找，当当前节点的值大于被查值时从前置节点的第一级子链继续查询，直至查到0级子链。
跳跃链表的平均时间复杂度为O(log 2 n)，与更高级的数据结构如自适应树或者AVL树相比效率相当不错，因此可以用来代替这些数据结构。

自组织链表：当查找某个节点后动态的重组织链表的结构，其重新组织链表的方法有以下四种。

前移法：在找到节点后将其放到链表头。
换位法：在找到节点后将其和前置节点位置互换。
计数法：根据节点的访问次数由高到低进行排序。
排序法：根据节点的自身属性进行排序。

前移法的查找某个节点x的摊销复杂度根据公式amCost(x) = cost(x) + (inversionsBeforeAccess(x) - inversionsAfterAccess(x));计算出amCost(x) <= 2posOL(x) - 1，posOL(x)表示节点x在排序法链表中的位置。可以看出当被查找节点x在前移法链表(MTF)的位置大于在排序法链表中的位置时候，其所需的访问数将大量增加。

稀疏表

当一个表只有一小部分空间被使用的时候成为稀疏表。其中很多稀疏表都可以使用链表的数据结构方式解决。例如当储存一个学校所有学生成绩时。如果用二维数组，课程作为行，学生作为列，这时很多学生并不会选修所有的课，这会造成大量的空间浪费。此时，使用Class和Student两个数组，其中class数组每个元素记录选修这门课程的链表，Student中每个元素记录这个学生所修课程的链表，这样会大量节约所需的内存空间。
数组的优点是随机访问，因此需要直接访问某个元素，数组是更好的选中，如二分查找法和大多数排序算法。当只需要固定的访问某些元素（如第一个和最后一个），并且结构的改变是算法的核心则链表是更好的选则，如队列。另外数组的另一个优点是空间，链表本身还会花空间存储指向节点的指针。

4. 栈与队列

栈：先进后出只能从栈顶访问和删除的数据结构，栈数据结构可以用于匹配分隔符以及大数相加的操作，可以用向量（数组）和链表的方式实现，其中链表的方式与抽象栈更匹配。在向量和链表形式的栈中，出栈操作的复杂度为O(1)，在向量栈中最坏的入栈复杂度为O(n)，而在链表栈中仍为O(1)。
队列：一端用于新加元素，一端用于删除元素的数据结构。同样队列也可以使用数组和链表的方式实现。在双向链表的实现中，入队和出队的复杂度为O(1)，单向链表的出队操作复杂度为O(n)。
优先队列：当队列中的某些操作需要优先被执行的时候采用的一直特殊队列。有以下三种实现方式。
（1）单链表实现：入队和出队的时间复杂度为O(n)，适合10个以下的元素。
（2）一个数目不固定的短有序链表和一个无序链表，有序链表中元素数目取决于阀值优先级，加入元素后会动态变化，当元素数目众多时效率和第一类相近。
（3）一个具有√n数量的有序链表和一个无序链表，入队平均操作时间是O(√n)，出队立即执行，适合任意尺寸的队列。
STL中的双端队列：靠指针数组实现。双端队列Deque对象包含head、tail、headBlock、tailBlock和blocks五个字段。其中blocks字段保存了所有的数据数据组。

迷宫问题通常可以使用栈数据结构解决，将迷宫中的位置墙看做1，通道看做0，整个迷宫看做一个二维数组，从初始点开始，将上下左右可以通过的点坐标依次存入栈Stack，从栈顶取出一个位置作为当前位置，并按上述顺序继续搜索可以通过的点并存入栈中，当栈为空时则没有路径可以走出迷宫，当栈顶为出口时则找到正确路径。

5.递归

函数内部对自己的调用，通常递归的定义通过运行时栈实现，实现递归的所有工作由操作系统完成。

unsigned int factorial (unsigned int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial (n -1);
  }
}

每个函数被调用时，系统会保存函数活动记录栈，从主函数开始，当一个函数被调用时该函数的活动记录入栈，当函数调用结束时函数的活动记录出站，系统也是基于此实现函数的递归调用。

int main {
  /* 第136行 */ y = power (5.6,2);
}

double power (double x, unsigned int n) {  /*102*/
  if (n == 0) {  /*103*/
    return 1.0;  /*104*/
  } else {  
    return x * power(x,n-1);  /*105*/
  }
}

尾递归：在每个函数实现的末尾只使用一个递归调用。尾递归都可以转化为迭代形式。

void tail (int i) {
    if (i > 0) {
      cout << i << '';
      tail(i-1);
    }
}

非尾递归：除尾递归以外的递归。将非尾递归转化为迭代形式的时候都需要显示的使用栈。

void nonTail (int i) {
    if (i > 0) {
      nonTail(i-1);
      cout << i << '';
      nonTail(i-1);
    }
}

例如雪花图案的绘制过程对递归函数的调用。

void drawSigleLine(sideLength, level) {
    if (level = 0) {
      画一条线
    } else {
      drawSigleLine(sideLength/3, level - 1);
      向左转60°;
      drawSigleLine(sideLength/3, level - 1);
      向右转120°；
      drawSigleLine(sideLength/3, level - 1);
      向左转60°；
      drawSigleLine(sideLength/3, level - 1);
    }
}

间接递归：当函数f()调用函数g()，函数g()调用函数f()时；或者当形成下述调用关系f() -> g1() -> g2() -> ... -> gm() -> f()时形成间接调用关系。如信息编码函数receive() -> decode() -> store() -> receive() -> decode() -> ...
嵌套递归：函数不仅根据自身进行定义，还作为该函数的一个参数进行传递。

int regression(int n) {
    if (n = 0) {
      return 0;
    } else if (n > 4) {
      return n;
    }  else if (n <= 4) {
      return regression(2+regression(2*n));
    } 
}

不合理递归：对于同一个输入进行多次计算，或者超大规模的递归调用通常是不合理的递归调用。
尽管递归在逻辑上更简单和易于阅读，但其降低了运行速度，过多次数递归使得函数被多次调用导致运行时栈空间有用尽崩溃的危险。例如如下函数：

int fib(int n) {
    if (n < 2) {
      return n;
    } else {
      return fib(n-2) + fib(n - 1);
    }
}

上述函数fib当n=6时可以看出对于同一个n进行了多次调用，随着n的增加，重复的计算次数极大提升。通常这类问题可以转化为迭代方式进行，当n=30时，递归方法调用次数为2 692 537次，而迭代方式只计算87次。

int iterativeFib(int n) {
    if (n < 2) {
      return n;
    } else {
      int i = 2, tmp, current = 1, last = 0;
      for (; i <= n, ++i) {
        tmp = current;
        current += last;
        last = tmp;
      }
      return current;
    }
}

回溯：在解决某问题是，从给定位置出发有许多不同路径，尝试一条路径不成功后返回出发的十字路口尝试另外一条路径的方法。

在国际象棋棋盘中，根据规则，当a中皇后确定位置后，其虚线上不能再放置皇后，求出能在每一行成功放置一名皇后的所有棋盘的解。使用二维数组标识棋盘上所有的点，假设棋盘边长为n，判断一个皇后在当前位置是否可以成功放置需先判断该行，该列，正斜率斜线，负斜率斜线是否可用，用数组column[n-1]标识所有的列，leftDiagonal[2n-1]标识所有的正斜率斜线，该斜线的row+column为0~2*n-1用于标识斜线在数组中的序号，rightDiagonal[2n-1]标识所有的负斜率斜线，该斜线的row-column为-n+1 ~ n-1，为其加上(n-1)用于标识斜线在数组中的序号。

/*
棋盘边长为n      column[n-1]所有列      leftDiagonal[2*n-1]所有正斜率斜线
rightDiagonal[2*n-1]所有负斜率斜线      positionInRow[n]每行皇后的列索引数组
*/
void putQueen (int row) {
    for (int col = 0; col < n; col++) {
      if (column[col] == true && leftDiagonal[row+col] == true 
      && rightDiagonal[row-col+n-1] == true) {
        positionInRow[row] = col;
        column[col] = false;
        leftDiagonal[row+col] = false;
        rightDiagonal[row-col+n-1] = false;
        if (row < n - 1) {
          putQueen(row+1);
        } else {
          printBoard(cout);
        }
        column[col] = true;
        leftDiagonal[row+col] = true;
        rightDiagonal[row-col+n-1] = true;
      }
    }
}

递归的效率常常比等价迭代形式更低，但其具有清晰性、可读性和简单性的特点。每个递归都可以转化为迭代形式，但转化过程并不总是很容易。以下两种场合下非递归的实现方式更可取：第一种是在实时系统中，如军事环境、航天器和科学实验中；第二种情况是需要避免使用递归的情况，如编译器。但是有时递归操作比非递归实现更快，如硬件带有内置栈操作。在计算结果时候，当某个部分毫无必要的重复就应该避免递归的使用。通常绘制一个调用树很有必要，如果树太深运行时栈就有溢出的风险，如果树浅且茂密递归就是一个很好的方法。

6 二叉树

6.1 查找

二叉树查找算法复杂性由查找过程中比较次数来度量。复杂度为到达某个节点的路径长度加1。内部路径长度（IPL）是所有节点的所有路径长度总和，平均路径深度可以代表查找一个节点的平均复杂度。在最坏情况下，即当树退化为链表时候，path = O(n)。最好情况下，即当树完全平衡时，path = h - 2。平均情况下path = O(lg n)。

6.2 遍历

二叉树的遍历方法根据树的访问策略分很多，重要的是广度优先遍历和深度优先遍历。

6.2.1 广度优先遍历

广度优先遍历先从树的最高层开始，从左向右逐层向下访问树中的每一个元素。

template<class T>
void BST<T>::breadthFirst() {
  Queue<BSTNode<T>*> queue;
  BSTNode<T> *p = root;
  if (p != 0) {
    queue.enqueue(p);
    while(!queue.empty()) {
      p = queue.dequeue();
      visit(p);
      if (p->left != 0) {
        queue.enqueue(p->left);
      }
      if (p->right != 0) {
        queue.enqueue(p->right);
      }
    }
  }
}

6.2.1 深度优先遍历

深度优先遍历会尽量从根节点访问到叶节点，再回溯至最近一次有未访问子节点的节点，再访问到其叶节点。根据其访问节点的先后顺序可以有多种访问的方式，但常用的主要是前序树遍历、中序树遍历和后序树遍历。

前序树遍历

template<class T>
void BST<T>::preorder(BSTNode<T> *p) {
  if (p != 0) {
    visit(p);
    preorder (p->left);
    preorder (p->right);
  }
}

中序树遍历

template<class T>
void BST<T>::inorder(BSTNode<T> *p) {
  if (p != 0) {
    inorder (p->left);
    visti(p);
    inorder (p->right);
  }
}

后序树遍历

template<class T>
void BST<T>::postorder(BSTNode<T> *p) {
  if (p != 0) {
    postorder (p->left);
    postorder (p->right);
    visti(p);
  }
}

但是使用递归函数会给系统带来很大的负担，有运行时栈溢出的危险，因此可以显示的使用栈来遍历二叉树。
另外对于特定形状的树，可能需要将所有节点放入栈中，这样会使用大量的空间。可以通过线索树和树的转换的方式遍历树。

线索树遍历

普通的二叉树的每个节点最多可以有两个指针，分别指向其左右子节点，为每个节点扩充两个分别指向前驱和后继节点的指针，这样包含线索的树称为线索树。但是通常我们可以通过重载已有指针的方式使用两个指针变量，和一个标识变量来同时维护后继、左、右子节点信息。其中标识变量标识当前节点的right指针代表的是右子节点还是后继节点，每个节点最多拥有上述三个节点信息中的两个。线索树的插入操作在后面讨论，这里只讨论遍历操作。拥有后继、左和右子节点的线索树可以进行前序、中序和后序遍历，这里只讨论中序遍历。

template<class T>
void ThreadedTree<T>::inorder() {
  ThreadedNode<T> *prev, *p = root;
  if (p != 0) {
    while (p->left != 0) {
      p = p->left;
    }
    while (p != 0) {
      visit(p)；
      prev = p;
      p = p->right;
      if (p != 0 && prev->successor == 0) {
        while (p->left != 0) {
          p = p->left;
        }
      }
    }
  }
}

Morris遍历法

Morris开发了一个精致的算法不使用栈和线索树，仅通过临时将树退化为链表的方式也能完成树的遍历，当然在遍历结束时需要恢复树的结构。

template<class T>
void BST<T>::MorrisInorder() {
  BSTNode<T> *p = root, *tmp;
  while (p != 0) {
    if (p->left == 0) {
      visit(p);
      p = p->right;
    } else {
      tmp = p->left;
      while (tmp->right != 0 && tmp->right != p) {
        tmp = tmp->right;
      }
      if (tmp->right == 0) {
        //改变树结构
        tmp->right = p;
        p = p->left;
      } else {
        visit(p);
        //恢复树结构
        tmp->right = 0;
        p = p->right;
      }
    }
  }
}

6.3 插入

6.3.1 一般树的插入操作

template<class T>
void BST<T>::insert(const T &el) {
  BSTNode<T> *p = root, *prev = 0;
  while (p != 0) {
    prev = p;
    if (el < p->el) {
      p = p->left;
    } else {
      p = p->right;
    }
  }
  if (root == 0) {
    root = new BSTNode<T>(el);
  } else if (el < prev->el) {
    prev->left = new BSTNode<T>(el);
  } else {
    prev-right = new BSTNode<T>(el);
  }
}

6.3.1 线索树的插入操作

这里只讨论由左子节点、右子节点和后继节点组成的线索树，除根节点外每个节点必有其右子节点后者后继节点中的一个。

template<class T>
void ThreadedTree<T>::insert(const T &el) {
  ThreadedNode<T> *p, *prev = 0, *newNode;
  NewNode = new ThreadedNode<T>(el);
  if (root == 0) {
    Root = newNode;
    return;
  }
  p = root;
  while (p != 0) {
    prev = p;
    if (p->key > el) {
      p = p->left;
    } else if (p->successor == 0) {
      p = p->right;
    } else {
      break;
    }
    if (prev->key > el) {
      prev->left = newNode;
      newNode->successor = 1;
      newNode->right = prev;
    } else if (prev->successor == 1) {
      newNode->successor = 1;
      prev->successor = 0;
      newNode->right = prev->right;
      prev->right = newNode;
    } else {
      prev->right = newNode;
    }
  }
}

6.4 删除

删除一个树中的节点分为1）删除一个子节点，2）删除的节点只有一个子节点，3）删除的节点有两个子节点。在面对前两种情况时很容易删除一个节点，在处理第三种情况时根据对树进一步处理分为合并删除和复制删除。

6.4.1 合并删除

合并删除在处理有两个子节点的节点P时通过找到左子树的最大节点LMax，并使P的右子树RTree成为节点LMax的右子树。或者找到右子树的最下节点RMin，并使节点P的左子树LTree成为节点RMin的左子树。合并删除的缺点是随着删除节点的进行可能导致树高度增加，生成高度不平衡的树。

template<class T>
//使用指针的引用变量做形参可以在函数内部更改调用处的参数值
void BST<T>::deleteByMerging(BSTNode<T> *& node) {
  BSTNode<T> *tmp = node;
  if (node != 0) {
    if (node->right == 0) {
      node = node->left;
    } else if (node->left == 0) {
      node = node->right;
    } else {
      tmp = node->left;
      while (tmp->right != 0) {
        tmp = tmp->right;
      }
      //这里使用上文中的第一种1方案
      tmp->right = node->right;
      tmp = node;
      node = node->left;
    }
    delete tmp;
  }
}

如果再树中删除一个节点将查找和删除操作分开非常不合理，因为合并删除方法在调用的时候希望直接将需要删除节点的指针存入父节点中，这样组合后将它们的引用变量作为实参传入函数才能在函数嫩不改变这个实参的值。

template<class T> 
void BST<T>::findAndDeleteByMerging(const T &el) {
  BSTNode<T> *node = root, *prev = 0;
  While (node != 0) {
    if (node->key == el) {
      break;
    }
    prev = node;
    if (node->key < el) {
      node = node->right;
    } else {
      node = node->left;
    }
  }
  if (node != 0 && node->key == el) {
    if (node == root) {
      deleteByMerging(root);
    } else if (prev->left == node) {
      deleteByMerging(prev->left);
    } else {
      deleteByMerging(prev->right);
    }
  } else if (root != 0) {
    cout << "key" << el << "is not in the tree\n"
  } else {
    cout << "the tree is empty\n";
  }
}

6.4.1 复制删除

复制删除可以在很大程度上解决合并删除树高度不断增加的问题，同样它也可以通过将其前驱即左子树中的最大节点和其后继即右子树中的最小节点复制到需要删除的节点处。但是多次删除后树也会出现不平衡现象。可以通过交替的替代前驱和后继节点来尽量使树保持平衡。实验表明对于n个节点的树多次插入和非对称复制删除后IPL期望值为Θ（n lg3 n）。当使用对称Θ（n lg n）。

template<class T>
void BST<T>::deleteByCopying(BSTNode<T>* & node) {
  BSTNode<T> *previous, *tmp = node;
  if (node->right == 0) {
    node = node->left;
  } else if (node->left == 0) {
    node = node->right；
  } else {
    tmp = node->left;
    previous = node;
    while (tmp->right != 0) {
      previous = tmp;
      tmp = tmp->right;
    }
    node->el = tmp->el;
    if (previous == node) {
      previous->left = tmp->left;
    } else {
      previous->right = tmp->left;
    }
  }
  delete tmp;
}

6.5 树的平衡

尽管前面很小心的对树进行删除操作，但是仍不能完全避免树的不平衡现象，因此我们在必要的时候需要进行平衡树操作。效率最低的办法是将所有数据放入一个数组中，通过排序算法将数组排序，通过特定的方式重建树。此方法的改进是通过中序树遍历得到递增数组，重建树，但是其效率仍然低下。下面讨论更高效的平衡树算法。

6.5.1 DSW算法

DSW算法的核心操作是将一个节点ch围绕其父节点pa进行左旋转或者右旋转。第一阶段该算法将树旋转退化为类似链结构，并从根到子节点递增，第二阶段创建完全平衡树。该算法创建主链最多需要O（n）次旋转，创建完全平衡树也只需要O（n）次旋转。

6.5.2 AVL树

通常我们在对树进行操作时只需要对树的部分进行平衡操作。AVL树也被称作可容许树，要求每个节点的左右子树高度差为1。AVL树的高度h受限于：lg（n+1） <= h < 1.44lg(n+2)-0.328。对于比较大的n，平均查找次数为lgn+0.25次。AVL树在进行插入和删除操作时都必须实时更新平衡因子，当平衡因子大于±1时则通过旋转的方式对树的部分进行平衡，并继续向父节点更新平衡因子，直至当某个节点的平衡因子不发生变化或者到根节点时停止操作。
另外AVL树可以扩展，平衡因子阈值可以调高，阈值越高，其平均查找效率越低，平均平衡效率越高。

6.6 自适应树

虽然平衡树能使树的平均路径深度得到有效降低，但是频繁的对树进行平衡操作会造成很大的性能浪费，因为通常我们更关心执行插入、删除和查找操作的效率而不是树的形状。因为我们对不同元素的访问有偏好性，因此根据访问频率沿着树向上移动元素从而形成一种优先树即自适应树是一个很好的解决方案。
自适应树的构造策略分为：1）单一旋转：如果访问子节点，则将子节点围绕它的父节点进行旋转。2）移动到根部：重复子节点-父节点的旋转，直至将被访问元素移到根部。

6.6.1 张开策略

张开策略是移动到根部的一个修改版本。其根据子节点、父节点和祖父节点之间的链接关系的顺序，成对的使用单一旋转。主要有两种链接关系：1）同构配置：节点RQ同为左子节点或同为右子节点；2）异构配置：节点RQ分别为左右子节点中的一个。

splaying (P, Q, R) {
  //R、Q、P分别为被访问节点、其父节点和祖父节点
  while R不是根节点
  if (R的父节点是根节点) {
    进行单一张开操作，使R围绕其父节点进行旋转
  } else if  (R与其前驱同构) {
    首先围绕P旋转Q，再围绕Q旋转R
  } else {
    首先围绕Q旋转R，再围绕P旋转R
  }
}

由于每次访问自适应树后，其树的结构都会发生变化，因此因使用摊销复杂度来计算访问节点的复杂度。其单词访问节点的摊销复杂度为O（lgn），对于一系列的m次访问，其效率为O（m*lgn）。

6.6.2 半张开策略

由于使用张开策略经常访问靠近根部的元素会使树不平衡，因此考虑其优化方法。半张开是张开策略的一个修改版本，它可以更加平衡，对于同构情况，该策略只需进行一次选择，然后继续张开被访问节点的父节点。

6.7 堆

堆是一种特殊类型的二叉树，通常可以分为最大堆和最小堆，最大堆具有以下性质1）每个节点的值大于等于其每个子节点的值；2）该树完全平衡，最后一层的叶子位于最左侧的位置。当第一个条件的大于变为小于时候则是最小堆。如果将一个堆通过广度优先算法遍历得打一个数组，则数组元素中节点和其页节点的序号对应从前往后分别为（x ：2x+1，2x+2）（其中x从1递增至n/2）。
将元素加入堆需要将元素加到堆末尾再逐层向上恢复堆的特性。在堆中删除元素需要删除根元素，因为其优先级最高，再将最后一个叶节点放在根上，再恢复堆属性。

6.7.1 用堆实现优先队列

堆很适合用于实现优先队列，通过链表实现的优先队列的结构复杂度是O（√n），而在堆中到达叶节点只需要O（lg n）次查找。

6.7.2 用数组实现堆

可以通过广度优先法遍历堆得到的数组来表示一个堆。将数组转化为堆的方法主要分从空堆创建和合并小堆两种方式。

从空堆开始创建：将数组中的元素挨个取出，创建一个堆。这个方法在最坏情况下的交换次数和比较次数为O（n lg n）。
合并小堆：为了增加算法的效率可以采用合并小堆的方式，该算法从最后一个非叶节点data[n/2 - 1]开始创建一个子树，并恢复堆属性同事交换数组中的元素，直至处理完第一个根节点。最坏情况下改算法的移动次数和比较次数都是O（n）。

最坏情况下合并小堆的方法效率更高，但是评价情况下两个算法的效率处于同一水平。

6.8 treap树

二叉查找树的操作非常高效，但多次操作时会发生树的不平衡现象，堆是完全平衡树，可以快速访问最大或者最小元素，但是不能立即访问其他元素。如果有一个树同时满足堆的部分性质和二叉查找树的部分性质的树称为他treap树。它有多种实现方式。

6.8.1 显示优先级实现-笛卡尔树

对于它的每个节点包含一个键值对，其中键满足二叉树性质，值满足最大堆性质。
在其中插入元素时，首先生成随机的优先级，用键根据二叉查找树性质在树中找到合适的位置插入，再通过值通过旋转二叉树方式来恢复堆属性。
删除其中元素时将其优先级较高的节点围绕它进行旋转直至被删除的节点只有一个子节点后者没有子节点，此时直接将改元素删除。

6.8.2 隐式优先级实现

treap树并不总是需要在每个节点储存其优先级，第一种方法是使用一个散列函数h，将具有键值k的某项优先级设置为h（k），但这种方案暂不讨论。另外一种是通过数组分方式实现treap树，其中数组的序号代表其优先级，这种方式类似于最小堆。但是节点和子节点在数组中序号的对应方式不能套用堆中的公式。
这种方案中插入一个节点，需要随机生成小于等于n的优先级i，如果i=n，则直接将节点放在数组末尾，否则需要将数组中占据i位置的项通过一系列的旋转操作变为叶节点，再将需要插入的节点根据二叉树的性质放在合适的位置，再根据其优先级恢复整个的堆性质就能得到新的treap树。在数组中直接插入对应索引即得到新的数组。
删除一个节点时，首先从treap树中删除节点，先通过二叉树删除节点规则将节点删除，然后在数组中将最后一个元素填到当前位置确定新的游优先级，再根据新的优先级恢复堆属性。

6.9 k-d树

通常二叉查找树的每个节点只有一个键值，当每个节点拥有多个键值时成为k-d树，k代表每个节点拥有的键值数。k-d树将各个维度在从根到子节点的每一层中有顺序的交替使用。通过这种方式可以在空间中划分很多不同的区域。

6.9.1 插入节点

void insert (el) {
  i = 0;
  p = root;
  prev = 0;
  while p != 0 {
    prev = p;
    if (el.keys[i] < p->el.keys[i]) {
      p = p->left;
    } else {
      p = p->right;
    }
    i = (i+1) mod k;
  }
  if (root == 0) {
    root = new BSTNode(el);
  } else if (el.keys[(i-1) mod k] < p-el.keys[(i-1) mod k]) {
    prev->left = new BSTNode(el);
  } else {
    prev->right = new BSTNode(el);
  }
}

6.9.2 查找节点

最坏情况下，具有n个节点的完全k-d树中执行查找操作的复杂度为O（k*n^（1-1/k））。

search(ranges[][]) {
  if (root != 0) {
    search(root,0,ranges)
  }
}

search(p, i, ranges[][]) {
  found = true;
  for (j = 0 ~ k-1) {
    if !(ranges[j][0] <= p->el.keys[j] <= ranges[j][1]) {
      found = false;
      break;
    }
  }  
  if (found) {
    输出p->el;
  }
  if (p->left != 0 并且 ranges[i][0] <= p->el.keys[i]) {
    search(p->left, (i+1) mod k, ranges);
  }
  if (p->right != 0 并且 p->el.keys[i] <= ranges[i][1]) {
    search(p->right, (i+1) mod k, ranges);
  }
}

6.9.3 删除节点

k-d树中删除节点不能完全套用二叉树的方法，因为需要删除的节点N的标识位i，其下一层的节点标识位变为j，因此其前驱节点即在i标识位上取得最低值的节点可能在N的左子节点NL的下一层节点的左右子树中，这和二叉树不同。当删除一个节点只如果该节点是叶节点，直接将其删除；如果含有右子节点则在右子树中找到和N在相同的标识位上最小值的节点，采用复制删除法的方式删除节点；如果没有右子节点，则在左子树中找到符合上述要求的节点，但是在删除后将其其左子树变为右。子树同样的后继节点也和二叉树中不同。删除随机选择的节点的复杂度为O（lg n）。

delete(el) {
  p = 包含el的节点；
  delete(p, p的识别字索引i)；
}

delete(p) {
  if (p是叶节点) {
    删除p;
  } else if (p->right != 0) {
    q = smallest(p->right, i, (i+1) mod k);
  } else {
    q = smallest(p->left, i, (i+1) mod k);
    p->right = p->left;
    p->left = 0;
  }
  p->el = q->el;
  delete(q, i);
}

smallest(q, i, j) {
  qq = q;
  if (i == j) {
    if (q->left != 0) {
      qq = q = q->left;
    } else {
      return q;
    }
  }
  if (q->left != 0) {
    lt = smallest(q->left, i, (j+1) mod k);
    if (qq->el.keys[i] >= lt->el.keys[i]) {
      qq = lt;
    }
  } 
  if (q->right != 0) {
    rt = smallest(q->right, i, (j+1) mod k);
    if (qq->el.keys[i] >= rt->el.keys[i]) {
      qq = rt;
    }
  }
  return qq;
}

6.10 表达式树和波兰表达式法

波兰表达式法是不使用括号来无歧义的表示一个代数、关系或逻辑表达式的方法。而通过遍历二叉树得到这种表达式的树成为表达式树。根据遍历表达式树的方式将不同的转换方法分为前缀表示法、中缀表示法和后缀表示法。优势中缀表示法并不能得到无歧义的波兰表达式。
表达式树的结构很适合在编译器中生成中间代码，另外表达式树叶可以很好的执行微分操作。

6.10.1 创建表达式树

可以通过将表达式拆解为加减法连接的项term，乘除法表示的因子factor,和括号表示的表达式expr来构建波兰表达式树。

term () {
  ExprTreeNode *p1, *p2;
  p1 = factor();
  while (token 是 *或/) {
    oper = token;
    p2 = factor();
    p1 = new ExprTreeNode(oper, p1, p2);
  }
  return p1;
}

factor() {
  if (token是一个数,id或者操作符) {
    return new ExprTreeNode(token);
  } else if (token 是 "(") {
    ExprTreeNode *p = expr ();
    if (token 是 ")") {
      return p;
    } else {
      错误
    }
  }
}

7 多叉树

二叉树中每个节点只有两个子节点，当每个节点最多包含m个节点时就是m阶多叉树。但是我们通常只关注多差查找树。对于m阶的多差查找树有以下四个特性。

1）每个节点都可以包含m个子节点和m-1个键值。
2）所有节点的键值都按升序排列。
3）前i个子节点中的键值都小于第i个键值。
4）后m-i个子节点中的键值都大于第i个键值。

但是如果不对多叉树的结构进行有效的限制时，当多叉树变得极不平衡时，对其操作的成本将会变得很大，通常我们常用的是B树。

7.1 B树家族

7.1.1 B树

对于在硬盘存储大块数据，如果使用二叉树的方式则每个节点可能放在磁盘的不同块上，这样查找、删除和插入节点时需要不断的在磁盘的不同轨中来回读取数据。因此我们应该尽量减少节点的访问次数，同时应尽量使单个节点的容量和单个磁盘块大小相等。B树就是按这个目的设计的一种数据结构。
m阶的B树具有以下性质

1）除叶节点外，根节点至少有两个子树
2）每个非根非叶节点都有k-1个键值和k个指向子树的指针 (其中m/2的上界整数<= k <= m)
3）每个叶节点都有k-1个键值（其中m/2的上界整数 <= k <= m)
4）所有的叶节点都在同一层

B树的每一个节点包含的键值可以直接表示为要存储的数据数组，或者是一个对象数组，对象数组中每个对象都由一个标识符和一个指向辅存的地址组成。从长远来看第二种实现方式更优，因为这样节点中可以尽量少存储数据。

7.1.1.1 插入元素

除了当前树的元素总数只能支撑一个根节点存在外，B树中插入元素第一步都会放到某个叶节点中。保证每个节点插入后B树的性质不会发生改变是一件很复杂的事情。
插入节点时会遇到以下情况。1）键值被放入尚有空间的叶节点中：此时只需要插入在合适的位置即可。2）要插入的叶节点键值已满，此时需要分解叶节点，同时新建节点，并在原叶节点、新叶节点和父节点中重新分配顺序，并更新父节点指针。3）当根节点是满的时候，此时必须创建一个新的根节点以及与原节点同级的节点。
插入操作时可以进行预分解策略防止溢出不断向上蔓延。具体实施方法是，当未要插入的节点查找合适位置的过程中，遇到已满的节点就预先分解。
节点的容量和其分解的概率成正相关关系，当m=10时，概率为0.25；当m=100时，概率为0.02，m=1000时，概率为0.002。

7.1.1.2 删除元素

删除元素很大程度上是插入元素的逆过程。1）叶节点删除元素后满足B树性质则不做多余操作。2）叶节点删除元素后叶节点下溢，并左右节点数目超过节点键值下限，则在两个节点和父节点中重新分配元素。3）叶节点删除元素后叶节点下溢，并左右节点中没有超过节点键值下限的节点，则合并其中一个节点和他们父节点中他们之间的元素。4）从非叶节点中删除键值，找到其前驱子节点，将其中最大元素复制到该处，并删除原来位置的键值。

7.1.2 B*树

因为B树中每个节点都代表辅存中一个块，因此每个节点的键值越饱和，创建的节点会更少，这样效率会更高。B树与B树不同的地方在于，B树要求节点是半满的，而B树要求节点是2/3满，即k满足 (2m-1)/3的下界整数 <= k <= m-1，另外B树在分解节点时讲解的分解为3个，B树的平均使用率高达81%。
另外在B树中版本的要求标识其充填因子为0.5，B*树充填因子则为2/3，B^n树允许自定义充填因子，其充填率为(n+1)/(n+2)。

7.1.3 B+树

当需要升序输出B树中的元素时，尽管可以采用中序数遍历方式，但是对于非终端节点需要多次访问该节点才能完成其所有键值的访问，由于B树存储的不同节点是在辅存的不同块中，这样频繁的在不同块中移动性能很低，因此引出B+树。
B+树只有叶节点引用率数据。内部节点构成的集合称为索引集，子节点构成的集合称为序列集。每个叶节点相教于B树都多了一个指向下一个节点的指针。对于叶节点中的键值可以在它的父节点的中出现。
B+树的插入删除操作类似于B树，不同的是子节点合并时，分界的键值是复制到父节点中而不是移动。删除叶节点引起下溢时，合并叶节点并删除父节点中的分界值。如果键值不在子节点中则删除失败，如果键值同时在子节点和非子节点中，只删除子节点中的键值。

7.1.4 前缀B+树

非终端节点中的键值主要是为查找子节点，但是通常同一层次并属于同一个父节点的非终端节点键值有很大的重复部分，如果我们取他们键值的最短前缀，并使之不会产生歧义。这样的树称为简单前缀B+树。如果我们再忽略他们共有的前缀，仅保留能区分各个键值的部分，这样的树称为简化版本的前缀B+树，但这样的树仅停留在理论层面。

7.1.5 k-d B树

k-d B树是k-d树的B树版本，但是每个节点的键值数和指针数是相同的。其中叶节点保存K维空间的点，非叶节点保存区域信息，有一个2*k维数组组成，每一列分别代表一个维度，第一行代表最小值，第二行代表最大值。叶节点保存的键值数和非叶节点保存的键值数并不一定相同。
在k-d B树中插入节点导致的重新分区问题非常复杂。通常插入一个元素后会导致叶节点发生分裂，从而导致其父节点分裂，最后甚至导致其根节点分裂，因此会从下向上检查溢出状态，直至不再溢出，再从像下剖分节点，同一个非终端节点中使用各个维度交替分区，这与普通k-d树中每一层有固定的分区标识不同。
k-d B树删除叶节点时如果发生下溢，可以合并节点，但是节点合并仅能合并两个相连仍是矩形区域的空间。
由于普通k-d B树区域只能是矩形，为了提高空间利用率，k-d B树有多种改良版本，可以通过范围节点实现k-b树，成为hB树，hB树的字节点可多次被引用，从而划分非矩形区域。

7.1.6 位树

位数是前缀B+树发挥到极致的状态，除了叶节点层上不再保留键值来区分不同的数据，只用键值的二进制差异位来区分，其余和前缀B+树相同。位数在查询到差异位后一定要将该数据的键值和所希望的键值比较，如果不同则查找失败。

7.1.7 R树

R树是用来处理空间数据的一类树，他对节点的饱和度没有下限要求。其每个节点的指针数和数据项数是相同的，类似于k-d B树，非终端子节点只负责分区仅包含分区信息和该分区下的子节点这种数据数组（rect，child），其中rect为k*2维数组，每一行代表一个维度，第一列代表下限，第二列代表上限。每个子节点的区域都被包含在父节点中，其插入和删除操作类似于k-d B树。由于每个节点都表示了一个区域数组，因此单个节点的区域数组中的每个区域经常发生重叠。
为了消除R树中的重叠现象，引入R+树，R+树允许元素在叶节点中重复出现，但同时禁止非叶节点区域相互重叠。

7.1.8 2-4树

2-4树指通过类似于二叉树的形式实现每个节点具有3个键值和4个指针的B树。将B树中的每个键值都转换为一个节点，并且B树中一个节点的中间键值和其左右两边键值用水平（红）指针相连，B树中的每个节点的键值和其左右两边子节点的中间键值用垂直（黑）指针相连，这样的2-4树也可以称为垂直-水平树（红黑树）。
2-4树的插入操作采用了预分解策略。当插入一个新元素时在查找的过程中需要根据需要对水平和垂直标志做出更改。该树的删除操作可以通过复制删除算法完成。
另外AVL树也可以转化为垂直水平树，具体策略是将其中具有偶数高度根和该根具有偶数高度的子树的子节点相连，并标记为水平链接。

7.2 trie

trie是一种特殊的多叉树，其中叶节点为一个字符串，非叶节点由一个标识从根到当前叶节点路径的字符串是否存在的变量和一系列键值组成，每个键值都为一个字符，并对应一个指向子节点的指针，并且这个子节点下的所有叶节点都具有从根节点到当前节点经过的字符串形成的前缀。
trie面临的问题是空间上巨大的浪费，某些节点可能会闲置大量空间。1）一种简单的办法是只存储需要的指针，但实现比较复杂，可以将同级节点放在一个链表中以2-4树的方式实现。2）改变单词的插入顺序。3）通过将各个节点按一定的规律放在一个数组中来达到压缩节点的目的。4）通过按一定规则创建二进制版本的键值来达到压缩的目的。

8 图

通常图有两种常用的表示方法，1）邻接表示法：通过邻接表列出图中所有相邻的顶点。邻接表也可以实现为链表。2）用矩阵表示：表示顶点间关系的邻接矩阵表示法和表示顶点和边关系的关联矩阵表示法。

8.1 图的遍历

深度遍历法。该算法可以保证生成至少一颗以上的生成树，因为从某个节点出发常常无法遍历完整个图，或者有不相连的子图存在，因此不止一棵树。生成树中出现的边成为正向边，图中有生成树中没有的边称为负向边。对于深度遍历法其复杂度为O（|V|+|E|）。

DFS(v) {
  num (v) = i++;
  for (顶点v的所有邻接顶点u) {
    if (num (u) = 0) {
      把变edge(uv)加入边集edges;
      DFS(u);
    }
  }
}

depthFirstSearch () {
  for (所有的顶点v) {
    num(v) = 0;
  }
  edges = null;
  i = 1;
  while (存在一个顶点v使num(v) = 0) {
    DFS(v);
  }
  输出边集edges;
}

然而对于图的遍历，广度优先算法具有更高的效率。

breadFirstSearch () {
  for (所有的顶点u) {
    num(u) = 0;
  }
  edges = null;
  i = 1;
  while (存在一个顶点v使num(v)为0) {
    num(v) = i++;
    enqueue(v);
    while (队列非空) {
      v = dequeue();
      for (顶点v的所有邻接顶点u) {
        if (num(u) == 0) {
          num(u) = i++;
          enqueue(u);
          把边edges(vu)加入到edges中;
        }
      }
    }
  }
  输出edges;
}

8.2 最短路径

如果图的每一条边有一个权重值weight，就可以寻找一个顶点到图中其他顶点的最短路径。其实现方式主要是通过标记每个顶点距离初始顶点的距离，根据标记更新的策略分为标记设置法和标记校正法。

8.2.1 标记设置法

标记设置法一旦给一个顶点标记后就不会更改，此方法只能处理权值为正的图，下述算法的复杂度为O（|V|^2）。

DijstraAlgorithm (带权的简单有向图diagraph, 顶点first) {
  for (所有顶点v) {
    currDist(v) = ∞;
  }
  currDist(first) = 0;
  toBeChecked = 所有节点;
  while (toBeChecked非空) {
    v = toBeChecked 中 currDist(v)最小的顶点；
    从toBeChecked中删除v;
    for (toBeChecked 中 v的所有邻接顶点u) {
      if (currDist(u) > currDist(v) + weight(edge(vu))) {
        currDist(u) = currDist(v) + weight(edge(vu));
        predecessor(u) = v;
      }
    }
  }
}

8.2.1 标记校正法

标记校正法给每个顶点设置的标记都可能会在后面的计算过程中被更新。它可以用来处理带负权值但是不含反向循环的图（反向循环指构成环的边的权相加为负值）。该算法的效率部分取决于toBechecked的数据结构，通常使用双端队列，首次包含在其中则加到队列末尾，否则加在前端。

labelCorrectingAlgorithm (带权的简单有向图digraph，顶点first) {
  for (所有的顶点v) {
    CurrDist(v) = ∞;
  }
  CurrDist(first) = 0;
  toBechecked = {first};
  while (toBechecked非空) {
    v = toBeChecked中的顶点；
    从toBechecked中删除顶点v；
    for (v的所有邻接顶点u) {
      if (currDist(u) > currDist(v) + weight(edge(vu))) {
        currDist(u) = currDist(v) + weight(edge(vu));
        predecessor(u) = v;
        如果顶点u不在toBeChecked中，将其加入；
      }
    }
  }
}

8.2.3 多源多目标最短路径

前面讨论的是从单个节点到其他节点的最短路径，如果要知道任意节点到其他任意节点的最短路径。在稀疏图中我们可以通过对每个节点执行前面的操作即可，但是对于过于密集和完全图我们一个邻接矩阵完成。矩阵的横纵坐标都是每个节点，初始化矩阵时，矩阵中每一个值表示其横纵坐标代表的顶点间距离，左下三角全部赋值为∞，不相邻的顶点也为∞。通过一定的计算就可以得到多源多目标的最短路径矩阵。

WLIalgorithm {
  for (i = 1 to |V|) {
    for (j = 1 to |V|) {
      for (k = 1 to |V|) {
        if (weight[j][k] > weight[j][i] + weight[i][k]) {
          weight[j][k] > weight[j][i] + weight[i][k];
        }
      }
    }
  }
}

8.3 环的检测

在无向图中检测环可以通过深度优先遍历改写完成，在有向图中检测环通过判断如果一个反向边的两个顶点包含在同一个生成树中则表示有环的存在。
对于修改后的深度优先遍历法检车环的存在在稠密图中的复杂度可达O（|v|^4），因此需要更好的方法。判断两个顶点是否在一个集合中，首先需要找到v的集合，再找到w的集合。如果分别属于不同的集合就将他们合并，这样成为联合查找。

8.4 生成树

深度优先遍历法可以得到至少一颗生成树。有时我们只关心最小生成树，即所有前向边的权值和最小。我们可以将一个无向图的所有边一次加入集合中，如果形成环，则将环中权值最大的边删除，直到处理完所有的边。

8.5 连通性

8.5.1 无向图中的连通性

如果任意两个顶点至少有n条不同的路径，并且这些路径不会包含共同的节点，称该图为n联通。如果一个顶点被删除导致图被分割为独立的子图，这样的顶点称之为分割点或者关节点。如果删除一条边导致图分为两个子图，这样的边称之为分割边。

8.5.2 有向图中的连通性

对于有向图，根据是否将方向考虑在内，连通性有两种定义方式。如果具有相同顶点的边的无向图是联通的，有向图就是弱连通的，如果每对顶点间存在双向路径，则有向图是强连通的。通常有向图不是强联通的，但是其可以含有强连通分量。

8.6 拓扑排序

通常任务之间都会存在依赖关系，将一个任务看成一个节点，将节点间的先后顺序用边表示，遍历这个有向图，找到一个没有输出边的顶点v，再删除所有到v的边，将v放入序列，这样最好得到的队列就是拓扑排序的结果。

8.7 网络

8.7.1 最大流

有向图可以形成一个网络，这个网络有一个起点和一个汇点，每条边表示其最大的流通量。对于网络我们通常关心如何配置每条边的流量使得汇点能够收到更多的流量。
流增大路径表示从原点到汇点的一系列边，他们可以由前向边和后向边组成，其中前向边负责向后送流，后向边负责往回推流，我们可以找到所有的流增大路径并分别对它们进行最优化操作，最后就可以得到最大流。

8.7.2 成本最低最大流

如果对于单一的一条边，我们不仅考虑其最大容量，还要考虑通过这条边的成本，这个问题就转化为成本最低最大流问题。通过找到所有的最大流再来考虑其成本并不是一个可行的办法。我们可以先找到传送1单位流量的最便宜路径，然后在这个路径上最大可能传送更多的流，然后在找到一条新的传送1单位流量的最便宜路径，然后再最大化使用该路径，直到原点不能流出更多，或者汇点不能收到更多。

8.8 匹配

对于两个集合A和B，其中A的每个元素分别只能和部分B中的元素匹配，此时我们要找出一种匹配方式能够得到最多的匹配对。这样的问题可以转化为无向图来分析，将两个集合中的元素作为顶点，能匹配的连个顶点相连。要找最大匹配问题就变成了再图中找到一条最长路径问题。

8.8.1 匹配

对于匹配问题，通常每个元素对于能与其匹配的多个元素有不同的偏好。如果一个匹配结果中不会出现两个子匹配对交换匹配单元能够得到更高的匹配度时，改匹配结果成为稳定的匹配。

8.8.2 分配

对于加权图的分配问题，我们通常希望得到一个总权值最大的匹配结果，这样转变为了分配问题。
完全二分图是有两个相同大小顶点集，并且每个集合中的元素都能在另一个集合中找到能匹配的元素，这样的分配问题也称为最优分配问题。
非完全二分图中可能会存在基数边的环，因此不能和完全二分图使用相同的算法。

8.9 欧拉图和汉密尔顿环

8.9.1 欧拉图

如果一个图中的每个顶点都与偶数条边相关联，或者图中刚好有两个顶点有基数条边，这个图就是欧拉图，这个图包含欧拉轨迹，欧拉轨迹指一条能包含所有边的不重复路径。

8.9.2 汉密尔顿图

汉密尔顿环是一个通过图中所有顶点的环，如果一个图至少包含一个汉密尔顿环，该图称为汉密尔顿图。通常我们将一个图中找到一个度最高的顶点和另一个非邻接顶点，如果他们度的和大于节点总数就链接它们，并将这条边标记为k（k从1递增），直到所有顶点链接得到一个新图，在这个图中很容易找到一个汉密尔顿环。下面进入算法第二阶段通过从标记最大的边逐渐断开，并用不带标记的边替代，直到最后所有的边都不带标记时则找到一个汉密尔顿环。

8.10 图的上色问题

当有很多任务需要处理，但有些任务不能同时由一个人处理时，需要找到最小的人手，此时我们可以将这类问题转换为图来解决。每个任务都是图中的一个节点，不能由一个人处理的任务就用边链接起来。此时我们考虑每个顶点都需要一种颜色，但是邻接顶点的颜色不能相同，我们要用最少的颜色将所有顶点都涂上色。

8.11 图中的NP完整性问题

在知道三满意问题是NP完整性问题前提下。对于1）派系问题，派系是G的一个完全子图，派系问题可以转换为三满意问题。2）三色问题，确定一个图是否能用三种颜色正确上色，三色问题也能转化为三满意问题。3）顶点覆盖问题，无向图G=（V，E）的顶点覆盖集合指的是这样一个顶点集合W属于V，图G中每条边都至少与W中的一个顶点相连。这个问题可以转化为派系问题。4）汉密尔顿环问题，能够查找到一个汉密尔顿环可以转化为顶点覆盖问题。因此以上4个问题都是NP完整性问题。

9 排序

9.1 基本排序算法

9.1.1 插入排序

插入排序单词查询从某个元素E开始，依次像上查找如果遇见比当前比较元素更大的值则向下移位，直至查找的第0个元素停止，再将E放在合适的位置。查询起点E从i=1递增到i=n-1，则实现数组排序。

template<class T> {
  void insertionsort(T data[], int n) {
    T tmp = data[i];
    for (j = i; j > 0 && tmp < data[j-1]; j--) {
      data[j] = data[j-1];
    }
    data[j] = tmp;
  }
}

插入排序的优点是只有需要时才会对数组排序，缺点是1）在某个元素在某次循环中实际已经达到合适位置，但是后续操作可能会反复改变其位置；2）插入操作直接移动数据项，并且经常移动大量的项。
插入排序最好的情况下比较次数为n-1，移动次数为2(n-1)。最坏情况下比较次数是n(n-1)/2，移动次数为(n+2)*(n-1)。平均情况下移动和比较的次数都是O(n^2)。

9.1.2 选择排序

选择排序每次在数组中选出最小元素，将其移到当前子数组的第一个位置，然后取不包含第一个元素的子数组继续重复上述操作，直至数组中只有一个元素。

template<class T> 
void selection(T data[], int n) {
  for (int i = 0,j,least; i<n-1; i++) {
    for (j = i+1,least = i; j<n; j++) {
      if (data[j] < data[least]) {
        least = j;
      }
    }
    swap(data[least], data[i]);
  }
}
}

选择排序的优点是赋值次数更少。但是其缺点是在任何情况下都有2*(n-1)次的交换次数，因此在swap中判断，如果需要才交换元素。选择排序的比较次数是O(n^2)，交换次数为O(n)。

9.1.3 冒泡排序

冒泡排序每次迭代将起始位置元素E和其后面所有元素比较，如果E更大则交换元素。起始元素从i=0的元素一直迭代到i=n-2的元素。

template<class T>
void bubblesort(T data[], int n) {
  for (int i = 0; i < n-1; i++) {
    for (int j = n-1; j>i; --j) {
      if (data[j] < data[j-1]) {
        swap(data[j],data[j-1]);
      }
    }
  }
}

冒泡排序的比较次数在最坏、最好和平均情况下都是O(n²)，移动次数最好情况为0，最好和最坏情况下都是O(n²)。冒泡排序的主要缺点是，元素需要一步一步向上冒泡到顶部，这样非常费时。

9.1.4 梳排序

梳排序分为两个阶段，第一阶段通过初始化步长为n，步长衰减因子为1.3，每次迭代时步长都会发生衰减，在单次迭代中比较距离当前步长的两个元素确定是否需要交换。当步长衰减到小于或等于1时进入第二阶段，这个阶段使用冒泡排序的方式对数组进行排序。梳排序的良好性能可以与快速排序媲美。

template<class T>
void combsort(T data[], const int n) {
  int step = n, j, k;
  while ((step = int(step/1.3)) > 1) {
    for (j = n-1; j >= step; j--) {
      k = j-step;
      if (data[i] < data[k]) {
        swap(data[j], data[k]);
      }
    }
  }
  bool again = true;
  for (int i = 0; i < n-1 && again; i++) {
    for (j = n -1, again = false; j>1; --j) {
      if (data[j] < data[j-1]) {
        swap(data[j],data[j-1]);
        again = true;
      }
    }
  }
}

9.2 决策树

排序过程可以简单的归纳为多次表较两个元素大小，最后得到一个正确顺序的过程。如果将每次比较看做是二叉树中的一个非叶节点，是否满足条件作为一个节点连接其子节点的两条边，所有的可能出现的结果和错误的结果为叶节点。这样对于一个排序操作就可以得到一个唯一的决策树。为了得到一个排序结果即到达一个叶节点，其中比较的次数为路径深度+1，从二叉树的性质我们可以得到理论上的最优平均路径深度为O(n*lgⁿ)。当n很大时，前面的插入、选择和冒泡排序的比较量都非常巨大，因此我们可以尽量找到一个比较次数接近与这个值的排序算法。

9.3 高效排序算法

9.3.1 希尔排序

由于简单的排序算法比较次数是随着n的增加而呈指数的增长，因此将大数组巧妙分成多个小数组，分别排序是一个很好的方法，这也是希尔排序的核心思想，其中希尔排序中子数组的排序方法用的是插入排序。希尔排序每一次采用增量k在原数组中逻辑上提取子数组，并将其用简单排序法排序，当完成i次迭代直至增量衰减为1时，数组成为有序数组。当希尔排序采用的增量序列满足h(1) = 1；h(i+1) = 3h(i)+1时，其平均比较的效率为O(n^1.25)。

template<class T>
void ShellSort(T data[], int arrSize) {
  register int i,j,hCnt,h;
  int increments[20],k;
  for (h = 1,i=0; h < arrSize; i++) {
    increments[i] = h;
    h = 3*h +1;
  }
  for (i--;i>=0;i--) {
    h = increment[i];
    for (hCnt = h; hCnt < 2*h; hCnt++) {
      for (j = hCnt; j < arrSize;) {
        T tmp = data[j];
        k = j;
        while (k-h > 0 && tmp < data[k-h]) {
          data[k] = data[k-h];
          k -= h;
        }
        data[k] = tmp;
        j += h;
      }
    }
  }
}

9.3.2 堆排序

堆排序分为两个阶段，第一阶段将数组转化堆，第二阶段的每一次迭代将最大值和数组末尾值交换，堆中将最后一个节点删除，恢复堆属性，重复该操作直到堆中只剩一个节点，得到的新数组就是一个有序的数组。堆排序的平均情况下第一阶段比较和移动的时间复杂度为O(n)，第二阶段的移动和比较的复杂度是O(nlgⁿ)，交换的次数是n-1，整个排序算法的复杂度是O(nlgⁿ)。最好情况下第一阶段比较次数为n，不需要移动操作，第二阶段比较次数为2(n-1)，移动次数为(n-1)，整个算法的复杂度为O(n)。