数据结构与算法( 七)字符串串算法

编程中还是经常用到字符串匹配的算发。

一.字符串匹配算法

字符串匹配算法通常分为两个步骤:预处理(Preprocessing)和匹配(Matching)。预处理就是计算每次匹配的时候滑动窗口,所以算法的总运行时间为预处理和匹配的时间的总和。

朴素的字符串匹配算法

从左向右匹配,每次匹配一个字串, 匹配失败后 向右移动一个字串。具体流程如下:

1.

首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

2.

因为B与A不匹配,搜索词再往后移。

3.

就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

4.

接着比较字符串和搜索词的下一个字符,还是相同。

5.

直到字符串有一个字符,与搜索词对应的字符不相同为止。

6.

这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。(下面部分就是KMP改进过程,原理在后面中讲)

7.

一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是,设法利用这个已知信息,不要把”搜索位置”移回已经比较过的位置,继续把它向后移,这样就提高了效率。

8.

怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

9.

已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。查表可知,最后一个匹配字符B对应的”部分匹配值”为2,因此按照下面的公式算出向后移动的位数:

  移动位数 = 已匹配的字符数 – 对应的部分匹配值

因为 6 – 2 等于4,所以将搜索词向后移动4位。

10.

因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2(”AB”),对应的”部分匹配值”为0。所以,移动位数 = 2 – 0,结果为 2,于是将搜索词向后移2位。

11.

因为空格与A不匹配,继续后移一位。

12.

逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 – 2,继续将搜索词向后移动4位。

13.

逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 – 0,再将搜索词向后移动7位,这里就不再重复了。

KMP算法

KMP算法是在朴素算法上的优化,因为我们发现,匹配失败后,每次向右移动一个字串,能不能移动多几个字串呢?

其实这也是以空间,时间,换时间的方式。进行一个预处理。

其实就是要找到匹配过的字串中的前缀与后缀匹配的字串长度,这样直接移动过去就好了,再演化一下,预处理就是先建立起部分匹配表(索引(hash)),寻找待匹配字串的前缀集与后缀集中的匹配长度。这样就可以计算出失败后的位移长度。

下面介绍《部分匹配表》是如何产生的。

首先,要了解两个概念:”前缀”和”后缀”。 “前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。

15.

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例,

  - ”A”的前缀和后缀都为空集,共有元素的长度为0;

  - ”AB”的前缀为[A],后缀为[B],共有元素的长度为0;

  - ”ABC”的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

  - ”ABCD”的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

  - ”ABCDA”的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为”A”,长度为1;

  - ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为”AB”,长度为2;

  - ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

16.

“部分匹配”的实质是,有时候,字符串头部和尾部会有重复。比如,”ABCDAB”之中有两个”AB”,那么它的”部分匹配值”就是2(”AB”的长度)。搜索词移动的时候,第一个”AB”向后移动4位(字符串长度-部分匹配值),就可以来到第二个”AB”的位置。

数据结构与算法( 六)图

没有最好的数据结构,只有最适合的数据结构,没有最快的算法,只有最适合的算法。

图是一种常见的非线性数据结构,探究图,其实就是将非线性数据线性化的尝试。

图的遍历部分发现一个博客写得挺好,直接修改转过来了

http://www.cnblogs.com/dolphin0520/archive/2011/07/13/2105236.html

一.图定义

1.有向图:边有方向的图。 无相图:边无方向。

2.无向完全图:任两个点之间都有边的图。

3.有向完全图:任两点之间都存在两个有向边的图。

4.路径:任两个顶点之间经过的顶点序列集,长度是顶点序列之间边的的数目。

5.简单路径:路径中没有重复的顶点。

6.连通图:任两个顶点之间都存在路径的图

7.连通分量(极大连通子图):image

8.连通图的生成树:包含图中全部的顶点,但只有n-1条边

9.图可以使用2维数组来表示他们之间的关系,(邻接矩阵单元值为0,表示没有边,1表示有边)。

image

二.图的遍历

图的遍历是树的遍历的推广,是按照某种规则(或次序)访问图中各顶点依次且仅一次的操作,亦是将网络结构按某种规则线性化的过程

由于图存在回路,为区别一顶点是否被访问过和避免顶点被多次访问,在遍历过程中,应记下每个访问过的顶点,即每个顶点对应有一个标志位,初始为False,一旦该顶点被访问,就将其置为True,以后若又碰到该顶点时,视其标志的状态,而决定是否对其访问。

对图的遍历通常有”深度优先搜索“和”广度优先搜索“方法,二者是人工智能的一个基础。

深度优先搜索(Depth First Search,简称DFS)

算法思路:

类似树的先根遍历。设初始化时,图中各顶点均未被访问,从图中某个顶点(设为V0)出发,访问V0,然后搜索V0的一个邻接点Vi,若Vi未被访问,则访问之,在 搜索Vi的一个邻接点(深度优先)…。若某顶点的邻接点全部访问完毕,则回溯(Backtracking)到它的上一顶点,然后再从此顶点又按深度优先的方法搜索下去,…,直到能访问的顶点都访问完毕为止。

设图G10如下图所示:

通过深度优先如下:

广度优先搜索(Breadth First Search),简称BFS

算法思路:

类似树的按层次遍历。初始时,图中各顶点均未被访问,从图中某顶点(V0)出发,访问V0,并依次访问V0的各邻接点(广度优先)。然后,分别从这些被访问过的顶点出发,扔仍按照广度优先的策略搜索其它顶点,….,直到能访问的顶点都访问完毕为止。

为控制广度优先的正确搜索,要用到队列技术,即访问完一个顶点后,让该顶点的序号进队。然后取相应队头(出队),考察访问过的顶点的各邻接点,将未访问过的邻接点访问 后再依次进队,…,直到队空为止。

通过广度优先如下:

