Search算法原理
由于查运算的使⽤频率很⾼，⼏乎在任何⼀个计算机系统软件和应⽤软件中都会涉及到，所以当问题所涉及的数据量相当⼤时，查⽅法的效率就显得格外重要。在⼀些实时查询系统中尤其如此。
查的基本概念
1、查表和查
    ⼀般，假定被查的对象是由⼀组结点组成的表(Table)或⽂件，⽽每个结点则由若⼲个数据项组成。并假设每个结点都有⼀个能惟⼀标识该结点的关键字。
    查(Searching)的定义是：给定⼀个值K，在含有n个结点的表中出关键字等于给定值K的结点。若到，则查成功，返回该结点的信息或该结点在表中的位置；否则查失败，返回相关的指⽰信息。
2、查表的数据结构表⽰
（1）动态查表和静态查表
      若在查的同时对表做修改操作(如插⼊和删除)，则相应的表称之为动态查表。否则称之为静态查表。
二叉树的基本性质
（2）内查和外查
      和排序类似，查也有内查和外查之分。若整个查过程都在内存进⾏，则称之为内查；反之，若查过程中需要访问外存，则称之为外查。
3、平均查长度ASL
    查运算的主要操作是关键字的⽐较，所以通常把查过程中对关键字需要执⾏的 平均⽐较次数(也称为平均查长度)作为衡量⼀个查算法效率优劣的标准。
顺序查(Sequential Search)
    在表的组织⽅式中，线性表是最简单的⼀种。顺序查是⼀种最简单的查⽅法。
1、顺序查的基本思想：从表的⼀端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相⽐较；
2、顺序查的存储结构要求：顺序表、链表都可以；
3、数据操作：
查：O(n)
⼆分查
1、⼆分查(Binary Search)
　⼆分查⼜称折半查，它是⼀种效率较⾼的查⽅法。
　⼆分查要求：线性表是有序表，即表中结点按关键字有序，并且要⽤向量作为表的存储结构。不妨设有序表是递增有序的。
2、⼆分查的基本思想　
（1）⾸先确定该区间的中点位置：
（2）然后将待查的K值与R[mid].key⽐较：若相等，则查成功并返回此位置，否则须确定新的查区间，继续⼆分查；
    因此，从初始的查区间]开始，每经过⼀次与当前查区间的中点位置上的结点关键字的⽐较，就可确定查是否成功，不成功则当前的查区间就缩⼩⼀半。
3、⼆分查判定树：⽤来描述⼆分查的过程。
4、算法复杂度：O(logN)
⼆分查失败时所需⽐较的关键字个数不超过判定树的深度，虽然⼆分查效率较⾼，但是其要求是线性表是有序表。
    当⽤线性表作为表的组织形式时，以⼆分查效率最⾼。但由于⼆分查要求表中结点按关键字有序，且不能⽤链表作存储结构，因此，当表的插⼊或删除操作频繁时，为维护表的有序性，势必要移动表中很多结点。这种由移动结点引起的额外时间开销，就会抵消⼆分查的优点。也就是说，⼆分查只适⽤于静态查表。若要对动态查表进⾏⾼效率的查，可采⽤下⾯介绍的⼏种特殊的⼆叉树或树作为表的组织形式。不妨将它们统称为树表。下⾯将分别讨论在这些树表上进⾏查和修改操作的⽅法。
⼆叉排序树
1、⼆叉排序树的定义
  ⼆叉排序树(Binary Sort Tree)⼜称⼆叉查(搜索)树(Binary Search Tree)。其定义为：⼆叉排序树或者是空树，或者是满⾜如下性质的⼆叉树：
①若它的左⼦树⾮空，则左⼦树上所有结点的值均⼩于根结点的值；
②若它的右⼦树⾮空，则右⼦树上所有结点的值均⼤于根结点的值；
③左、右⼦树本⾝⼜各是⼀棵⼆叉排序树。
  上述性质简称⼆叉排序树性质(BST性质)，故⼆叉排序树实际上是满⾜BST性质的⼆叉树。
