一、顺序查找
顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。
URL:http://www.cnblogs.com/tangge/p/5351291.html#SX
二、二分查找
折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储，其时间复杂度为O(logn)。
URL:http://www.cnblogs.com/tangge/p/5351291.html#EX
2.1.Array.BinarySearch方法
在调用这个方法前，需要确保作为参数的查找表内的关键字已经有序，否则就需要手动调用Array.Sort()方法进行排序。
2.2.System.Collections.SortedList类
SortedList类的Add方法，从中可以发现，它借助了Array.BinarySearch方法获取存储位置，也就是说它也使用了二分查找方法。
三、查找树方法
3.1.二叉查找树
（1）基本概念
二叉查找树（Binary Search Tree,BST）又称二叉排序树，它是满足如下性质的二叉树：
- 若它的左子树非空，则左子树上所有记录的值均小于根记录的值；
- 若它的右子树非空，则右子树上所有记录的值均大于根记录的值；
- 左、右子树又各是一棵二叉查找树。
假如有一个序列{62,88,58,47,35,73,51,99,37,93}，那么构造出来的二叉查找树如下图所示：
二叉查找树是递归定义的，其一般理解是：二叉查找树中任一节点，其值为k，只要该节点有左孩子，则左孩子的值必小于k，只要有右孩子，则右孩子的值必大于k。二叉查找树的一个重要的性质是：中序遍历该树得到的序列是一个递增有序的序列。
URL:http://www.cnblogs.com/tangge/p/5549844.html
（2）二叉查找树的新增操作
（3）二叉查找树的删除操作
step1”叶子节点：直接删除该节点，再修改其父节点的指针（注意分是根节点和不是根节点）
（例：删除72）
step2”单支节点（即只有左子树或右子树）：让p的子树与p的父亲节点相连，再删除p即可；（注意分是根节点和不是根节点两种情况）
（例：删除79）
step3”节点p的左子树和右子树均不为空：首先找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；或者可以先找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点。
（4）二叉查找树的代码实现
有关二叉查找树的新增和删除节点如何实现，可以阅读《数据结构基础温故—4.树（中）》一文，该文使用C#实现了二叉查找树。
3.2.平衡二叉树
（建议用红黑树）
AVL树
父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，此时就要旋转节点，在编码时，我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增，比如在下图中我们认为树的高度为h=2。
2.旋转
节点再怎么失衡都逃不过4种情况，下面我们一一来看一下。
① 左左情况（左子树的左边节点）
我们看到，在向树中追加“节点1”的时候，根据定义我们知道这样会导致了“节点3"失衡，满足“左左情况“，可以这样想，把这
棵树比作齿轮，我们在“节点5”处把齿轮往下拉一个位置，也就变成了后面这样“平衡”的形式，如果用动画解释就最好理解了。
② 右右情况（右子树的右边节点）
同样，”节点5“满足”右右情况“，其实我们也看到，这两种情况是一种镜像，当然操作方式也大同小异，我们在”节点1“的地方
将树往下拉一位，最后也就形成了我们希望的平衡效果。
③左右情况（左子树的右边节点）
从图中我们可以看到，当我们插入”节点3“时，“节点5”处失衡，注意，找到”失衡点“是非常重要的，当面对”左右情况“时，我们将
失衡点的左子树进行"右右情况旋转"，然后进行”左左情况旋转“，经过这样两次的旋转就OK了，很有意思，对吧。
④右左情况(右子树的左边节点）
这种情况和“情景3”也是一种镜像关系，很简单，我们找到了”节点15“是失衡点，然后我们将”节点15“的右子树进行”左左情况旋转“，
然后进行”右右情况旋转“，最终得到了我们满意的平衡。
3：添加
如果我们理解了上面的这几种旋转，那么添加方法简直是轻而易举，出现了哪一种情况调用哪一种方法而已。
4：删除
删除方法跟添加方法也类似，当删除一个结点的时候，可能会引起祖先结点的失衡，所以在每次”结点“回退的时候计算结点高度。
5: 测试
不像上一篇不能在二叉树中灌有序数据，平衡二叉树就没关系了，我们的需求是检索2012-7-30 4:00:00 到 2012-7-30 5:00:00
的登陆用户的ID，数据量在500w，看看平衡二叉树是如何秒杀对手。
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; using System.IO; using System.Diagnostics; namespace DataStruct { class Program { static void Main(string[] args) { AVLTree<int, int> avl = new AVLTree<int, int>(); Dictionary<DateTime, int> dic = new Dictionary<DateTime, int>(); AVLTree<DateTime, int> tree = new AVLTree<DateTime, int>(); //500w for (int i = 1; i < 5000000; i++) { dic.Add(DateTime.Now.AddMinutes(i), i); tree.Add(DateTime.Now.AddMinutes(i), i); } //检索2012-7-30 4:00:00 到 2012-7-30 5:00:00的登陆人数 var min = Convert.ToDateTime("2012/7/30 4:00:00"); var max = Convert.ToDateTime("2012/7/30 5:00:00"); var watch = Stopwatch.StartNew(); var result1 = dic.Keys.Where(i => i >= min && i <= max).Select(i => dic[i]).ToList(); watch.Stop(); Console.WriteLine("字典查找耗费时间:{0}ms", watch.ElapsedMilliseconds); watch = Stopwatch.StartNew(); var result2 = tree.SearchRange(min, max); watch.Stop(); Console.WriteLine("平衡二叉树查找耗费时间:{0}ms", watch.ElapsedMilliseconds); Console.Read(); } } #region 平衡二叉树节点 /// <summary> /// 平衡二叉树节点 /// </summary> /// <typeparam name="K"></typeparam> /// <typeparam name="V"></typeparam> public class AVLNode<K, V> { /// <summary> /// 节点元素 /// </summary> public K key; /// <summary> /// 增加一个高度信息 /// </summary> public int height; /// <summary> /// 节点中的附加值 /// </summary> public HashSet<V> attach = new HashSet<V>(); /// <summary> /// 左节点 /// </summary> public AVLNode<K, V> left; /// <summary> /// 右节点 /// </summary> public AVLNode<K, V> right; public AVLNode() { } public AVLNode(K key, V value, AVLNode<K, V> left, AVLNode<K, V> right) { //KV键值对 this.key = key; this.attach.Add(value); this.left = left; this.right = right; } } #endregion public class AVLTree<K, V> where K : IComparable { public AVLNode<K, V> node = null; #region 添加操作 /// <summary> /// 添加操作 /// </summary> /// <param name="key"></param> /// <param name="value"></param> public void Add(K key, V value) { node = Add(key, value, node); } #endregion #region 添加操作 /// <summary> /// 添加操作 /// </summary> /// <param name="key"></param> /// <param name="value"></param> /// <param name="tree"></param> /// <returns></returns> public AVLNode<K, V> Add(K key, V value, AVLNode<K, V> tree) { if (tree == null) tree = new AVLNode<K, V>(key, value, null, null); //左子树 if (key.CompareTo(tree.key) < 0) { tree.left = Add(key, value, tree.left); //如果说相差等于2就说明这棵树需要旋转了 if (Height(tree.left) - Height(tree.right) == 2) { //说明此时是左左旋转 if (key.CompareTo(tree.left.key) < 0) { tree = RotateLL(tree); } else { //属于左右旋转 tree = RotateLR(tree); } } } //右子树 if (key.CompareTo(tree.key) > 0) { tree.right = Add(key, value, tree.right); if ((Height(tree.right) - Height(tree.left) == 2)) { //此时是右右旋转 if (key.CompareTo(tree.right.key) > 0) { tree = RotateRR(tree); } else { //属于右左旋转 tree = RotateRL(tree); } } } //将value追加到附加值中（也可对应重复元素） if (key.CompareTo(tree.key) == 0) tree.attach.Add(value); //计算高度 tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1; return tree; } #endregion #region 计算当前节点的高度 /// <summary> /// 计算当前节点的高度 /// </summary> /// <param name="node"></param> /// <returns></returns> public int Height(AVLNode<K, V> node) { return node == null ? -1 : node.height; } #endregion #region 第一种：左左旋转（单旋转） /// <summary> /// 第一种：左左旋转（单旋转） /// </summary> /// <param name="node"></param> /// <returns></returns> public AVLNode<K, V> RotateLL(AVLNode<K, V> node) { //top：需要作为顶级节点的元素 var top = node.left; //先截断当前节点的左孩子 node.left = top.right; //将当前节点作为temp的右孩子 top.right = node; //计算当前两个节点的高度 node.height = Math.Max(Height(node.left), Height(node.right)) + 1; top.height = Math.Max(Height(top.left), Height(top.right)) + 1; return top; } #endregion #region 第二种：右右旋转（单旋转） /// <summary> /// 第二种：右右旋转（单旋转） /// </summary> /// <param name="node"></param> /// <returns></returns> public AVLNode<K, V> RotateRR(AVLNode<K, V> node) { //top：需要作为顶级节点的元素 var top = node.right; //先截断当前节点的右孩子 node.right = top.left; //将当前节点作为temp的右孩子 top.left = node; //计算当前两个节点的高度 node.height = Math.Max(Height(node.left), Height(node.right)) + 1; top.height = Math.Max(Height(top.left), Height(top.right)) + 1; return top; } #endregion #region 第三种：左右旋转（双旋转） /// <summary> /// 第三种：左右旋转（双旋转） /// </summary> /// <param name="node"></param> /// <returns></returns> public AVLNode<K, V> RotateLR(AVLNode<K, V> node) { //先进行RR旋转 node.left = RotateRR(node.left); //再进行LL旋转 return RotateLL(node); } #endregion #region 第四种：右左旋转（双旋转） /// <summary> /// 第四种：右左旋转（双旋转） /// </summary> /// <param name="node"></param> /// <returns></returns> public AVLNode<K, V> RotateRL(AVLNode<K, V> node) { //执行左左旋转 node.right = RotateLL(node.right); //再执行右右旋转 return RotateRR(node); } #endregion #region 是否包含指定元素 /// <summary> /// 是否包含指定元素 /// </summary> /// <param name="key"></param> /// <returns></returns> public bool Contain(K key) { return Contain(key, node); } #endregion #region 是否包含指定元素 /// <summary> /// 是否包含指定元素 /// </summary> /// <param name="key"></param> /// <param name="tree"></param> /// <returns></returns> public bool Contain(K key, AVLNode<K, V> tree) { if (tree == null) return false; //左子树 if (key.CompareTo(tree.key) < 0) return Contain(key, tree.left); //右子树 if (key.CompareTo(tree.key) > 0) return Contain(key, tree.right); return true; } #endregion #region 树的指定范围查找 /// <summary> /// 树的指定范围查找 /// </summary> /// <param name="min"></param> /// <param name="max"></param> /// <returns></returns> public HashSet<V> SearchRange(K min, K max) { HashSet<V> hashSet = new HashSet<V>(); hashSet = SearchRange(min, max, hashSet, node); return hashSet; } #endregion #region 树的指定范围查找 /// <summary> /// 树的指定范围查找 /// </summary> /// <param name="range1"></param> /// <param name="range2"></param> /// <param name="tree"></param> /// <returns></returns> public HashSet<V> SearchRange(K min, K max, HashSet<V> hashSet, AVLNode<K, V> tree) { if (tree == null) return hashSet; //遍历左子树（寻找下界） if (min.CompareTo(tree.key) < 0) SearchRange(min, max, hashSet, tree.left); //当前节点是否在选定范围内 if (min.CompareTo(tree.key) <= 0 && max.CompareTo(tree.key) >= 0) { //等于这种情况 foreach (var item in tree.attach) hashSet.Add(item); } //遍历右子树（两种情况：①:找min的下限 ②：必须在Max范围之内） if (min.CompareTo(tree.key) > 0 || max.CompareTo(tree.key) > 0) SearchRange(min, max, hashSet, tree.right); return hashSet; } #endregion #region 找到当前树的最小节点 /// <summary> /// 找到当前树的最小节点 /// </summary> /// <returns></returns> public AVLNode<K, V> FindMin() { return FindMin(node); } #endregion #region 找到当前树的最小节点 /// <summary> /// 找到当前树的最小节点 /// </summary> /// <param name="tree"></param> /// <returns></returns> public AVLNode<K, V> FindMin(AVLNode<K, V> tree) { if (tree == null) return null; if (tree.left == null) return tree; return FindMin(tree.left); } #endregion #region 找到当前树的最大节点 /// <summary> /// 找到当前树的最大节点 /// </summary> /// <returns></returns> public AVLNode<K, V> FindMax() { return FindMin(node); } #endregion #region 找到当前树的最大节点 /// <summary> /// 找到当前树的最大节点 /// </summary> /// <param name="tree"></param> /// <returns></returns> public AVLNode<K, V> FindMax(AVLNode<K, V> tree) { if (tree == null) return null; if (tree.right == null) return tree; return FindMax(tree.right); } #endregion #region 删除当前树中的节点 /// <summary> /// 删除当前树中的节点 /// </summary> /// <param name="key"></param> /// <returns></returns> public void Remove(K key, V value) { node = Remove(key, value, node); } #endregion #region 删除当前树中的节点 /// <summary> /// 删除当前树中的节点 /// </summary> /// <param name="key"></param> /// <param name="tree"></param> /// <returns></returns> public AVLNode<K, V> Remove(K key, V value, AVLNode<K, V> tree) { if (tree == null) return null; //左子树 if (key.CompareTo(tree.key) < 0) { tree.left = Remove(key, value, tree.left); //如果说相差等于2就说明这棵树需要旋转了 if (Height(tree.left) - Height(tree.right) == 2) { //说明此时是左左旋转 if (key.CompareTo(tree.left.key) < 0) { tree = RotateLL(tree); } else { //属于左右旋转 tree = RotateLR(tree); } } } //右子树 if (key.CompareTo(tree.key) > 0) { tree.right = Remove(key, value, tree.right); if ((Height(tree.right) - Height(tree.left) == 2)) { //此时是右右旋转 if (key.CompareTo(tree.right.key) > 0) { tree = RotateRR(tree); } else { //属于右左旋转 tree = RotateRL(tree); } } } /*相等的情况*/ if (key.CompareTo(tree.key) == 0) { //判断里面的HashSet是否有多值 if (tree.attach.Count > 1) { //实现惰性删除 tree.attach.Remove(value); } else { //有两个孩子的情况 if (tree.left != null && tree.right != null) { //根据平衡二叉树的中顺遍历，需要找到”有子树“的最小节点 tree.key = FindMin(tree.right).key; //删除右子树的指定元素 tree.right = Remove(tree.key, value, tree.right); } else { //自减高度 tree = tree.left == null ? tree.right : tree.left; //如果删除的是叶子节点直接返回 if (tree == null) return null; } } } //统计高度 tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1; return tree; } #endregion } }
3.3.红黑树
另一种与平衡二叉树类似的是红黑树，红黑树和AVL树的区别在于它使用颜色来标识节点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。在.NET中的System.Collections.Generic命名空间下，SortedDictionary类就是使用红黑树实现的。红黑树和AVL树的原理非常接近，但是复杂度却远胜于AVL树，这里也就不做讨论。园子里也已经有了不少关于红黑树的比较好的介绍的文章，有兴趣的可以去阅读阅读。
http://www.cnblogs.com/abatei/archive/2008/12/17/1356565.html
参考：http://www.cnblogs.com/edisonchou/p/4700850.html
http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html
http://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html