建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

本章内容颇多，所以我分三篇来写，这一篇是关于一些基本的概念和选择，后面两篇分别是插入和删除。

上一章总结过BST(http://www.wutianqi.com/?p=2430)，BST在高度较小时，可以获得很好的性能(因为BST的操作的平均时间为O(lgn))，但是在高度较大时，则性能就一般。而红黑树“近似平衡”，于是降低了平均时间，再者，红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。

谈到红黑树的用途，最广为人知的应该就是红黑树在C++ STL中的应用了，在set, multiset, map, multimap等中，都应用了红黑树(具体大家可以去网上搜搜)。

 

下面给出红黑树和黑高度的定义：

满足下面几个条件(红黑性质)的二叉搜索树，称为红黑树：
1. 每个结点或是红色，或是是黑色。
2. 根结点是黑的。
3. 所有的叶结点(NULL)是黑色的。（NULL被视为一个哨兵结点，所有应该指向NULL的指针，都看成指向了NULL结点。）
4. 如果一个结点是红色的，则它的两个儿子节点都是黑色的。
5. 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

黑高度的定义：
从某个结点出发(不包括该结点)到达一个叶结点的任意一条路径上，黑色结点的个数成为该结点x的黑高度。

下面就是一个红黑树：

红黑树是二叉搜索树的一种。它与普通二叉搜索树不同的是，红黑树的每个节点都附加了另一个属性――颜色，可以是红色，也可以是黑色。通过对于每条路径上节点颜色的规则进行限定，红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过2倍。所以，红黑树是一种近似平衡的二叉搜索树。

红黑树的查找、最大值、最小值、前趋、后继等操作，与普通的二叉搜索树没有什么区别。插入和删除操作需要重新实现。仅仅用普通的二叉搜索树的插入和删除动作，可能会破坏红黑树本身的一些性质，因此，需要进行额外的处理。这些额外的处理主要是改变树节点的颜色，或是改变树的结构。

关于旋转：

我把13-2手动画了一次并添加了一些注释：

 

旋转其实比较简单，就不多说了，以下是代码：

 

下一篇是关于插入。

 

在我独立博客上的原文：http://www.wutianqi.com/?p=2438

欢迎大家互相学习，互相讨论！

     摘要: 建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html 推荐在看算法导论的这一章之前先看看严蔚敏老师在《数据结构》上的二叉查找树。 整体来说二叉查找树不难，就是插入和删除节点时让人纠结，我就是在删除节点时各种纠结了。 二叉树执行基本操作的时间与树的高度成正比。 首先说下二叉查找树的性质： 设x为二叉查...  阅读全文

建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

 

第10章没法说，数据结构还是看严奶奶的比较好，所以《算法导论》上的这一章我随便瞄了几眼就过去了，不过话说回来，数据结构非常重要！！！所以，大家最好把严蔚敏的《数据结构》认认真真的看N遍！！！

另外，推荐看看这个：

数据结构的源码实现：http://www.cppleyuan.com/viewthread.php?tid=418

 

第11章散列表也属于数据结构方面的知识，第10章只是讲了最基本的几个结构。这一章也很简单，其实就是介绍了一些概念及思想，很容易理解。(你可以把散列表想象成平时用的英语字典，26个英文字母就是下标，通过它来定位你要查的单词。)

所以这一章我就不重复去打出概念了，我把几个散列函数和处理碰撞的方法放在图表里方便对比。

 

①.散列表的优点：出色的期望性能。

②.引出：

直接寻址表(P132)的缺点：

1.全域U也许会很大。

2.实际关键字域K也许相对于U会很小。

由此引出了散列表。

以下是我总结对比的表：

 

这一章我也不知道该怎么说，表面上感觉比较简单，但是如果深入研究，会发现它的内容太多了，而且很好很强大。所以还是建议大家看看书也许以后深入了解了我会再补充。

这几天主要在研究红黑树在，那个晕啊，不过总算弄明白了，心情也跟着很爽，接下来的一些章节都比较麻烦了，大家一起加油！

在我独立博客上的原文：http://www.wutianqi.com/?p=2419

欢迎大家互相学习，互相讨论！

建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

这一章的内容很简单，基本都是一些概念。

第i个顺序统计量:在一个由n个元素组成的集合中，第i个顺序统计量(order statistic)是该集合中第i小的元素。

最小值是第1个顺序统计量(i=1)

最大值是第n个顺序统计量(i=n)

中位数：一个中位数(median)是它所在集合的“中点元素”，当n为奇数时，i=(n+1)/2，当n为偶数是，中位数总是出现在 （下中位数）和 （上中位数）。

找最大值/最小值问题，通过比较n-1次可以得出结果。

MINIMUM(A)
1  min ← A[1]
2  for i ← 2 to length[A]
3         do if min > A[i]
4                then min ← A[i]
5  return min

如果要同时找出最大值和最小值，则比较次数最少并不是2*n-2，而是 ，我们可以将一对元素比较，然后把较大者于max比较，较小者与min比较，这样就只需要 。

如果是一般的选择问题，即找出一段序列第i小的数，看起来要比找最大值或最小值要麻烦，其实两种问题的渐进时间都是 。

首先看看这个强悍的伪代码：

RANDOMIZED-SELECT(A, p, r, i)
1  if p = r
2      then return A[p]
3  q ← RANDOMIZED-PARTITION(A, p, r)
4  k ← q - p + 1
5  if i = k          ▹ the pivot value is the answer
6      then return A[q]
7  elseif i < k
8      then return RANDOMIZED-SELECT(A, p, q - 1, i)
9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

这个算法利用了随机化的Partition算法，这个实在第七章的随机化快排中讲到：http://www.wutianqi.com/?p=2368，不记得的可以先复习下前面的快排。

这个随机化的选择算法返回数组A[p..r]中第i小的元素。

具体实现如下：

结果如图：

在(89, 100, 21, 5, 2, 8, 33, 27, 63)中查找第二小的数字是5. 

该算法的平均情况性能较好，并且又是随机化的，所有没有哪一种特别的输入会导致最坏情况发生。

在我独立博客上的原文：http://www.wutianqi.com/?p=2395
欢迎大家互相学习，互相探讨。      摘要: 建议先看看前言 ： http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html 这一节讲的是非线性排序。 一.计数排序(Counting Sort) 基本思想：对每一个输入元素x，确定出小于x的元素个数。 适用范围：适用于输入是由小范围的整数构成的序列。 稳定性：算法是稳定的。 具体实现：  1 ...  阅读全文

建议先看看前言 ： http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

 

第八章将介绍几种非比较排序—计数排序，基数排序，桶排序，这三种排序都在线性时间下运行的。

这一节决策树其实是对前面的堆排序，快排等是最优的比较算法的证明，

首先说下《算法导论》上对决策树的定义：一棵决策树是一棵满二叉树(注意看下面解释)，表示某排序算法作用于给定输入所做的所有比较，而控制结构，移动等都被忽略了。

注意：这里个人认为定义是错误的，决策树不是一棵满二叉树，连完全二叉树都不是。(不知道有没有朋友看到这里和我想法一样？)

首先看看只有三个元素时，决策树的图：

在决策树中，每个内结点都用i:j表示比较下标为i数组元素与下标为j的数组元素的大小。每一个叶结点是一个n个元素的全排列。

所以排序算法的执行对应于遍历一条从树的根到叶结点的路径！

因为有n个结点，根据高中学的组合排列知识，知道有n!个情况，也就是n!个叶子结点。

在决策树中，从根到任意一个可达叶结点之间的最长路径的长度，表示对应的排序算法中最坏情况下的比较次数。这样，一个比较算法的最坏情况的比较次数就是其决策树的高度。

定理8.1证明了任意一个比较算法在最坏情况下都需要做Ω(n lg n)次的比较。这个证明比较简单，可以看看书上的证明过程。

这一节其实没什么内容，就是一点基本的概念，以及了解比较算法可以通过转换为决策树这个模型去理解。

 

推荐先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

其实这一篇我老早就写过了，只不过最近在总结《算法导论》，而第七章就是快速排序，我当初总结的快排也是根据算法导论来的，为了方便大家阅读，我在这里把曾经写过的重新再贴一遍。

---

前几天写过一个堆排序的文章(http://www.wutianqi.com/?p=1820)，里面谢了很多讲解和代码注释，个人感觉快速排序不是很难，所以不想写讲解，也不需要写注释，大家如果不明白什么是快速排序，可以去看下文章最后我推荐的几个链接。

 

我查过网上很多关于快排的文章和代码，但是基本都是最原始的快排，即霍尔(Hoare)快排。想必大家也没有注意这些，我准备把霍尔快排，算法导论上的快排和随机化快排的代码一起发出来，供大家对比与学习，欢迎大家和我探讨

代码一.霍尔快排：

/*
 * Author: Tanky Woo
 * Blog:   www.WuTianQi.com
 * Note:   快速排序版本1 --- Hoare-Partition
 */
 
#include <iostream>
using namespace std;
 
int num;
 
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
void PrintArray(int *arr)
{
    for(int i=1; i<=num; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
 
int Partition1(int *arr, int beg, int end)
{
    int low = beg, high = end;
    int sentinel = arr[beg];
    while(low < high)
    {
        while(low<high && arr[high]>=sentinel)
            --high;
        arr[low] = arr[high];
        while(low<high && arr[low]<=sentinel)
            ++low;
        arr[high] = arr[low];
    }
    arr[low] = sentinel;
 
    cout << "排序过程:";
    PrintArray(arr);
    return low;
}
 
void QuickSort(int *arr, int beg, int end)
{
    if(beg < end)
    {
        int pivot = Partition1(arr, beg, end);
        QuickSort(arr, beg, pivot-1);
        QuickSort(arr, pivot+1, end);
    }
}
 
int main()
{
    int arr[100];
    cout << "Input the num of the elements:\n";
    cin >> num;
    cout << "Input the elements:\n";
    for(int i=1; i<=num; ++i)
        cin >> arr[i];
    QuickSort(arr, 1, num);
    cout << "最后结果:";
    PrintArray(arr);
    return 0;
}

代码二.《算法导论》里讲的快排：

/*
 * Author: Tanky Woo
 * Blog:   www.WuTianQi.com
 * Note:   快速排序版本2---《算法导论》
 */
 
#include <iostream>
using namespace std;
 
int num;
 
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
void PrintArray(int *arr)
{
    for(int i=1; i<=num; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
 
int Partition2(int *arr, int beg, int end)
{
    int sentinel = arr[end];
    int i = beg-1;
    for(int j=beg; j<=end-1; ++j)
    {
        if(arr[j] <= sentinel)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[end]);
 
    cout << "排序过程:";
    PrintArray(arr);
    return i+1;
}
 
void QuickSort(int *arr, int beg, int end)
{
    if(beg < end)
    {
        int pivot = Partition2(arr, beg, end);
        QuickSort(arr, beg, pivot-1);
        QuickSort(arr, pivot+1, end);
    }
}
 
int main()
{
    int arr[100];
    cout << "Input the num of the elements:\n";
    cin >> num;
    cout << "Input the elements:\n";
    for(int i=1; i<=num; ++i)
        cin >> arr[i];
    QuickSort(arr, 1, num);
    cout << "最后结果:";
    PrintArray(arr);
    return 0;
}

代码三.随机快排：

/*
 * Author: Tanky Woo
 * Blog:   www.WuTianQi.com
 * Note:   快速排序版本3 --- 随机化版本
 * 解决待排序元素相差很大的情况
 */
 
 
#include <iostream>
#include <cstdlib>
using namespace std;
 
int num;
 
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
void PrintArray(int *arr)
{
    for(int i=1; i<=num; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
 
int Partition3(int *arr, int beg, int end)
{
    int sentinel = arr[end];
    int i = beg-1;
    for(int j=beg; j<=end-1; ++j)
    {
        if(arr[j] <= sentinel)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[end]);
 
    cout << "排序过程:";
    PrintArray(arr);
    return i+1;
}
 
int RandomPartition(int *arr, int beg, int end)
{
    int i = beg + rand() % (end-beg+1);
    swap(arr[i], arr[end]);
    return Partition3(arr, beg, end);
}
 
 
void RandomQuickSort(int *arr, int beg, int end)
{
    if(beg < end)
    {
        int pivot = RandomPartition(arr, beg, end);
        RandomQuickSort(arr, beg, pivot-1);
        RandomQuickSort(arr, pivot+1, end);
    }
}
 
int main()
{
    int arr[100];
    cout << "Input the num of the elements:\n";
    cin >> num;
    cout << "Input the elements:\n";
    for(int i=1; i<=num; ++i)
        cin >> arr[i];
    RandomQuickSort(arr, 1, num);
    cout << "最后结果:";
    PrintArray(arr);
    return 0;
}

最后，我想说下，随机化的快排一般适用于待排序的数据之间相差较大的情况下。

这里给出几篇网上讲得不错的文章：

1.http://bbs.chinaunix.net/viewthread.php?tid=1011316

算是一个讨论帖。很给力！

2.http://www.javaeye.com/topic/561718

讲得比较详细，不过代码是Java的。

3.http://tayoto.blog.hexun.com/25048556_d.html

4.http://www.360doc.com/content/10/1106/11/1317564_67067368.shtml

概念上很详细。

5.http://blog.csdn.net/wssxy/archive/2008/12/05/3448642.aspx

一篇讲快排的佳作！

6.http://www.cnblogs.com/chinazhangjie/archive/2010/12/09/1901491.html

小杰的文章，用C++模板类写的。大家可以去学习学习。

在我独立博客上的原文：http://www.wutianqi.com/?p=2368
欢迎大家互相学习，互相探讨。

建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

上一章总结是的堆排序算法，这一章同样是利用了堆这种数据结构，实现在是优先级队列。

根据堆分为最大堆，最小堆，所以优先级队列也可以分为最大优先级队列和最小优先级队列。

优先级队列的概念和用途书上已经写的很清楚了，我就不再打一遍了。直接写出具体实现。

在实现前先说几点：

1.上一章说过，堆的length和heapsize要区分清楚，这一章的优先级队列里就用到了。

2.优先级队列用到了上一章的一些函数比如MaxHeapify()，不记得的可以复习下上一章。

以下是代码及讲解(此处实现的是最大优先级队列)：

以下是运行结果：

看上图的结果：

在第二次使用HeapExtractMax后，把第二个数字即6设为15，更新后，结果就是HeapIncreaseKey的输出。

建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

首先介绍几个概念：

卫星数据：一个带排序的的数通常是有一个称为记录的数据集组成的，每一个记录有一个关键字key，记录的其他数据称为卫星数据。

原地排序：在排序输入数组时，只有常数个元素被存放到数组以外的空间中去。

 

在第二章介绍了两种排序：插入排序和合并排序，接下来两章要介绍的是推排序和快速排序，这四个排序都属于比较排序(comparison sort)。

 

我以前总结过堆排序，并具体实现了堆排序，代码中给出了详细的注释，所以在这里就不重复发了，大家可以去看看，个人觉得总结的还是比较给力的：

http://www.wutianqi.com/?p=1820

这里再补充几点：

1.区别length[A]和heap-sort[A]。(P73)(这个在下一篇的优先级队列中将会具体区别)

2.总体上看堆排序由三个函数组成：①.MAX-HEAPIFY ②.BUILD-MAX-HEAP ③.HEAP-SORT

 

另外，在这里给大家补充一点个人经验，有时理论难以理解，代码难以理解，这个时候，就要靠秘诀了：拿起手中的笔和纸，自己给出一组输入，按照书上的代码，自己去模拟这组输入的执行过程。(这个过程人人都知道，但并不是人人都去做了！学算法，就要自己去模拟，去画图，去推！怎么样容易理解就怎么去做！)

所以这也是我喜欢《算法导论》的原因，接下来，就要强烈推荐大家看《算法导论》上非常非常给力的堆排序实现图了—图6-4。

 

 

总结：本章最基础也是最重要的就是理解堆这种结构！

堆是什么？来看看《算法导论》上的图6-1：

图(a)是一个最大堆，图(b)是最大堆的数组表示。可以看到堆的数组并不是已排序好的。

让我们来回忆下最大堆的定义(P74)：

在最大堆中，最大堆特性是指除了根以外的每个结点i，有A[PARENT(i)] >= A[i]。这样，堆的最大元素就存放在根结点中。

对，堆排序就是利用的这个特性—“堆的最大元素就存放在根结点中”

每次堆化，这样就找到了当前堆的最大元素。

所以说，理解了其本质特征，堆排序其实很简单的。

至于堆排序的具体应用，在后面的最短路算法—Dijkstra中，会用到由堆来优化普通的Dijkstra算法。

下一篇将实现最大优先级队列。

建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/10/143850.html#143880

因为《算法导论》第一部分1~5章的理论性太强，研究过多容易纠结，所以索性合起来快点讲过去。

第四章：

这一章讲的是递归式(recurrence)，递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值来定义的。

本章讲了三种方法来解递归式，分别是代换法，递归树方法，主方法。

1.代换法(Substitution method)(P38~P40)

定义：即在归纳假设时，用所猜测的值去代替函数的解。

用途：确定一个递归式的上界或下界。

缺点：只能用于解的形式很容易猜的情形。

总结：这种方法需要经验的积累，可以通过转换为先前见过的类似递归式来求解。

2.递归树方法(Recursion-tree method)

起因：代换法有时很难得到一个正确的好的猜测值。

用途：画出一个递归树是一种得到好猜测的直接方法。

分析(重点)：在递归树中，每一个结点都代表递归函数调用集合中一个子问题的代价。将递归树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。

总结：递归树最适合用来产生好的猜测，然后用代换法加以验证。

递归树扩展过程：①.第二章2.3.2节分析分治法时图2-5(P21~P22)的构造递归树过程；②.第四章P41图4-1的递归树构造过程；这两个图需要好好分析。

3.主方法(Master method)

优点：针对形如T(n) = aT(n/b) + f(n)的递归式

缺点：并不能解所有形如上式的递归式的解。

具体分析：

T(n) = aT(n/b) + f(n)描述了将规模为n的问题划分为a个子问题的算法的运行时间，每个子问题的规模为n/b。

在这里可以看到，分治法就相当于a=2, b=2, f(n) = O(n).

主方法依赖于主定理：(图片点击放大)

图片可以不清晰，可以看书。

主定理的三种情况，经过分析，可以发现都是把f(n)与 比较。

第一种情况是 更大，第二种情况是 与f(n)相等，第三种情况是f(n)更大。

但是，这三种情况并未完全覆盖所有可能的f(n)：

第一种情况是f(n)多项式的小于 ，而第三种情况是f(n)多项式的大于 ，即两者相差的是 。如果两者相差的不是 ，则无法用主定理来确定界。

比如算法导论P44最下面的 就不能用主定理来判断。

至于主定理的证明，有兴趣的可以拿笔在纸上推算，反正我这里是没看的，毕竟时间有限，要选择性的学习。

第五章：

本章是围绕一个雇佣问题展开的。

问题：有一批参与面试的人，你要一个个面试(面试每个人都要花费c1)，如果当前面试者比自己的助理能力强，则辞掉当前助理的，并把当前面试者提拔为助理(雇佣一个人要花费c2)，一直面试完所有人。

这里考虑的是面试所花的money，假设总共有N人参加面试，有M人被雇佣过，则花费O(N*c1 + M*c2)，因为参与面试的人员顺序是不确定的，所以要花费的money也是不确定的(N*c1是确定的，而M是不确定的，所以M*c2也是不确定的）。

首先介绍两个概念：

1.概率分析：指在问题的分析中应用概率的技术。

2.随机算法：如果一个算法的行为不只是由输入决定，同时也由随机数生成器所产生的数值决定，则成这个算法是随机的。

书上讲的理论性有点强，我这里用自己的话来说下：

首先说下概率分析，因为前面讲到过：雇佣所需的花费与输入序列有关，有N个面试人员(考虑每个人的能力不一样)，则一共有N!中排列情况(即每种排列出现的概率是1/(N!))，于是假设每种排列花费Ti元，则所有供花费：

T1/(N!) + T2/(N!) + … + TN/(N!)。

其实这里可以结合高中学的正态分布来理解，都是讲的每种情况出现的概率，思想差不多，所以这里也不需要什么概率论的知识，都是一些常识。

顺便补充一下：5.2节的指示器随机变量就是用的高中学的期望，用期望来表示概率。

再说下随机算法，对于上面概率分析时的方法，虽然面试人员的排列是不确定的。但是如果当排列确定后，则所需花费也就确定了。而对于随机算法，就算排列确定，其花费也是不确定的。即随机发生在算法上，而不是发生在输入分布上。这就是概率分析与随机算法之间的区别。

比如按书上的，可以给每个人员随机生成一个优先级，或者把每一个面试人员与其后的面试人员中随机一员交换，来产生一个随机的序列。

我以前总结过一些随机算法，有兴趣的朋友可以去看看：

1.《随机化算法(1) — 随机数》

2.《随机化算法(2) — 数值概率算法》

3.《随机化算法(3) — 舍伍德(Sherwood)算法》

4.《随机化算法(4) — 拉斯维加斯(Las Vegas)算法》

5.《随机化算法(5) — 蒙特卡罗(Monte Carlo)算法》

另外，比如像C/C++中库函数rand()就是一个产生随机变量的函数，但是它并不是真正意义上的随机函数，所以称之为伪随机函数。因为当srand(seed)设置的seed一样时，则rand()产生的随机数也一样，所以通常可以通过rand(-1)来把当前时间作为种子模拟随机函数。

补充：在第五章的5.4节给出了几个题目及其分析，这几个题目都很有趣，不过对于数学也相对有一定的要求。其实可以很简化的想：概率和期望是互相转化的，这几题就可以考虑是去求期望的。

我昨天在论坛出了一个逻辑面试题：一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯 从一楼到十楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到最大的一颗？

想必好多人都看过这题，网上的解答多种多项，我觉得此题应该考察的是最优解问题，按照最优解的思路，此题没有100%的解决方法，只能尽量使其期望更高，也就是概率更大。这一题可以说是数学和哲学的完美结合，有点像人生，总想得到更多，但又怕后面的都不行，各种纠结啊。。。

总的来说，第五章说来说去都是一个期望的问题。