下面看一下实现代码:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define MAX 20
  5. //访问记录
  6. int visit[MAX];
  7. //图的结构设计
  8. typedef struct
  9. {
  10. int vex[MAX];//记录顶点
  11. int adjmatrix[MAX][MAX];//邻接矩阵
  12. int n;//顶点的个数
  13. }GRAPH;
  14. //初始化图
  15. int init_graph(GRAPH *pG)
  16. {
  17.     memset(pG,0,sizeof(GRAPH));
  18.     pG->n = -1;
  19.     printf(“input vex\n”);
  20. while(scanf(“%d”,&pG->vex[++pG->n]));
  21. while(getchar() != ‘\n’);
  22. #ifndef _DEBUG_
  23. int i = 0;
  24. for(i = 0;i < pG->n ;i ++)
  25. {
  26.         printf(“V%d “,pG->vex[i]);
  27. }
  28.     printf(“\n”);
  29. #endif
  30.     return 0;
  31. }
  32. //获取顶点的位置
  33. int locatevex(GRAPH *pG,int vex)
  34. {
  35. int i = 0;
  36. for(i = 0;i < pG->n;i ++)
  37. {
  38. if(pG->vex[i] == vex )
  39.             return i;
  40. }
  41.     return 0;
  42. }
  43. //输入图的顶点之间的边
  44. int input_edge(GRAPH *pG)
  45. {
  46. int vex1,vex2;
  47. int i,j;
  48.     printf(“input edge(i,j):\n”);
  49. //任意字母键结束
  50. while(scanf(“(%d,%d)”,&vex1,&vex2))
  51. {
  52.         getchar();
  53.         i = locatevex(pG,vex1);
  54.         j = locatevex(pG,vex2);
  55.         pG->adjmatrix[i][j] = pG->adjmatrix[j][i] = 1;
  56. }
  57. #ifndef _DEBUG_
  58. int m,n;
  59. for(m = 0;m < pG->n;m ++)
  60. {
  61. for(n = 0;n < pG->n; n ++)
  62. {
  63.             printf(“%d “,pG->adjmatrix[m][n]);
  64. }
  65.         printf(“\n”);
  66. }
  67. #endif
  68.     return 0;
  69. }
  70. //栈的设计
  71. typedef struct
  72. {
  73. int buf[MAX];
  74. int n;
  75. }Stack;
  76. //创建空栈
  77. Stack *create_empty_stack()
  78. {
  79.     Stack *stack;
  80.     stack = (Stack *)malloc(sizeof(Stack));
  81.     stack->n = -1;
  82.     return stack;
  83. }
  84. //出栈
  85. int pop_stack(Stack *stack)
  86. {
  87. int temp;
  88.     temp = stack->buf[stack->n];
  89.     stack->n –;
  90.     return temp;
  91. }
  92. //入栈
  93. int push_stack(Stack *stack,int data)
  94. {
  95.     stack->n ++;
  96.     stack->buf[stack->n] = data;
  97.     return 0;
  98. }
  99. //判断空栈
  100. int is_empty_stack(Stack *stack)
  101. {
  102. if(stack->n == -1)
  103.         return 1;
  104. else
  105.         return 0;
  106. }
  107. int visit_all(GRAPH *pG)
  108. {
  109. int i = 0;
  110. for(i = 0;i < pG->n; i ++)
  111. {
  112. if(visit[i] != 1)
  113.             break;
  114. }
  115. if(i == pG->n)
  116.         return 1;
  117. else
  118.         return 0;
  119. }
  120. //图的深度非递归遍历
  121. int DFS(GRAPH *pG,int v)
  122. {
  123.     Stack *stack;
  124. int i = 0;
  125.     stack = create_empty_stack();
  126.     push_stack(stack,pG->vex[v]);
  127.     visit[v] = 1;
  128.     printf(“V%d “,pG->vex[v]);
  129. while(!is_empty_stack(stack) || !visit_all(pG))
  130. {
  131. for(i = 0;i < pG->n;i ++)
  132. {
  133. if(visit[i] == 0 && pG->adjmatrix[v][i] == 1)
  134.                 break;
  135. }
  136. if(i == pG->n)
  137. {
  138.             v = pop_stack(stack);
  139. }else{
  140.             v = i;
  141.             push_stack(stack,pG->vex[v]);
  142.             visit[v] = 1;
  143.             printf(“V%d “,pG->vex[v]);
  144. }
  145. }
  146.     printf(“\n”);
  147.     return 0;
  148. }
  149. //队列的设计
  150. typedef struct node
  151. {
  152. int data;
  153.     struct node *next;
  154. }ListNode;
  155. typedef struct
  156. {
  157.     ListNode *front;
  158.     ListNode *rear;
  159. }Queue;
  160. //创建空队列
  161. Queue *create_empty_queue()
  162. {
  163.     Queue *queue;
  164.     ListNode *head;
  165.     queue = (Queue *)malloc(sizeof(Queue));
  166.     head = (ListNode *)malloc(sizeof(ListNode));
  167.     queue->front = queue->rear = head;
  168.     return queue;
  169. }
  170. //判断队列是否为空
  171. int is_empty_queue(Queue *queue)
  172. {
  173. if(queue->rear == queue->front)
  174.         return 1;
  175. else
  176.         return 0;
  177. }
  178. //入队
  179. int EnterQueue(Queue *queue,int data)
  180. {
  181.     ListNode *temp;
  182.     temp = (ListNode *)malloc(sizeof(ListNode));
  183.     temp->data = data;
  184.     temp->next = NULL;
  185.     queue->rear->next = temp;
  186.     queue->rear = temp;
  187.     return 0;
  188. }
  189. //出队
  190. int DelQueue(Queue *queue)
  191. {
  192.     ListNode *temp;
  193.     temp = queue->front;
  194.     queue->front = queue->front->next;
  195.     free(temp);
  196.     temp = NULL;
  197.     return queue->front->data;
  198. }
  199. //图的广度遍历
  200. int BFS(GRAPH *pG,int v)
  201. {
  202.     Queue *queue = create_empty_queue();
  203. int i = 0;
  204.     memset(&visit,0,sizeof(visit));
  205.     EnterQueue(queue,v);
  206.     visit[v] = 1;
  207. while(!is_empty_queue(queue))
  208. {
  209.         v = DelQueue(queue);
  210.         printf(“V%d “,pG->vex[v]);
  211. for(i = 0;i < pG->n;i ++)
  212. {
  213. if(visit[i] == 0 && pG->adjmatrix[v][i] == 1)
  214. {
  215.                 EnterQueue(queue,i);
  216.                 visit[i] = 1;
  217. }
  218. }
  219. }
  220.     printf(“\n”);
  221.     return 0;
  222. }
  223. int main()
  224. {
  225.     GRAPH G;
  226. int n;
  227. //输入顶点,初始化图
  228.     init_graph(&G);
  229. //初始化邻接矩阵
  230.     input_edge(&G);
  231. //图的深度遍历
  232.     DFS(&G, 0);
  233. //图的广度遍历
  234.     BFS(&G,0);
  235.     return 0;
  236. }

输出结果:

数据结构与算法(五)查询

很多时候,我们会比较在意查询的时间,因为这是用户最常使用的功能,并且是实时的需求,非常影响用户体验,以下是各种数据结构查询的效率,我们可以看到平衡二叉树等查找效率比较高,其实这是将时间前移了,因为平衡二叉树本身就是有序的,相当于已经对数据进行了一个排序,我们可以看到插入构造这个树的时间LOG(N)。

image

一.无序数据基础查找

像单链表这种无序队列,插入的时候很快的,直接加到末尾就可以,但是其查找确实耗时,使用了直接查找法。

所以为了加速查找的速度,需要将数据预先进行排序,一般就是生成的 时候就进行排序,比如数据库表加索引,构造二叉树,哈希表存储数据,这样在这些有序数据基础上进行数据查找就快多了,虽然在构造的时候会消耗时间,甚至让总时间都增加了,但是,有什么关系呢。

二.有序数据查找

无序数据查找效率比较慢,所以一般查找前都会排序,分担一部分的压力。

折半查找法

适用场景:针对已排序序列,并且只适用于顺序存储结构的序列,这样才能O(1)找到其中间值。但是这样一来,其插入,删除会变得比较低效,鱼熊不可兼得。

B树(二叉查找树)算法

其查找效率与树的深度有关。

HASH查找

算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

算法流程:

1)用给定的哈希函数构造哈希表;

2)根据选择的冲突处理方法解决地址冲突;

常见的解决冲突的方法:拉链法和线性探测法。 详细的介绍可以参见:  哈希表 。

3)在哈希表的基础上执行哈希查找。

这也是用空间换时间的例子之一。所以哈希表是查询效率的极致了。但是要解决好健冲突问题,比如拉链法,相当于将有共同哈希值的数据存储到一个链上,哈希值索引指向这个链,如果链COUNT>1,则再在链上顺序查找,这也有分治法的应用效果,基本上std::map 这种 kv存储结构就是哈希表的应用。这还可以衍生出进行大数据外排查找Top K问题。

数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。综合两者特性,设计一种寻址容易,插入删除也容易的数据结构,如拉链法实现的哈希表。

拉链法实现的哈希表应该也算是一个分块查找,索引查找的实现方式

分块查找(索引查找)

分块查找又称索引顺序查找,它是顺序查找的一种改进方法。

算法思想: 将n个数据元素”按块有序”划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……

这种也适合使用并行进行查找。

算法流程:

step1 先选取各块中的最大关键字构成一个索引表;

step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。

数据结构与算法(四)排序

根据待排序数据量能否被全部装载到内存中进行排序分为:内部排序外部排序。当然我们都希望直接在内存中进行排序,因为IO的延迟非常的大,但对于大数据集来说,内存是远远不够的,这时候就涉及到外排序,外排序通过读/写外存的次数来衡量其效率。基本上上学的时候学的都是内部排序,同时万不得已,都尽量使用内部排序,或者转化为内部排序。其实也就是说,我们要以空间换时间,以稳定性换时间,所以如何选择排序方法要综合场景来进行

一.基本排序

http://ibinguo.net/wp-content/uploads/2016/12/image_thumb8.png

image

冒泡排序->快速排序->归并排序

冒泡排序是最基本的排序算法,遍历所有数据,一次遍历查出最大值。所以如果要查询某个最大值也可以使用下冒泡。但是这个速度不敢恭维,所以有了变种快速排序,当然是以牺牲部分空间及稳定性为条件的。

快速排序快排是基础单线程排序中效率最好的了。以分治的思想进行排序,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

 

插入排序->希尔排序->并归排序

插入排序:遍历剩余所有数据,遍历待排序数据,将数据插入到一个已排序好的队列中,该已排序好的队列慢慢增大。

插入排序是每次将一个数据插入待排序序列,即步长为1希尔排序也可称为分组插入方法,则是步长>1,每个分组内使用插入排序或者二分插入排序。

并归排序:

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时,把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成,将它们依次两两归并得到长度为2的若干有序子表,再对它们两两合并。直到得到长度为n的有序表,排序结束。
归并操作的工作原理如下:

  1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  2、设定两个指针,最初位置分别为两个已经排序序列的起始位置

  3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

  4、重复步骤3直到某一指针达到序列尾

堆排序

堆实际上是一棵完全二叉树,利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。

二.适用场景

综合上述,得到的各种情况下的最优排序分别是:

(1)序列完全有序,或者序列只有尾部部分无序,且无序数据都是比较大的值时, 【直接插入排序】最佳(哪怕数据量巨大,这种情形下也比其他任何算法快)

(2)数据基本有序,只有少量的无序数据零散分布在序列中时,【希尔排序】最佳