2、数据操作：
查：最好情况：O(logN)      最坏情况：O(N)
插⼊、删除：O(logN)
虽然⼆叉排序树在查、插⼊、删除上有了较好的性能，但是其最坏情况下，这些数据操作的时间均会增加到O(n)，所以，需要“平衡”⼆叉排序树，使其避免最坏情况的发⽣。
平衡树
1、平衡⼆叉树⼜称AVL树。它或者是颗空树，或者是具有下列性质的⼆叉树：
①它的左⼦树和右⼦树都是平衡⼆叉树，
②左⼦树和右⼦树的深度之差的绝对值不超过1。
若将⼆叉树节点的平衡因⼦BF定义为该节点的左⼦树的深度减去它的右⼦树的深度，则平衡⼆叉树上所有节点的平衡因⼦只可能为-1,0,1.只要⼆叉树上有⼀个节点的平衡因⼦的绝对值⼤于1，那么这颗平衡⼆叉树就失去了平衡。
2、数据操作：
查：O(logN)
插⼊、删除： O(logN)
结点的调整⽅法：
LL型（右旋）、RR型（左旋）
LR型（双旋：左旋、右旋）、RL型（双旋：右旋、左旋）
红⿊树
红⿊树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从⽽提⾼了性能。
红⿊树的5个性质：
每个结点要么是红的要么是⿊的。
根结点是⿊的。
如果⼀个结点是红的，那么它的两个⼉⼦都是⿊的。
对于任意结点⽽⾔，其到叶结点树尾端NIL指针的每条路径都包含相同数⽬的⿊结点。
每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是⿊的。
正是红⿊树的这5条性质，使⼀棵n个结点的红⿊树始终保持了logn的⾼度，从⽽也就解释了上⾯所说的“红⿊树的查、插⼊、删除的时间复杂度最坏为
O(log n)这⼀结论成⽴的原因。
散列表
散列⽅法不同于顺序查、⼆分查、⼆叉排序树及AVL树、红⿊树上的查。它不以关键字的⽐较为
基本操作，采⽤直接寻址技术。在理想情况下，⽆须任何⽐较就可以到待查关键字，查的期望时间为O(1)。
根据设定的散列函数h(key)和处理冲突的⽅法将⼀组关键字key映像到⼀个有限的连续的地址区间上，并以关键字在地址区间中的像作为数据元素在表中的存储位置，这种表便被称为散列表，这⼀映像过程称为散列，所得存储位置称为散列地址。
关键字、散列函数以及散列表的关系如下图所⽰：
1、散列函数
散列函数是从关键字到地址区间的映像。
好的散列函数能够使得关键字经过散列后得到⼀个随机的地址，以便使⼀组关键字的散列地址均匀地分布在整个地址区间中，从⽽减少冲突。
常⽤的构造散列函数的⽅法有：
（1）、直接定址法
取关键字或关键字的某个线性函数值为散列地址，即：
h(key) = key 或 h(key) = a * key + b
其中a和b为常数。
（2）、数字分析法
（3）、平⽅取值法：取关键字平⽅后的中间⼏位为散列地址。
（4）、折叠法
将关键字分割成位数相同的⼏部分（最后⼀部分的位数可以不同），然后取这⼏部分的叠加和（舍去进位）作为散列地址。
（5）、除留余数法
取关键字被某个不⼤于散列表表长m的数p除后所得的余数为散列地址，即：
h(key) = key MOD p p ≤ m
（6）、随机数法
选择⼀个随机函数，取关键字的随机函数值为它的散列地址，即：
h(key) = random(key)
其中random为随机函数。
2、处理冲突
对不同的关键字可能得到同⼀散列地址，即key1 ≠ key2，⽽h(key1)= h(key2)，这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称作同义词。
在⼀般情况下，散列函数是⼀个压缩映像，这就不可避免地会产⽣冲突，因此，在创建散列表时不仅要设定⼀个好的散列函数，⽽且还要设定⼀种处理冲突的⽅法。
常⽤的处理冲突的⽅法有：
（1）、开放定址法
hi =(h(key) + di) MOD m i =1,2,…,k(k ≤ m-1)
其中，h(key)为散列函数，m为散列表表长，di为增量序列，可有下列三种取法：
1)、di = 1,2,3,…,m-1，称线性探测再散列；
2）、di = 12,-12,22,-22,32,…,±k2 (k ≤m/2)，称⼆次探测再散列；
3）、di = 伪随机数序列，称伪随机探测再散列。
（2）、再散列法
hi = rhi(key) i = 1,2,…,k
rhi均是不同的散列函数。
（3）、拉链法
将所有关键字为同义词的数据元素存储在同⼀线性链表中。假设某散列函数产⽣的散列地址在区间[0,m-1]上，则设⽴⼀个指针型向量void *vec[m]，其每个分量的初始状态都是空指针。凡散列地址为i的数据元素都插⼊到头指针为vec[i]的链表中。在链表中的插⼊位置可以在表头或表尾，也可以在表的中间，以保持同义词在同⼀线性链表中按关键字有序排列。
3、散列表上的运算
    散列表上的运算有查、插⼊和删除。其中主要是查，这是因为散列表的⽬的主要是⽤于快速查，且插⼊和删除均要⽤到查操作。
插⼊和删除的时间均取决于查，故只需要分析查操作的时间性能。
    虽然散列表在关键字和存储位置之间建⽴了对应关系，理想情况是⽆须关键字的⽐较就可到待查关键字。但是由于冲突的存在，散列表的查过程仍是⼀个和关键字⽐较的过程，不过散列表的平均查长度⽐顺序查、⼆分查等完全依赖于关键字⽐较的查要⼩得多。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。