一：查找
1.1 基本概念和术语
查找(Search)是在数据结构中确定是否存在关键码等于给定关键码的记录的过程。关键码有主关键码和次关键码。主关键码能够唯一区分各个不同的记录，次关键码通常不能唯一区分各个不同的记录。以主关键码进行的查找是最经常、也是最主要的查找。
查找有静态查找(Static Search)和动态查找(dynamic Search)两种。静态查找是指只在数据结构里查找是否存在关键码等于给定关键码的记录而不改变数据结构，动态查找是指在查找过程中插入数据结构中不存在的记录，或者从数据结构中删除已存在的记录。
衡量查找算法的最主要的标准是平均查找长度（Average Search Length，简称ASL）。平均查找长度是指在查找过程中进行的关键码比较次数的平均值，其 数学定义为：
其中，pi是要查找记录的出现概率，ci是查找相应记录需进行的关键码比较次数。
1.2 静态查找表
由于静态查找不需要在静态查找表中插入或删除记录，所以，静态查找表的数据结构是线性结构，可以是顺序存储的静态查找表或链式存储的静态查找表。下面采用顺序表作为顺序存储的静态查找表，单链表作为链式存储的静态查找表。
1.2.1 顺序查找
顺序查找(Sequnce Search)又称线性查找(Linear Search)，其基本思想是：从静态查找表的一端开始，将给定记录的关键码与表中各记录的关键码逐一比较，若表中存在要查找的记录，则查找成功，并给出该记录在表中的位置；否则，查找失败,，给出失败信息。
顺序查找的基本操作是关键码的比较，因此，查找表的长度就是查找算法的时间复杂度，即为 O(n)。
顺序查找虽然简单，但效率很低，特别是当查找表中的记录很多时更是如此。
1.2.2 有序表的折半查找
折半查找(Binary Search)又叫二分查找，其基本思想是：在有序表中，取中间的记录作为比较对象，如果要查找记录的关键码等于中间记录的关键码 ，则查找成功；若要查找记录的关键码小于中间记录的关键码，则在中间记录的左半区继续查找；若要查找记录的关键码大于中间记录的关键码，则在中间记录的右半
区继续查找。不断重复上述查找过程，直到查找成功，或有序表中没有所要查找 的记录，查找失败。
c#算法实现
/// <summary>
/// 折半查找
/// </summary>
/// <param name="sqList">有序顺序表</param>
/// <param name="key">要查找的值</param>
/// <returns>返回下标，如果找到，返回目标元素的下标，查找失败，返回-1</returns>
public int BinarySearch1(SeqList<int> sqList, int key)
{
int left, right, mid;
left = ;//数组左端
right = sqList.GetLength() - ;//数组右端 while (left <= right)//在左右指针交换之前，查找还没结束
{
mid = (left + right) / ;//更新中间的值 if (sqList[mid] == key)//查找成功
{
return mid;
}
else if (sqList[mid] > key)//若还没有找到，改变左右区间继续寻找
{
right = mid - ;
}
else
{
left = mid + ;
}
} return -;
} /// <summary>
/// 折半查找递归版本
/// </summary>
/// <param name="sqList">有序顺序表</param>
/// <param name="left"></param>
/// <param name="right"></param>
/// <param name="key"></param>
/// <returns></returns>
public int BinarySearch2(SeqList<int> sqList, int left, int right, int key)
{
if (left > right)//查找不到
return -;
int mid = (left + right) / ;
if (sqList[mid] == key)//查找成功
{
return mid;
}
else if (sqList[mid] > key)//若还没有找到，改变左右区间继续寻找
{
return BinarySearch2(sqList, left, mid - , key);
}
else
{
return BinarySearch2(sqList, mid + , right, key);
}
}
性能分析：从折半查找的过程来看，以有序表的中点作为比较对象，并以中点将有序表分为两个子表，对定位到的子表进行递归操作。所以，对有序表中的每个记录的查找过程，可用二叉树来描述，这棵二叉树称为判定树，如下图所示。
从图 8.1 所示的判定树可知，查找有序表中任何一个记录的过程，即是从判定树的根结点到该记录结点路径上的各结点关键码与给定记录关键码的比较过程。所以，比较次数为该记录结点在判定树中的层次数。因此，由二叉树的性质可知，折半查找在查找成功时所进行的关键码比较次数为log2(n+1)次。
下面分析折半查找的平均查找长度。为了便于讨论，以层次为k的满二叉树（n=2k-1）为例。假设顺序表中每个记录的查找概率是相等的，即pi=1/n，则折半查找的平均查找长度为：
所以，折半查找的时间复杂度为O(logn)。折半查找的平均效率较高，但要求是有序表。
注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。
1.2.3 插值查找
在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？
比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。
经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：
基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，插值查找也属于有序查找。是对二分查找的优化
注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
c# 算法实现
/// <summary>
/// 插值查找
/// </summary>
/// <param name="sqList">有序顺序表</param>
/// <param name="left">数组左端</param>
/// <param name="right">数组右端</param>
/// <param name="key">要查找目标值</param>
/// <returns>返回下标，如果找到，返回目标元素的下标，查找失败，返回-1</returns>
public int InsertionSearch(SeqList<int> sqList, int left, int right, int key)
{
if (left > right)//查找不到
return -;
int mid = left + (key - sqList[left]) / (sqList[right] - sqList[left]) * (right - left);
if (sqList[mid] == key)//查找成功
{
return mid;
}
else if (sqList[mid] > key)//若还没有找到，改变左右区间继续寻找
{
return InsertionSearch(sqList, left, mid - , key);
}
else
{
return InsertionSearch(sqList, mid + , right, key);
}
}
复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。
1.2.4 斐波那契查找
在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。
黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。
0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。
大家记不记得斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。
基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;
开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种
1）相等，mid位置的元素即为所求
2）>，low=mid+1,k-=2;
说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。
3）<，high=mid-1,k-=1。
说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。
复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。
c# 算法实现
/// <summary>
/// 创建斐波那契数列
/// </summary>
/// <returns></returns>
public int[] fibonacci()
{
int[] f = new int[];
int i = ;
f[] = ;
f[] = ;
for (i = ; i < ; i++)
{
f[i] = f[i - ] + f[i - ];
}
return f;
} /// <summary>
/// 斐波那契查找
/// </summary>
/// <param name="sqList"></param>
/// <param name="key"></param>
/// <returns></returns>
public int fibonacciSearch(SeqList<int> sqList, int key)
{
int low = ;
int high = sqList.GetLength() - ;
int mid = ; // 斐波那契分割数值下标
int k = ; // 序列元素个数
int i = ; // 获取斐波那契数列
int[] f = fibonacci(); // 获取斐波那契分割数值下标
while (sqList.GetLength() > f[k] - )
{
k++;
} // 创建临时数组
int[] temp = new int[f[k] - ];
for (int j = ; j < sqList.GetLength(); j++)
{
temp[j] = sqList[j];
} // 序列补充至f[k]个元素
// 补充的元素值为最后一个元素的值
for (i = sqList.GetLength(); i < f[k] - ; i++)
{
temp[i] = temp[high];
} while (low <= high)
{
// low：起始位置
// 前半部分有f[k-1]个元素，由于下标从0开始
// 则-1 获取 黄金分割位置元素的下标
mid = low + f[k - ] - ; if (temp[mid] > key)
{
// 查找前半部分，高位指针移动
high = mid - ;
// （全部元素） = （前半部分）+（后半部分）
// f[k] = f[k-1] + f[k-1]
// 因为前半部分有f[k-1]个元素，所以 k = k-1
k = k - ;
}
else if (temp[mid] < key)
{
// 查找后半部分，高位指针移动
low = mid + ;
// （全部元素） = （前半部分）+（后半部分）
// f[k] = f[k-1] + f[k-1]
// 因为后半部分有f[k-1]个元素，所以 k = k-2
k = k - ;
}
else
{
// 如果为真则找到相应的位置
if (mid <= high)
{
return mid;
}
else
{
// 出现这种情况是查找到补充的元素
// 而补充的元素与high位置的元素一样
return high;
}
}
}
return -;
}
其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。
1.3 动态查找表
静态查找表一旦生成后，所含记录在查找过程中一般固定不变，而动态查找表则不然。动态查找表在查找过程中动态生成，即若表中存在关键码为 key 的记 录， 则查找成功返回，否则则插入关键码为key的记录。在动态查找表中，经常需要对表中的记录进行插入和删除的操作，所以动态查找表采用灵活的存储方法来组织查找表中的记录，以便高效率地实现查找、插入和删除等操作。
1.3.1 最简单的树表查找算法——二叉树查找算法
具体内容见【C#数据结构系列】树和二叉树—二叉树的应用
1.3.2 平衡查找树之2-3查找树（2-3 Tree）
二叉查找树(Binary Search Tree)对于大多数情况下的查找和插入在效率上来说是没有问题的，但是他在最差的情况下效率比较低。下面介绍的平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率，要实现这一目标我们需要保证树在插入完成之后始终保持平衡状态，这就是平衡查找树(Balanced Search Tree)。在一棵具有N 个节点的树中，我们希望该树的高度能够维持在lgN左右，这样我们就能保证只需要lgN次比较操作就可以查找到想要的值。不幸的是，每次插入元素之后维持树的平衡状态太昂贵。所以这里会介绍一些新的数据结构来保证在最坏的情况下插入和查找效率都能保证在对数的时间复杂度内完成。首先介绍2-3查找树(2-3 Search Tree)，后面会在此基础上介绍红黑树和B树。
1：定义
和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：
1. 要么为空，要么：
2. 对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key有效，有节点也是一个2-3节点，所有的值比key要大。
3. 对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个根节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。
如果中序遍历2-3查找树，就可以得到排好序的序列。在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。
2：查找
在进行2-3树的平衡之前，我们先假设已经处于平衡状态，我们先看基本的查找操作。
2-3树的查找和二叉查找树类似，要确定一个树是否属于2-3树，我们首先和其跟节点进行比较，如果相等，则查找成功；否则根据比较的条件，在其左中右子树中递归查找，如果找到的节点为空，则未找到，否则返回。查找过程如下图：
3：插入
往一个2-node节点插入
往2-3树中插入元素和往二叉查找树中插入元素一样，首先要进行查找，然后将节点挂到未找到的节点上。2-3树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。如果查找后未找到的节点是一个2-node节点，那么很容易，我们只需要将新的元素放到这个2-node节点里面使其变成一个3-node节点即可。但是如果查找的节点结束于一个3-node节点，那么可能有点麻烦
往一个3-node节点插入
往一个3-node节点插入一个新的节点可能会遇到很多种不同的情况，下面首先从一个最简单的只包含一个3-node节点的树开始讨论。
只包含一个3-node节点
如上图，假设2-3树只包含一个3-node节点，这个节点有两个key，没有空间来插入第三个key了，最自然的方式是我们假设这个节点能存放三个元素，暂时使其变成一个4-node节点，同时他包含四个子节点。然后，我们将这个4-node节点的中间元素提升，左边的节点作为其左节点，右边的元素作为其右节点。插入完成，变为平衡2-3查找树，树的高度从0变为1。
节点是3-node，父节点是2-node
和第一种情况一样，我们也可以将新的元素插入到3-node节点中，使其成为一个临时的4-node节点，然后，将该节点中的中间元素提升到父节点即2-node节点中，使其父节点成为一个3-node节点，然后将左右节点分别挂在这个3-node节点的恰当位置。操作如下图：
节点是3-node，父节点也是3-node
当我们插入的节点是3-node的时候，我们将该节点拆分，中间元素提升至父节点，但是此时父节点是一个3-node节点，插入之后，父节点变成了4-node节点，然后继续将中间元素提升至其父节点，直至遇到一个父节点是2-node节点，然后将其变为3-node，不需要继续进行拆分。
4：实现
直接实现2-3树比较复杂，因为：
- 需要处理不同的节点类型，非常繁琐
- 需要多次比较操作来将节点下移
- 需要上移来拆分4-node节点
- 拆分4-node节点的情况有很多种
2-3查找树实现起来比较复杂，在某些情况插入后的平衡操作可能会使得效率降低。在2-3查找树基础上改进的红黑树不仅具有较高的效率，并且实现起来较2-3查找树简单。但是2-3查找树作为一种比较重要的概念和思路对于理解红黑树和B树非常重要。
5：总结：
这些本地操作保持了2-3树的平衡。对于4-node节点变形为2-3节点，变形前后树的高度没有发生变化。只有当跟节点是4-node节点，变形后树的高度才加一。如下图所示：
完全平衡的2-3查找树如下图，每个根节点到叶子节点的距离是相同的：
2-3树的查找效率与树的高度是息息相关的。
- 在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN
- 在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN
距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。
对于插入来说，只需要常数次操作即可完成，因为他只需要修改与该节点关联的节点即可，不需要检查其他节点，所以效率和查找类似。下面是2-3查找树的效率：
1.3.3 平衡查找树之红黑树
上面介绍了2-3查找树，可以看到，2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgN，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，下面介绍一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）
定义
红黑树的主要是想对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。
根据以上描述，红黑树定义如下：
红黑树是一种具有红色和黑色链接的平衡查找树，同时满足：
- 红色节点向左倾斜
- 一个节点不可能有两个红色链接
- 整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同。
下图可以看到红黑树其实是2-3树的另外一种表现形式：如果我们将红色的连线水平绘制，那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。
表示
我们可以在二叉查找树的每一个节点上增加一个新的表示颜色的标记。该标记指示该节点指向其父节点的颜色。
C# 实现
/// <summary>
/// 红黑树节点类
/// </summary>
/// <typeparam name="T"></typeparam>
public class RedBlackTreeNode<T>
{
public T Data { get; set; }
public RedBlackTreeNode<T> LChild { get; set; }
public RedBlackTreeNode<T> RChild { get; set; }
public bool Color {get;set;} public RedBlackTreeNode(T data, RedBlackTreeNode<T> lp, RedBlackTreeNode<T> rp, bool color)
{
Data = data;
LChild = lp;
RChild = rp;
Color = color;
} public RedBlackTreeNode(RedBlackTreeNode<T> lp, RedBlackTreeNode<T> rp, bool color)
{
Data = default(T);
LChild = lp;
RChild = rp;
Color = color;
} public RedBlackTreeNode(T data, bool color)
{
Data = data;
LChild = null;
RChild = null;
Color = color;
} public RedBlackTreeNode()
{
Data = default(T);
LChild = null;
RChild = null;
Color = false; ;
}
}
查找
红黑树是一种特殊的二叉查找树，他的查找方法也和二叉查找树一样，不需要做太多更改。
但是由于红黑树比一般的二叉查找树具有更好的平衡，所以查找起来更快。
c# 实现
/// <summary>
/// 红黑树查找
/// </summary>
/// <param name="bt">红黑树</param>
/// <param name="key">目标值</param>
/// <returns>0：查找成功，1：查找失败</returns>
public int Search(RedBlackTree<int> rbt, int key)
{
RedBlackTreeNode<int> p;
//红黑树为空
if (rbt == null)
{
Console.WriteLine("The RedBlackTree is empty!");
return ;
}
p = rbt.Head;
//红黑树非空
while (p != null)
{
//存在要查找的记录
if (p.Data == key)
{
Console.WriteLine("Search is Successful!");
return ;
}
//待查找记录的关键码大于结点的关键码
else if (p.Data < key)
{
p = p.RChild;
}
//待查找记录的关键码小于结点的关键码
else
{
p = p.LChild;
}
} return ;
}
平衡化
在介绍插入之前，我们先介绍如何让红黑树保持平衡，因为一般的，我们插入完成之后，需要对树进行平衡化操作以使其满足平衡化。
旋转
旋转又分为左旋和右旋。通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接。对比操作前后，可以看出，该操作实际上是将红线链接的两个节点中的一个较大的节点移动到根节点上。
左旋操作如下图：
/// <summary>
/// 左旋转
/// </summary>
/// <param name="h"></param>
/// <returns></returns>
public RedBlackTreeNode<T> RotateLeft(RedBlackTreeNode<T> h)
{
RedBlackTreeNode<T> x = h.RChild;
//将x的左节点复制给h右节点
h.RChild = x.LChild;
//将h复制给x右节点
x.LChild = h;
x.Color = h.Color;
h.Color = RED;
return x;
}
左旋的动画效果如下：
、
右旋是左旋的逆操作，过程如下：
代码如下：
/// <summary>
/// 右旋转
/// </summary>
/// <param name="h"></param>
/// <returns></returns>
public RedBlackTreeNode<T> RotateRight(RedBlackTreeNode<T> h)
{
RedBlackTreeNode<T> x = h.LChild;
//将x的右节点复制给h左节点
h.LChild = x.RChild;
//将h复制给x右节点
x.RChild = h; x.Color = h.Color;
h.Color = RED;
return x;
}
右旋的动画效果如下：
颜色反转
当出现一个临时的4-node的时候，即一个节点的两个子节点均为红色，如下图：
这其实是个A，E，S 4-node连接，我们需要将E提升至父节点，操作方法很简单，就是把E对子节点的连线设置为黑色，自己的颜色设置为红色。
有了以上基本操作方法之后，我们现在对应之前对2-3树的平衡操作来对红黑树进行平衡操作，这两者是可以一一对应的，如下图：
现在来讨论各种情况：
Case 1 往一个2-node节点底部插入新的节点
先热身一下，首先我们看对于只有一个节点的红黑树，插入一个新的节点的操作：
这种情况很简单，只需要：
- 标准的二叉查找树遍历即可。新插入的节点标记为红色
- 如果新插入的节点在父节点的右子节点，则需要进行左旋操作
Case 2往一个3-node节点底部插入新的节点
先热身一下，假设我们往一个只有两个节点的树中插入元素，如下图，根据待插入元素与已有元素的大小，又可以分为如下三种情况：
- 如果带插入的节点比现有的两个节点都大，这种情况最简单。我们只需要将新插入的节点连接到右边子树上即可，然后将中间的元素提升至根节点。这样根节点的左右子树都是红色的节点了，我们只需要调研FlipColor方法即可。其他情况经过反转操作后都会和这一样。
- 如果插入的节点比最小的元素要小，那么将新节点添加到最左侧，这样就有两个连接红色的节点了，这是对中间节点进行右旋操作，使中间结点成为根节点。这是就转换到了第一种情况，这时候只需要再进行一次FlipColor操作即可。
- 如果插入的节点的值位于两个节点之间，那么将新节点插入到左侧节点的右子节点。因为该节点的右子节点是红色的，所以需要进行左旋操作。操作完之后就变成第二种情况了，再进行一次右旋，然后再调用FlipColor操作即可完成平衡操作。
有了以上基础，我们现在来总结一下往一个3-node节点底部插入新的节点的操作步骤，下面是一个典型的操作过程图：
可以看出，操作步骤如下：
- 执行标准的二叉查找树插入操作，新插入的节点元素用红色标识。
- 如果需要对4-node节点进行旋转操作
- 如果需要，调用FlipColor方法将红色节点提升
- 如果需要，左旋操作使红色节点左倾。
- 在有些情况下，需要递归调用Case1 Case2，来进行递归操作。如下：
代码实现
经过上面的平衡化讨论，现在就来实现插入操作，一般地插入操作就是先执行标准的二叉查找树插入，然后再进行平衡化。对照2-3树，我们可以通过前面讨论的，左旋，右旋，FlipColor这三种操作来完成平衡化。
具体操作方式如下：
- 如果节点的右子节点为红色，且左子节点位黑色，则进行左旋操作
- 如果节点的左子节点为红色，并且左子节点的左子节点也为红色，则进行右旋操作
- 如果节点的左右子节点均为红色，则执行FlipColor操作，提升中间结点。
根据这一逻辑，我们就可以实现插入的Put方法了。