(3)数据基本逆序,或者完全逆序时,  【希尔排序】最佳(哪怕是数据量巨大,希尔排序处理逆序数列,始终是最好的,当然三数取中优化的快速排序也工作良好)

(4)数据包含大量重复值,【希尔排序】最佳(来自实验测试,直接插入排序也表现得很好)

(5)数据量比较大或者巨大,单线程排序,且较小几率出现基本有序和基本逆序时,【快速排序】最佳

(6)数据量巨大,单线程排序,且需要保证最坏情形下也工作良好,【堆排序】最佳

(7)数据量巨大,可多线程排序,不在乎空间复杂度时,【归并排序】最佳

 

三.

数据结构与算法(三)树

这一节我们专门来看看树吧,因为这个的应用也是非常广泛。基本的就是二叉查找树,因为二叉查找树可能会出现跛脚的情况,一边长,一边短,所以就出现了平衡二叉树,根据其实现又有AVL树,红黑树。

1.二叉树查找树

定义

对于任何一个结点X

若它的左子树非空,则左子树上所有结点的值均小于等于X的值;             

若它的右子树非空,则右子树上所有结点的值均大于等于X的值;

遍历:

前序遍历:根节点->左子树->右子树

中序遍历:左子树->根节点->右子树

后序遍历:左子树->右子树->根节点

例如:求下面树的三种遍历


前序遍历:abdefgc

中序遍历:debgfac

后序遍历:edgfbca

按中序遍历二叉查找树,所得到的中序遍历序列是一个递增(或递减)的有序序列。

我们来说二叉查找树当然是和查找操作有关系,查找的时间复杂度是和高度H成正比的:log(h)。也可以这么说,二叉查找树基本操作的时间都是和树的高度H是成正比的。这些基本操作包括查找插入和删除,前驱后继等。遍历不在这里讲,以后会专门写有关遍历的文章,BFS,DFS,无栈非递归等。

查找

我们先来看一下查找:给定一个树的树根指针x和关键字k,返回指向关键字的指针,否则返回NIL。 TREE-SEARCH(x,k)伪代码

在递归查找的过程中遇到的结点即构成了一条由树根下降的路径,故TREE-SEARCH的时间复杂度是O(H)。

再来一个非递归版本的ITERATIVE-TREE-SEARCH,这个比递归的要快一些。


最大值和最小值

那么如何去找最大值和最小值呢?最大值肯定是二叉树的最右结点啦,从根结点开始沿着right指针一路走到right指针为空。而最小值肯定在最左结点,从根结点沿着left指针一路走到left指针为空。(此时说的二叉树是按中序遍历是从小到大)

	时间复杂度都是O(H),因为寻找的过程就是根结点一路下降的过程。

前驱和后继

找到最大值和最小值还不够,有时候我们需要寻找前驱和后继。如何寻找呢?我们这里来讲述一下中序遍历的的前驱和后继寻找。后序遍历和前序遍历的前驱后继的寻找和这是一样的道理。
后继
先说后继,对于一个结点X来说,后继无非是有3种情况: 1  X有右孩子,那么X的后继就是右孩子的最左结点。 2  X无右孩子,而且X是其父母的左孩子,那么X后继就是其父母结点(可能NIL)。 3  X无右孩子,而且X是其父母的右孩子,那么X的后继就是X的某个祖先(这个最低祖先的左孩子也是X的祖先),此时让父母成为新的X,寻找不断找X是其父母的左孩子的结点,如果此时出现一个X结点是其父母左孩子,那个父母就是X的后继。这个意思也就是说把第三种情况变成第二种情况。如果这个时候找不到则得到的是NIL结点。因为最大值是没有后继的,其他的肯定都有。 对于第一种情况很简单

对于第二种情况,更简单了,可能父母是NIL,即X结点是根结点。

对于第三种情况,找不到的话就是NIL。最大值没有后继。

伪代码

前驱
	再来看一下前驱,前驱和后继是对称的。如果你仔细看,你会发现刚才寻找后继2 、3 情况的过程是X一直向上查找X是否是其父母的左孩子,而此时X的前驱的分类是和他对称的,是一直向上寻找看X是否是其父母的右孩子,那么其父母就是其前驱。
	1  X有左孩子,那么X的前驱就是左孩子的最右结点。
	2  X无左孩子,而且X是其父母的右孩子,那么X前驱就是其父母结点(可能NIL)。
	3  X无左孩子,而且X是其父母的左孩子,那么X的前驱就是X的某个祖先(这个最低祖先的右孩子也是X的祖先),此时让父母成为新的X,寻找不断找X是其父母的右孩子的结点,如果此时出现一个X结点是其父母右孩子,那个父母就是X的前驱。这个意思也就是说把第三种情况变成第二种情况。如果这个时候找不到则得到的是NIL结点。最小值没有前驱。
对应第一种情况

对应于第二种情况,父母可能是NIL。

对应于第三种情况,找不到是NIL。最小值没有前驱。

伪代码
TREE-PREDECESSOR(x)
1 if left[x]≠NIL
2    then return TREE-MAXIMUM(left[x])
3 y←p[x]
4 while y≠NIL and x=left[y]
5      do  x←y
6          y←p[y]
7 return y
	时间复杂度都是O(H),就是一条自结点向上的路径罢了。
	综上所述 对于一颗高度为H的二叉查询树来说,静态操作SEARCH,MINIMUN,MAXIMUM,SUCCESSOR,PREDECESSOR等用时都是O(H)。
	对于一颗二叉树,要的不仅仅是静态操作,还需要动态操作。因为必然会有插入和删除操作,而且还要保持二叉排序树的性质。

插入

先来看如何插入结点Z,插入很简单的。先把结点Z的左右孩子left[z] 、right[z]和父母p[z]初始化,然后从根结点开始一直向下寻找Z的父母,找到之后就把孩子Z插入,如果是空树,直接把Z当成根结点。 在伪代码中,X初始化为根结点,Y始终是其父母,最后把Z插入。

TREE-INSERT的时间复杂度是O(H)。

删除

插入结点很简单,那么如何删除结点呢?删除结点之后还要保持中序遍历是一个相对位置不变的序列。对于删除一个结点Z,其实是要分类的。 1 如果Z没有孩子,直接删除,仅仅修改其父结点P[Z]的孩子为NIL即可。 2 如果Z仅仅只有一个孩子,那么删除Z之前要把Z的孩子赋值给其父母P[Z]的孩子(左|右)。这样一个拉链直接去删除Z了。 3 如果Z有两个孩子,这样就有点麻烦了。因为删除Z之后还有两个孩子,如果不好好处理会破坏二叉树的性质,我们删除Z一定要保持中序遍历的相对位置序列不变。这样有两种方法,因为只有保持性质即可,两种方法得来的二叉树不一定是一样的,但是都是正确的二叉树。 我们来看一下第三种情况的两种方法:假设删除的结点是P,而且中序遍历的序列是{....CL ,C....  QL,Q,SL,S,P,PR,F}删除P之后的中序遍历序列应该是{....CL ,C....  QL,Q,SL,S,PR,F}。S是P的前驱,PR是P的后继。

这就是未删除P之前的二叉树原型。
方法一
第一种方法是,先把P的前驱S的左孩子SL(S肯定无右孩子,左孩子可能是NIL)变成S父母Q的右孩子,删除S。然后把S的值全部给P,这就让P前驱S取代了P的位置,这样序列相对位置没有发生变化。

	可是真的是这样吗?这是老严数据结构书上的截图,算导上给的是找后继结点,然后和上边说的一样,就是把刚才的前驱换成后继。
	可是我想说的是这里忽略了一种情况,那就是如果前驱是其左孩子了怎么办?根据之前分析的前驱分类,在这里要删除的结点P肯定有两个孩子,那么对于前驱来说就只有两种情况,如果P前驱是左孩子的最右结点,刚才的分析没有一点问题,可是如果P前驱是其左孩子,也就是说左子树根结点没有右子树。那么按刚才的分析 就是说不通了。前驱S是P的左孩子,你还要把S的左孩子变成S的父母(P)的右孩子吗?那之前P的右孩子岂不是丢了??!!
	所以这个时候你要判断一点就是P前驱是否是P的左孩子,就是在找前驱的时候保留一个指针指向前驱的父母,最后判断是否和P相等,如果相等就把P左孩子的左孩子变成P的左孩子,然后P的左孩子(此时也是前驱)覆盖P。如果不相等,就按刚才说的做。
	算导给的,和这是一样的,只不过是对称找后继,如果后继是其右孩子也是尴尬。也可以和刚才一样,留个指针判断。
	我们要分类判断,如果判断得到P的前驱是其左孩子的话,那么直接将前驱取代P就好了,其他什么都不用做。或者像算导上说的找后继,后继是其右孩子的话就让后继取代他。也就是说如果一个结点的前驱或者后继是其孩子的话,直接让其孩子取代他就好了,很简单的,其他什么都不用做。
	不能想当然的以为前驱一定是左孩子的左右结点,后继一定是右孩子的最左结点。这样就算是前驱不是其左孩子,只要后继是其右孩子,就让右孩子取代他,两个孩子满足一个就可以减少很多的处理,优化算法,而且此时不必留指针再判断了。如何判断呢?如果P的左孩子没有右子树,那前驱就是左孩子。如果他的右孩子没有左子树,那后继就是其右孩子。
伪代码
TREE-DELETE(T,z)
1 if left[z]=NIL or right[z]=NIL
2    then if left[z]=NIL
3            then  p[right[z]]=p[z]
4                  left[p[z]]=right[z]
5         else if right[z]=NIL
6            then p[left[z]]=p[z]
7                 left[p[z]]=left[z]
8 else if  right[left[z]]=NIL
9  then key[z]=key[left[z]]
10              p[left[left[z]]]=z
11              left[z]=left[left[z]]
12 else if left[right[z]]=NIL
13         then p[right[right[z]]]=z
14              right[z]=right[right[z]]
15 else
16      then y=left[z]
17           while right[y]≠NIL
18                 y=right[y]
19           p[left[y]]=p[y]
20           right[p[y]]=left[y]
21           key[z]=key[y]
	这是一种分类的做法,老严给的版本是找后继判断,算导给的是找前驱判断,我这里给他综合了一下,更加的优化。不过算导版本虽然没有分类,但是有各种判断,代码很紧凑。虽然我感觉没我的好,不过还是在这里贴一下。

方法二
	接下来我们看第二种方法,这种方法的好处是不像刚才那么有BUG,不过好像大多数书上举的例子都是第一种,汗。难道第一种比第二种的简单?我们看一下吧
	先令P的右孩子PR成为其前驱S的右孩子,然后将P的左孩子C成为P父母F的左孩子,删除P。这样就不用管C是不是其前驱了。C就是其前驱也是把PR给C的右孩子,序列的相对位置是不会发生变化的。

来看一下伪代码
TREE-DELETE(T,z)
1 if  left[z]=NIL or right[z]=NIL
2     then if left[z]=NIL
3             then  p[right[z]]=p[z]
4                   left[p[z]]=right[z]
5          else if right[z]=NIL
6                  then p[left[z]]=p[z]
7                       left[p[z]]=left[z]
8  else  9       y=TREE-PREDECESSOR(z)
10      p[right[z]]=y
11      right[y]=right[z]
12      p[left[z]]=p[z]
13      left[p[z]]=left[z]	代码很简洁,我反倒觉得这个简单,还不麻烦。这两种方法都很简单的,一时想不起,就拿笔画一颗二叉树,很快就明白了。一定要动手画一下。时间复杂度很明显是O(H)。	上边所说的二叉树的大部分操作的时间复杂度都是O(H),H是树的高度。大家一听高度想当然以为就是lgN,其实非也。一个好的二叉树高度可能是O(lgN),即便是如此,可是经过了很多的插入和删除,高度就会发生变化。就像是一开始只有一个结点的二叉树,最后变成了一个高度为N-1的链。这虽然还是树,可是已经不是我们需要的了,时间复杂度太大了(O(N)).
	可是我们怎么才能保证一个树的高度是lg级的呢?随机。一个N个关键字随机的构造的二叉树的高度是lgN。可是经过删除和再次插入的洗礼,高度也不会一直是lgN。所以我们二叉树期望高度是O(lgN),平均时间复杂度是良好的,不过还是不可避免的是会出现最坏情况。这个时候我们就不能仅仅依靠随机了。

平衡二叉树

不过我们不会任由这种最坏情况的发生,我们可以对二叉树做一些平衡的处理,接下来就介绍一下平衡二叉树,这个在最坏情况的时间复杂度都是lg级。 平衡二叉树是为了避免刚才的最坏情况产生的,平衡是指所有的叶子的高度趋于平衡,更广义的是指在平衡二叉树上所有可能查找的均摊复杂度偏低。几乎所有平衡树的操作都基于树的旋转操作,通过旋转操作可以使得树趋于平衡。AVL树,红黑树,伸展树,Treap树等都是平衡二叉树。

AVL树

AVL树仅仅只是平衡二叉树的一种而已,具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵AVL树。若二叉树上结点的平衡因子定义为该结点的左子树的高度减去右子树的高度。那么AVL树的平衡因子就只能是0,-1,1。如果有一个结点的平衡因子的绝对值大于1 ,那么这个二叉树就不是AVL树。如果由于插入和删除结点导致AVL树不平衡,那么就从这个结点开始进行一次或多次的左右旋转和高度的调整,最后使二叉树变得平衡。 老严那本书上讲的平衡二叉树仅仅只是AVL算法的一种平衡二叉树而已,不代表全部的。注意平衡二叉树一种平衡树,而AVL算法只不过是调整树的高度保持平衡的算法而已,不是平衡二叉树的全部。平衡二叉树有很多种,这里我把一些以前的AVL笔记中中的旋转K过来看一下吧。

红黑树

这里我们主要是说一个特殊的平衡二叉树,那就是红黑树RB-TREE。RB-TREE的好处在于检索很快,主要用于关联式容器。Set map multiset  multimap的底层实现都是RB-TREE,这些关联容器存入的时候都是自动排序,查询的时候都是很快。不过代价就是RB-TREE树的插入和删除带来的麻烦很多,不过还好的是 它可以在O(log n)时间内做查找,插入和删除。 红黑树在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。每一个结点有5个域:color key  left  right  p。如果某个结点没有孩子或没有父结点,则把相应的结点设为NIL,颜色BLACK。 红黑树是每个结点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求(性质): 性质1. 每个结点只能是红色或黑色。 性质2. 根结点是黑色。 性质3. 所有叶子结点都是黑色(叶子是NIL结点)。 性质4. 每个红色结点的两个孩子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点) 性质5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

	在很多树数据结构的表示中,一个结点有可能只有一个子结点,而叶子结点包含数据。这种表示红黑树是可能的,但是这会改变一些属性并使算法复杂。为此,我们使用 NIL来表示叶子结点。如上图所示,它不包含数据而只充当树在此结束的指示。这些结点在绘图中经常被省略,导致了这些树好像同上述原则相矛盾,而实际上不是这样。与此有关的结论是所有结点都有两个子结点,尽管其中的一个或两个可能是空叶子NIL。有点时候为了节省内存把所有的NIL连在一起当成一个NIL[T]哨兵,代表所有的叶子NIL和父母结点是NIL的结点。
	结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。
	要知道为什么这些特性确保了这个结果,注意到性质4导致了路径不能有两个相连的红色结点就足够了。最短的可能路径都是黑色结点,最长的可能路径有交替的红色和黑色结点。还有注意的是叶子节点都是NIL,它不包含数据而只充当树在此结束的指示。所以根据属性5所有最长的路径都有相同数目的黑色结点,这就表明了没有路径能多于任何其他路径的两倍长。
	我们定义黑高度BH(X)为从结点X出发(不包括X)到叶子结点的任意一条路径上,黑色结点的个数。这样我们就会得到一个结论:一颗有N个结点(不包括NIL叶子)的红黑二叉树的高度至多是2lg(N+1)。
	简单证明一下:由于以X为根的RB-TREE至少包含2^BH(X)-1个结点。因为对于高度为0的RB树,结点数目是0,对于一个结点高度大于0的RB树,左右孩子的颜色可能是红,也可能是黑,所以孩子的黑高度BH有可能和父母一样,也有可能比父母少1。所以孩子的结点数目加上父母结点X就和X为根的RB树的结点数目是一样的,也就是说2^(BH(X)-1)-1+2^(BH(X)-1)-1+1=2^BH(X)-1,所以假设成功。此时呢,假设N个结点的RB树高度是H,则黑高度至少是H/2,所以呢,2^BH-1=2^(H/2)-1<=N,H<=2lg(N+1),得证。
	所以对于红黑树的所有动态和静态的操作都可以在O(lgN)时间内实现。
旋转
可是经过了删除和插入,红黑树的性质会发生变化,所以需要一些旋转操作和结点颜色的改变来维持性质。这里我们先来看一下旋转的知识。旋转分左旋和右旋。

	当在某个结点x上做左旋操作时,我们假设它的右孩子y不是NIL,x可以为RB树内任意右孩子而不是的结点。旋以x到y之间的链为“支轴”逆时针旋转,它使y成为该子树新的根,而y的左孩子b则成为x的右孩子。而右旋和左旋是对称的。Y的右孩子X也不是NIL,这时候以y到x之间的链为“支轴”逆顺时针旋转,使x成为新的子树的根,x的右孩子变成y的左孩子。因为左右对称,这里我们只给出左旋的伪代码。假设X的右孩子不等于NIL,而且根的父母结点是NIL。

	时间复杂度都是O(1),旋转的时候只有指针在变化,而其他的所有域都不会改变。至于RB树颜色的变化是和旋转无关的。还要明确一点的就是旋转不改变中序遍历的相对顺序
插入
现在就先说插入吧,因为插入毕竟比删除简单一些。在一个有N个RB树中插入一个结点可以在O(lgN)时间内完成。 插入一个结点肯定是要赋予颜色的,我们是给他红色,还是给他黑色呢? 5大性质: 性质1. 每个结点只能是红色或黑色。 性质2. 根结点是黑色。 性质3. 所有叶子结点都是黑色(叶子是NIL结点)。 性质4. 每个红色结点的两个孩子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点) 性质5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。 根据5大性质我们知道,如果把插入的结点赋予黑色,则会违反性质5,导致黑高度发生变化,这个是很麻烦的。待会删除的时候你就会明白。而如果赋予红色,则只会违反性质2和4,如果是性质2,说明插入的是根结点,直接把根结点变成黑色就好。如果违反性质4,说明插入结点的父节点是红色的,此时可以通过旋转和结点颜色的改变搞定,这个不是很麻烦。我们只讨论违反性质的情况,不违反的就不说了。我们来看一下。 RB-TREE的插入和之前的二叉查找树的插入代码有些不同,所有的NIL结点换成哨兵NIL[T],插入的结点初始化left和right都是哨兵NIL[T],颜色直接赋予红色。然后专门写一个调整算法RB-INSERT-FIXUP。这里我们只看调整算法,之前的插入我们已经讲过了,不明白看前面章节。 我们假设父节点是P,叔叔结点是U,祖父结点是G,插入结点是N。同时假设Z的父节点P是祖父G的左孩子,这和是右孩子是对称的,我们只讨论P是G左孩子的情况。 如何调整呢?我们要寻找一些辅助,父节点P肯定是要参与的,因为要看他是不是红色,红色的话就调整,不是红色的话直接给根结点变黑色(不判断都行),不管其他的。而且可以肯定是祖父节点G肯定是存在的,而且是黑色(NIL或者其他,因为插入之前肯定满足RB树的性质)。如果父结点P是红色,那么我们如何调整?因为除了根结点是黑色之外,其他的都不晓得,我们也不能随意的调整。
情况一
	我们不能贸然调整把插入结点N变成黑色,不过如果父结点的兄弟结点,也是插入结点N的叔叔结点U,他如果是红色的话。

	此时我们可以把U和P都变成黑色,但是此时以祖父的父节点G为根的子树的黑高度变化了,也即是+1了。这就违反了性质5,唉,千万不敢违反性质5,超级麻烦。所以我们做一个变通,可以把祖父结点G变成红色,此时的违反性质的可能性就落到了G身上,这时就把G当成插入结点N,继续进入调整算法开始调整。
	也就是说我们可以把这个插入结点N和父节点P的连续红色的违反情况向上移动,就是把违反性质的结点向上调整,这样直到最后变成根结点是红色的,根结点父节点是NIL[T]黑色,此时直接把根结点变成黑色即可,很nice。

	此时的G就变成了新的插入结点了,继续调整,最多到根结点。情况一:如果父节点P和叔父节点U二者都是红色,则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质5)。
	可是如果叔叔结点U是黑色呢?这就不能按刚才说的调整了,我们要换一个策略了。此时我们要分情况,插入结点N是父节点P的左孩子还是右孩子,这是不一样的。
情况三
如果N是P的左孩子

	此时我们直接把父节点P变成黑色,然后以G--P为轴顺时针旋转(右旋),P变成了根,但是G变成了P的右孩子,这个时候两边的黑高度就发生了变化,右边的+1了,此时我们可以把G变成红色,这样两边就均衡了啊。而且
此时算法直接就结束了,因为性质都保持住了。

情况二
可是如果N是P的右孩子呢?

	这样看起来很不好搞啊,旋转变色,都达不到要求,都是无用的。我们可以把这个N右孩子变成刚才说的左孩子吗?看起来是不可以。不过我们可以发现的是父母和孩子结点的变换是可以通过旋转来做的,也就是说通过一次旋转,孩子可以变成父母,父母也可以变成孩子,而新的孩子和之前的孩子的左右是相反的。而此时N和P都是红色,我们通过一次的左旋,可以把P变成N的左孩子,也就是相当于P变成插入结点是红色,N变成父节点是红色,叔叔结点U是黑色,则和刚才说的是一样的。

	也即是变成了刚才那种情况。所以我们把这种情况称为第二种,刚才说的是第三种。因为第二种到第三种是直接过度的,不是互斥的情况。虽然我们忘了一种情况,那就是叔叔不存在,但是这并不影响我们刚才分析的结果。
情况二:如果父节点P是红色而叔父节点U是黑色或不存在,并且插入节点N是其父节点P的右孩子。我们以P-N为轴进行一次左旋调换插入节点N和其父节点P的角色(不是颜色)

情况三::如果父节点P是红色而叔父节点U是黑色或不存在,并且插入节点N是其父节点P的左孩子。我们可以把P重绘为黑色,并重绘G为红色。然后以P-G为轴以进行一次左旋调换节点P和节点G的角色。
	情况一要进入继续调整,最坏的情况是向上调整到根。情况二直接进入情况三。情况三调整完了之后调整算法就结束了。
	上伪代码,这个伪代码和刚才分析的是一样的,如此同时还是只有半边代码,就是只有父节点P是祖父结点G的左孩子的情况。不过在伪代码里,插入结点是z,y是其叔叔。
INSERT伪代码

RB-INSERT-FIXUP伪代码

给一个例子看看,很好的例子,囊括了三种情况。
这是情况一的情况

情况一调整结果变成了情况二了。

情况二调整结果变成了情况三了。

情况三调整完了就结束了。

	很明显我们的RB-INSERT的1-16行的时间代价是(lgN),而对于RB-INSERT-FIXUP中,只有情况一才会发生循环,即便是循环到根,也不过用时O(lgN),所以总的时间花费就是O(lgN)。而且这个RB-INSERT-FIXUP过程的旋转不超过2次,也就是情况二和情况三各旋转一次O(1),旋转过后算法就结束了。
删除
接下来我们来看看如何删除RB-TREE的结点。
	对于一个有N个结点的RB-TREE来说,删除一个结点要花费的时间就是O(lgN)。与插入相比,只不过是更加的复杂罢了。我们来分析一下。删除一个二叉树的结点我们说过了,这里不再说,之说删除结点之后如何保持红黑树的5大性质。
5大性质:
	性质1. 每个结点只能是红色或黑色。
	性质2. 根结点是黑色。
	性质3. 所有叶子结点都是黑色(叶子是NIL结点)。
	性质4. 每个红色结点的两个孩子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
	性质5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。
	如果删除的结点的颜色是一个红色,我们压根就不需要调整,因为这并不违反任何一个性质。因为各结点黑高度没有变化,不存在相邻的红色结点,删除的也不是根结点。如果树的结点只有一个,那么删除了也不需要调整。如果树的结点不是一个而且删除的结点是黑色的,那么就有可能违反性质4,因为可能有两个相邻的红色结点。删除了根结点,造成新的根结点是红色可能违反了性质2。而且删除黑色的结点会违反性质5,导致黑高度不一致。
	我们如何调整呢?假设删除了结点Y,肯定有占用他位置的结点是X,X可能是他的前驱或后继,X也可能是Y的孩子,或者是哨兵NIL[T]结点。如果X结点本身是红色,也就是说有可能违反性质4和5,那我们直接赋予它黑色就解决了。如果红色结点X变成了根违反性质1,也直接赋予黑色就OK。现在的问题是如果X结点是黑色而且不是根结点,违反了性质5,黑高问题就不好解决了。这里我们主要说如何解决这一个情况,前两个情况很easy,不需细说了。
	之前说过如果违反了性质5,会很麻烦,这会你就知道了。违反了性质5,我就很拙计了。当然这也不是解决不了的。那如何保持性质5呢?我们总不能期望他不违反性质5吧。这里我们用一个技巧,就是假设删除的结点Y把它的黑色性质X结点了,也就是说X结点多了一重黑色,就是黑+黑,这样的话黑高度就一致了,性质5就满足了。
	当然这只是假设,我们假想的,不过这有助于我们解决问题。这个黑+黑结点是X结点,他的颜色属性还是黑色,只不过用一个指针指向他,他便多了一层黑色。不断调整的过程,会出现新的X结点,这时候指针指向的结点不一定会是原来的X了,不过还是会多一层黑色。而且在不断旋转的过程会出现旋转前后两边子树黑高发生变化的情况,此时如果N这边的子树黑高+1了,那N头上的多于黑色就没有了,舍弃。这就是我们的最终目的。
	这也就是调整的麻烦之处,接下来我们看看他如何麻烦。当然这还是要分类的。这里我们只考虑结点X是其父节点左孩子的情况,对称的情况不再讲。
	我们假设占用被删除结点的位置的结点是N,N的兄弟结点是S,N的父亲结点是P,S的左孩子是SL,S是右孩子是SR。要明确一点的是S不是NIL[T],因为如果是NIL[T],那两边的黑高现在就不一样,即便是没删除之前,RB-TREE也不会出现这种情况的。
情况一
如果兄弟结点S是红色,那么S的父亲结点P和S的孩子SL和SR都必然是黑色,此时N也是黑色的。

	此时如何调整?指针指向的是N,N是黑+黑。此时父亲结点P变红色,S变黑色,然后以P-S为轴左旋。此时指针指向的还是N,看起来好象是没什么变化,其实是变了,父亲结点P变成了红色,兄弟结点变成SL还是黑色。不要着急,这只是第一步而已嘛。

情况一:如果兄弟结点S是红色的(隐含的意思P,SL,SR都是黑色),那么我们就交换父节点P和兄弟结点S的颜色,即P变红色,S变黑色,然后以P-S为轴左旋。	如果兄弟结点是红色的话,只可能有这一种情况,因为父节点和孩子结点的颜色都是定好的黑色。接下来看兄弟结点是黑色的情况,这样他的孩子结点和父亲结点的颜色可就不唯一了,这可以分好几种情况的。
情况二
如果N的兄弟结点S是黑色的,而且两个孩子结点都是黑色的。N还是被指针指向,黑+黑。(P的颜色不晓得)

	如何调整?此时我们并不知道P的颜色,我们也不需要去判断。我们假设N和S都脱掉一层的黑色(两边路径上的黑色结点数还是相同),那N变成了正儿八经的黑色了,指针也不指向他了,而S脱掉黑色就只能变成了红色。而此时经过P的路径在这边少了一个黑色,黑高-1,所以我们要用指针指向他,给他多一层的黑色,这样经过P的路径在这边的黑色就不变了,这样多好。

	此时指针指向的是P(新的N)多了一层黑色,黑+黑或者是红+黑。有变化吗?当然了,看起来好像回到了情况一(兄弟S是红色),其实不是。因为新的N是P,这样指针指向的结点不断的向上移动,至多变成了根结点,那敢情好,直接赋予黑色,OK搞定。
情况二:如果兄弟结点S是黑色的,而且S的两个孩子也都是黑色的。直接把N变成黑色,S变成红色,用指针指向P,P多了一层黑色。
情况三
如果N的兄弟结点S是黑色,不过S的左孩子SL是红色的,右孩子SR是黑色的。

	那么如何调整?此时把SL和S的颜色交换,即SL变成黑色,S变成红色,然后以S-SL为轴右旋。此时N的兄弟变成了SL,而SL的右孩子变成了红色。

情况三:如果N的兄弟结点S是黑色,而且S的左孩子SL是红色的,右孩子SR是黑色的。此时把SL变成黑色,S变成红色,然后以S-SL为轴右旋。
情况四
此时N的兄弟S的右孩子就变成了红色,而左孩子不晓得。这种情况就是我们要说的情况四,情况三直接过渡到情况四,相互不排斥,其实是在一个分类里面。

	这样的话就是直接交换P和S的颜色,P变成黑色,而S变成P的颜色(不定),S的右孩子SR也变成黑色。然后以P-S为轴左旋。此时只有S的颜色不定,可是此时S的孩子都是黑色,S是什么色都无所谓了。此时算法就结束了,调整完毕。

算法为什么就结束了呢?因为调整的前后左边的子树的黑高+1了,所以此时N的多一层黑色就没用了,要舍弃。就是说我们解决了黑高的问题,性质5保持住了。
情况四:如果N的兄弟结点S是黑色,而且S的右孩子SR是红色的。那么交换P和S的结点颜色,即S变成P的颜色(不定),P变成黑色,SR变成黑色,然后以P-S为轴左旋。
	OK,大功告成一半,接下来上伪代码。伪代码中Y是要删除的结点,X是替代Y的结点,W是X的兄弟。调整算法是RB-DELETE-FIXUP。
RB-DELETE(T,x)
........
if color[y]=black
   then RB-DELETE-FIXUP(T,x)

     RB-DELETE-FIXUP的时间复杂度是O(lgN),因为只有情况二需要循环,循环次数最多是O(lgN)。情况 1 、3、 4最多需要旋转3次和一些颜色的改变而已。所以RB-DELETE-FIXUP过程要花费O(lgN)的时间,至多需要3次旋转。总的来说红黑树是很不错的,很快,所以很多容器的底层都用RB树。
	OK,这样红黑树就差不多说完了,以后有新的理解还会继续更新。

数据结构与算法(二)概述

数据结构与算法都比较严谨,找了一篇通俗的介绍篇。

http://www.matrix67.com/blog/archives/90

《数据结构与算法分析》

4月7日买起来看,前几天才看完。这可以说明很多问题,比如,学习很紧张,没有时间;书本身很好,很有看头;看书看得很细心,很有耐心。
    打算大致写一下书里的内容。
    Data Structures and Algorithm Analysis in C, Second Edition,机械工业出版社。封面很丑,一个黑底版,上面有些大理石花纹,正中间生硬的摆一个原版封面,同样丑。一共12章,近400页。
    400多页是很多的。我们必须要“把厚书读薄”,厚的变薄的,薄的变一页,一页变一行,一行变成一个字。因此,我要在有限的字数内把整本书说完。

    算法分析,就是复杂度的问题。复杂度只算“最要命的”,比如,执行n^2的算法前来个快排根本不拖速度,n^2多的都豁出去了不在乎区区一个nlogn。书里对复杂度进行了严格的定义,包括O()、o()、Θ()、Ω()四种符号。简单地说,O(n^2)就是顶破天了搞个n^2次;o(n^2)就是天花板不到n^2,比n^2矮一点(比如希尔排序就是o(n^2),因为它再倒霉也达不到n^2);Ω(n^2)就是说某个算法随便怎么至少都要耗费n^2,比如所有基于比较的排序都是Ω(nlogn);Θ(n^2)就是说它即是O(n^2)又是Ω(n^2),被天花板和水泥地夹在中间了,动不了了,就是它了。这里面有一个经典的例子,就是最大子序列(找数列中连续一段数之和最大)的四种算法,复杂度分别为O(n^3)、O(n^2)、O(nlogn)和O (n)。这书一个特色在于,对每种数据结构都有严格的算法复杂度证明,这往往是看上去最头痛的部分。

    表、栈和队列是三个基本的数据结构。说穿了表就是把数据找起来排排坐吃果果,找什么东西都来把整个队伍找一遍。栈就是一个桶,后放进去的先拿出来,它下面本来有的东西要等它出来之后才能出来,就好像你看到了一个丑人不可能今天的中饭还没吐出来就先把早饭吐出来了。栈是拿来模拟多个过程的调用的(比如递归),实际点的用途就是表达式计算队列好比堵车,先进去的先出来。先进队先买票,不能插队。常拿来实现广搜

    树,是一种植物,有很多枝枝丫丫。不同的是这里的树是倒着的,树枝朝下长。最上面叫根,尖尖的地方叫树叶,生出树叶的是他爸,他爸生的是他儿子。不管是根是树叶还是儿子还是儿子他爸都叫节点。我们常常把数据储存在节点上,并且以后还要不断地插入、改变和删除数据。
    二叉树就是每个分叉的地方最多分两个岔,而且还分得清左右。二叉查找树就是说把数据存在节点上,而且左边的都比他爸小,右边的都比他爸大,以后要找哪个数就可以只找其中的一边,一半一半地扔掉。在二叉查找树里也可以插入一个数,删掉一个数(只有一个儿子好办,有两个就把右边的最小的一个拿来替代这个),找最小的数(一直往左走),找最大的数(一直往右走),但是容易搞着搞着的树就变畸形了,比如说左边猛起长右边萎缩导致以后往左边走要走很久。我们就需要一种方法来让树左右差不多一样多而且左边的值仍然比右边的小。事实上这种方法已经找到了,而且不只一种方法,而是一卡车的方法,比如AVL、Splay、红黑树、Treap等。几种方法都靠一个叫“旋转”的技巧,就是把几个节点怎么个一转,左边的就跑到右边去了一点。看下面这个图你就明白了。

         ①                   ②
        /        旋转       / 
      ②   ZZ    ——>    XX  ①
     /                        / 
    XX  YY                    YY  ZZ

这样一来左边就少了,如果左边的XX本来很多的话就可以往上提一层从而平衡。同样地,右边多了反过来做就是了。这只是最简单的“单旋转”,事实上还有很多其它的较复杂的旋转方法。Splay树就是把刚才访问过的节点转啊转啊转啊转转到最顶上去,Treap就是每个节点附加一个随机的数,随时通过旋转保持儿子的这些随机数比他爸大,其余的有点复杂。这些方法都能使二叉查找树相对地平衡一些,防止畸变导致的时间浪费。
    B-树和二叉查找树有两个不同,一个是节点不存数据,数据全在树叶子上,二个是它不一定是二叉。数据仍然左边小右边大方便查找。每个节点最多的儿子数有限制,最多三叉的叫2-3树,最多四叉的叫2-3-4树。因为只有树叶上有数据,所以可以递归地用分裂的方法处理新插入后出现的分叉比规定的最多的儿子个数时还多的情况。比如,2-3树中如果哪里分了四个岔,就把它重新分成两个两个的岔。我们还规定,除了根以外,每个节点最少的儿子数是规定的最多儿子数的一半,除不尽取上整。容易想到,删除的话可以把插入时的分裂反过来做,什么时候只剩一个儿子了就和旁边的合并起来。

    Hash表又叫散列表,一般用于判断有没有重复。比如我想找我们班有没有两个一天生的,我们不必每两个人都来比较一次,而是准备一个年历,让人一个一个上去在他的生日那天那里画一个圈,如果谁要画圈时发现那里已经有一个圈了,就找到了一对。这个很简单,不说了。

堆,就是一陀一陀的东西。头重脚轻不算堆,要上面小下面大才算一个堆。堆是一棵二叉树,满足下面的始终比上面的大。它和二叉查找树比较起来既有好的又有不好的:好的就是要想知道数据里的最小值时根本就不用找了,直接就是最顶上的那个了;不好的就是堆除了这个以外基本上不能做别的事了。除了最顶上的那个以外,你几乎没办法控制其余的部分。当然,插入和删除数据这种基本操作还是可以做的。插入就是把数据暂时先放在最下面的某个位置,然后通过与它上面一个进行比较、交换不断往上冒直到已经到了自己的位置不能再向上为止。删除反起来,通过不断交换往下沉一直沉到底。因为是往下走,所以要考虑到一个把左边的放上来还是把右边的放上来的问题。当然,为了保证堆上小下大的性质,应该把小的一边换上来。刚才说过,由于你只能“看”到最顶上的东西,不知道中间部分是什么样,我们通常只删除最小的(最上面的)那个节点。其实堆还有一个最大的好处:容易写代码。因为我们可以有意让数据把树“排得满满的”,满到它是一行一行挨着排下来的。这叫做“完全二叉树”。我们可以给完全二叉树编个号,从上到下从左到右挨着数下来。根是1,找左儿子就乘2,找右儿子就乘2加1,找它爸就 div 2。以后叫谁就是谁,很方便。这样整个树就可以用一个数组实现了。由于堆基本上只用来找最小,因此如果某个问题要求很复杂的话,最好还是用成二叉查找树;当然,如果问题只要求插入、删除和找最小三种操作,你应该毫不犹豫地选择堆,毕竟找最小时堆方便得多,写起又简单。什么时候出现这种问题呢?比如说,我的女友排起队的,我每次要选一个最纯洁的,就是受那些的影响最小的人。每当我遇见了一个新的美女,我就把她放在这个队伍里合适的位置供我以后娱乐。这时,我只关心每次插入、取最小和删最小。这个队伍就可以用一个堆来优化。因此,堆还有一个形象的名字叫优先队列。如果谁问题目要求不找最小找最大怎么办,那人肯定是个傻子,把堆变通一下,上大下小不就完了吗?
    研究堆麻烦的地方就是堆的合并。如何把两个堆合并成一个堆?这个解决了很有用,至少上面的这些操作跟着全部统一了:插入就是与一个单节点的堆合并,删除根就是把根不要了,把根的左右两边(显然还是堆)合并起来。一个简单的办法就是递归地不断把根大的堆往根小的堆的右边合并,把新得到的堆替换原来的右儿子。注意递归过程中哪个根大哪个根小是不停在改变的。这样下来的结果就是典型的“右倾错误”,而且破坏了完全二叉树的完美。为此,我们想要随时保证堆的最右边尽量少。于是,干脆不要完全二叉树了,不过是多写几行代码嘛。这个不存在像二叉查找树那样“某一边越做越多”的退化问题,因为对于一个堆来说,反正我只管最顶上的东西,下面平不平衡无所谓,只要不挡我合并的道就行。于是,我们想到人为下一个能让堆尽量往左边斜的规定。这个规定就是,对于左右两个儿子来说,左边那个离它下面最近的两个儿子不全(有可能一个都没有)的节点的距离比右边那个的远。这规定看着麻烦,其实还真有效,最右边的路径的长比想像中的变得短得多。这就叫左式堆(左偏树)。这下合并倒是方便了,但合并着合并着要不了多少次右边又多了。解决的办法就是想办法随时保持左式堆的性质。办法很简单,你合并不是递归的吗?每次递归一层后再看看左右两边儿子离它下面没有两个儿子的节点哪个远,如果右边变远了就把左边右边调一下。由于我们已经没有用数组实现这玩意了,因此链表搞起很简单。这个对调左右的方法给了我们一个启发:哪里还要管什么到没有两个儿子的节点的距离嘛,既然我每次都在往右合并,我为什么不每次合并之后都把它对调到左边去呢?这种想法是可行的,事实上它还有一个另外的名字,叫斜堆。
    二项堆更强,它也是堆,也能合并,不过它已经超越了堆的境界了:它不是一个堆,而是满屋子的堆。也就是说,找最小值不能再一下子找到了,而是要把二项堆中的每个堆的顶部都看一下。二项堆的合并也很强,直接把根大的堆放在根小的堆的下面。这意味着二项堆的每个堆都可能不是二叉树了。这增加了编程的难度,不过可以用一个叫做“左儿子右兄弟”的技巧来解决问题。这个技巧,说穿了就是仍然用二叉树来表示多叉树:把树画好,然后规定节点的左儿子是下一层的最左边那个,右儿子就是它右边那个。就是说,左儿子才是真正的儿子,右儿子不过是一起生出来的。为了让二项堆好看些,让堆的个数和大小保持在一个能快速操作的数目和比例内,二项堆作出了一个明智的规定:每个堆的大小(总的节点个数)只能是1、2、4、8、16…中的一个,且每种大小的堆只能有一个。若干个互不相同的2的幂足以表示任意一个正整数,因此这个规定可以保证不管多大的二项堆都能表示出来。保持这个性质很简单,遇到两个大小相等的堆就合并起来成为一个大一号的堆。由于总是两个大小相等的堆在合并,因此二项堆中的每一个堆都有一个奇妙的样子,看看本文结束后下面附的一个大小为16的堆的示意图,再看一下,再看一下,你就能体会到了。图下面有一个用“左儿子右兄弟”法表示的同样的树,其中,往下走的线是左儿子,往右走的线是右儿子。
    最后简单说一下Fibonacci堆。保持一个跟着变的数组记录现在某个节点在堆中的位置,我们还是可以对堆里的数据进行一些操作的,至少像删除、改变数值等操作是完全可以的。但这个也需要耗费一些时间。Fibonacci堆相当开放,比二项堆更开放,它可以不花任何时间减少(只能是减少)某个节点的值。它是这样想的:你二项堆都可以养一屋子的堆,我为什么不行呢?于是,它懒得把减小了的节点一点一点地浮上去,而是直接就把它作为根拿出来当成一个新的堆。每次我要查最小值时我就再像二项堆一样(但不要求堆的大小了)一个个合并起来还原成一个堆。当然,这样的做法是有适用范围的,就是前面说的数值只能是减少。在什么时候需要一个数值只减少不增加的堆结构呢?莫过于Dijkstra一类的图论算法了。所以说,这些图论算法用Fibonacci堆优化可以进一步提速。
有一个女人的男人很幸福。事实上,这是片面的。应该说,有不止一个女人的男人更幸福。但是,这样会坏了我的人品,而且被女的知道了也不好。两个耍得好的女人话很多,秘密在女人中传得很快。于是,我打算不同时和两个耍得好的女的耍朋友。后来我意识到,这样也不行。女人太无敌了,即使A与B耍得好,B与C耍得好,A和C的消息也是互通的。哪怕只有一个朋友关系也能把两群人联系在一起。我不得不改变策略,使得我的女朋友之间没有任何渠道传递信息。也就是说,在上面的A、B、C三个人中,虽然A和C没有直接的联系,但我也不能同时和A、C耍。不久后,我想知道,某两个女人是否可以通过某条“朋友链”传递信息。这就是所谓的等价关系——基本上算是判断一个无向图的连通性。就像很多个集合,每次选两个并成一个,而且我们随时想知道某两个元素经过前面的合并后是否在同一个集合内。怎么办呢?后来有一天,我发现那些小女生喜欢玩些认亲戚的游戏,什么谁是谁妈,谁是谁姐,谁是谁女儿之类的(不知道为什么这些疯女人喜欢搞这些)。我突然恍然大悟,我的问题可以用树结构来完成。亲戚的亲戚还是亲戚,但有一点总相同:所有亲戚的始祖总是一样的。始祖一样的都是一伙的。因此,把两个集合并在一起,只要让其中一个集合的根成为另一个集合中的某个元素的一个儿子就行了,这种家谱关系的改变将使前面的集合中所有的元素拥有和后面那个集合一样的鼻祖,而这将成为这些元素的“标志”。这个想法的灵感是来自女人世界的,因此女人还是有一定的作用。     这就叫并查集,又叫不相交集。它可以合并两个集合并且查询两个元素是否在同一集合。我们有一个很有效的剪枝:递归时顺便把路上经过的祖祖辈辈全部变成根的儿子。这样的程序只用2行来解决。function find_set(x:integer):integer;   begin   if x<>p[x] then p[x]:=find_set(p[x]);   exit(p[x]);end;
    p[x]表示元素x的父亲的位置。一开始,p[x]都等于x自己,表示自己一个人是一个集合。函数find_set(x)将返回x所在集合(一棵树)的根。     并查集还有些其它的剪枝和一些很复杂的效率分析问题,这里不多说了。
    写到这里,《数据结构与算法分析》中的几个大块内容算是说清楚了。由于本文的叙述调整了原书各章节的顺序且至此还没有涉及书里的一些小问题,因此这里想把遗漏下的一些小东西提一下。     有一些树结构可能要求同时满足多个要求。比如一个简单的问题:如果要求构造一个堆使得既能查找最小元素又能查找最大元素怎么办?这时,我们可以用一个特殊的方法来实现:树的单数层满足一种性质,树的双数层满足另一种性质。我们用一个叫做最小-最大堆的东西来实现前面说的问题。这个堆的双数层的数据小于它爸大于它爸的爸,单数层的数据反过来,大于它爸小于它爸的爸。用类似的方法,我们还可以设计一个二叉查找树,使得它能够支持含有2种不同类型元素的数据。在单数层按其中一种操作,在双数层按另一种操作,这样可以方便的查找同时位于两个不同类元素的指定区间内的数据。这种二叉查找树叫做2-d树。扩展2-d 树,我们可以得到k-d树。这些数据结构的具体实现方法这里不说了,书上本来也是作为一个习题介绍的。     书里的第7章花了近50页介绍并分析各种排序算法,分析得很全。其中第11节花了10页介绍外部排序。所谓外部排序,就是说怎样快速地把一个根本无法全部读入内存的大文件进行排序。很多排序之所以可行是因为它们可以随意读写任意一个指定的数。但在大文件里,我们无法实现“第1234567890个元素和第 123个元素交换位置”,更无法实现递归之类的操作,而只能像磁带一样“过一遍”,从头到尾扫一遍,由于文件太大内存不能接受,因此必须要读一截扔一截。于是,外部排序产生了。不要以为这个限制会把排序速度拖得很慢。事实上,外部排序同样突破了O(n^2)的界限。它借助了归并排序中的“合并两个已经有序的数组”的思想,因为这个操作可以边读就边做。把文件先拆成两个文件,再把每个文件处理成一段一段的等长有序序列(一段多大取决于内存能一次处理多大),然后不断从两个文件中各取一段出来合并。可以看到,每段有序序列的长度变长了,变成了2倍长。过不了几次,这个长度将变成文件的总长。注意,我们必须要让每次合并时为下次合并做好准备(就是说合并后的结果仍然要是两个分了段的文件)。一个好的方法是将合并的结果交替存在两个不同的新文件中。     第9章讲图论算法。讲了图的遍历(广搜和深搜)、AOV、AOE、Dijkstra、网络流、Prim、Kruskal和NP问题。在讲深搜时,我学到了两个新东西,用线性时间查找割点(去掉了的话图就不连通了的点)和强分支(有向图中的一个分支满足其中任两个点之间都可以互相到达)。后来发现黑书上也有,又觉得这个东西很不好说,因此这里不想说了。说到了黑书还想顺便补一句:黑书真的看不得——太多错误了。不是说LRJ怎么了,LRJ在真正的大问题上有他的思想和经验,但很多细节的概念他也是昏的,这不利于初学者接受知识。不信哪天我还要写一篇日志纠正黑书的错误。引用政治书上抨击“人性自私论”的经典语言:“从理论到实践都是错的”。     第10章讲“算法设计技巧”,大概是些贪心啊,分治啊,动规啊,回溯啊,随机化啊之类的。调度问题、Huffman树、装箱问题近似算法、最近点距分治算法、最优二叉查找树、Floyd-Warshall、跳跃表、Miller-Rabin素性测试、博弈算法等都在这章中有讲,并且讲得相当好。由于这不是本书的重点内容,这里也不说了。     第11章整章都在讲摊还分析。这是一个相当复杂的问题,是分析时间复杂度的一个有力工具。它的分析告诉我们的不是某一个操作的复杂度,而是重复执行某一个操作的平均复杂度。研究这个是很有必要的,因为我们会遇到一些“越变越慢”的退化情形和“自我保持不变”的自调整性等数据结构,单个操作并不能反映它真正的效率。
    到这里,这本书的所有东西都已经介绍完了。总的来说,这本书很值得一看(虽然有些地方翻译得很差)。它的理论性很强,证明过程完整(再复杂的分析它也证明得很清楚,满足那些刨根问底的人);整本书自成一个体系,前后呼应;习题具有研究性,与课文互相补充。事实上,这些都是国外教材共有的特点。这算是我完整读过的第一本国外教材,今后我还会读一些。这几天在看《组合数学》(仍然是这个出版社出版的),看完后也打算写一下“对《组合数学》一书中部分内容的形象理解”。读一本国外教材,你会发现它与国内书籍的不同并会从中获益更多。
    这篇文章就写到这里了。号称是一个5000字缩写,没想到写着写着已经超过8000字了。而且,这个并不是缩写,而是一些简单的、系统的、清晰的、形象化的思想和理解。这篇文章或许对已经知道一些有关知识的人有用,但不适合一点也没有接触过数据结构与算法分析的人。如果有一个人能从中收获一件东西,我写这个的目的也就达到了。
(完)

数据结构与算法(一)基础

数据结构是一门研究非数值计算程序设计问题中,计算机的操作对象以及他们之间的关系和操作的学科

数据是用来描述现实世界的数字字符图像声音以及能够输入到计算机中并能被计算机识别的符号的集合

数据结构三方面内容:

(1)数据的逻辑结构指数据元素之间固有的逻辑关系

(2)数据的存储结构指数据元素及其关系在计算机内的表示

( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除,更新,查询,排序等

一.数据结构基础概念

逻辑结构包括:

(1)线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继。
(2)非线性结构,一个结点可能有多个直接前趋和后继。:集合,树形结构、图形结构

存储结构包括:

1)顺序存储,逻辑相邻的结点存储在物理上相邻的存储单元内。逻辑顺序与存储顺序一致
2)链接存储,结点间的逻辑关系由附加指针字段表示,1.逻辑顺序与存储顺序不一致2.每个节点存取的费时不同
3)索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引。
4)散列存储,按结点的关键字直接计算出存储地址。

(操作)算法时间复杂度

是该算法的时间耗费,是求解问题规模n的函数。记为O(n)。
时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

评价算法的标准:正确性,高效性,健壮性(容错),可读性。

抽象数据类型的形式描述为:

ADT = ( D,S,P )

  其中:D 是数据对象,

S 是 D 上的关系集,

P 是 D 的基本操作集。

ADT 抽象数据类型名 {

 数据对象: 数据对象的定义

 数据关系: 数据关系的定义

 基本操作: 基本操作的定义

} ADT 抽象数据类型名

二.各类数据结构特点(算法时间复杂度)

    索引 插入 删除 查询 排序
  静态数组 O(1) O(1)  
  动态数组 O(1) O(n) O(n) O(n)  
  单链表 O(n) O(1) O(1) O(n)  
  双链表 O(n) O(1) O(1) O(n)  
  二叉排序树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  红黑树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  B树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  笛卡尔树 O(log(n)) O(log(n)) O(log(n))  
  哈希表 O(1) O(1) O(1)  
             
             
             
排序:

image