查找

2020-01-21T14:18:19

顺序查找、折半查找、索引查找、分块查找是静态查找,动态查找有二叉排序树查找,最优二叉树查找,键树查找,哈希表查找

静态查找表
顺序表的顺序查找:应用范围:顺序表或线性链表表示的表,表内元素之间无序。查找过程:从表的一端开始逐个进行记录的关键字和给定值的比较。

顺序有序表的二分查找。平均查找时间(n+1)/n log2(n+1)

分块查找:将表分成几块,块内无序,块间有序,即前一块中的最大值小于后一块中的最小值。并且有一张索引表,每一项存放每一块的最大值和指向该块第一个元素的指针。索引表有序,块内无序。所以,块间查找用二分查找,块内用顺序查找,效率介于顺序和二分之间;先确定待查记录所在块,再在块内查找。因此跟表中元素个数和块中元素个数都有关。

用数组存放待查记录,
建立索引表,由每块中最大(小)的关键字及所属块位置的信息组成。
当索引表较大时,可以采用二分查找
在数据量极大时,索引可能很多,可考虑建立索引表的索引,即二级索引,原则上索引不超过三级
分块查找平均查找长度:ASLbs = Lb + Lw。其中,Lb是查找索引表确定所在块的平均查找长度, Lw是在块中查找元素的平均查找长度。在n一定时,可以通过选择s使ASL尽可能小。当s=sqrt(n)时,ASL最小。

时间:顺序查找最差,二分最好,分块介于两者之间
空间:分块最大,需要增加索引数据的空间
顺序查找对表没有特殊要求
分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块;另外,增加了索引的维护。
二分查找要求表有序,所以若表的元素的插入与删除很频繁,维持表有序的工作量极大。
在表不大时,一般直接使用顺序查找。
动态查找
二叉排序树的结点删除:

x为叶子结点,则直接删除
x只有左子树xL或只有右子树xR ,则令xL或xR直接成为双亲结点f的子树;
x即有左子树xL也有右子树xR,在xL中选值最大的代替x,该数据按二叉排序树的性质应在最右边。
平衡二叉树:每个结点的平衡因子都为 1、-1、0 的二叉排序树。或者说每个结点的左右子树的高度最多差1的二叉排序树。

平衡二叉树的平衡:

左调整(新结点插入在左子树上的调整):
LL(插入在结点左子树的左子树上):旋转前后高度都为h+1
LR(新插入结点在左子树的右子树上):旋转前后高度仍为h+1
右调整(新结点插入在右子树上进行的调整):
RR(插入在的右子树的右子树上):处理方法和 LL对称
RL(插入在的右子树的左子树上):处理方法和 LR对称
平衡树建立方法:

按二叉排序树插入结点
如引起结点平衡因子变为|2|,则确定旋转点,该点是离根最远(或最接近于叶子的点)
确定平衡类型后进行平衡处理,平衡后以平衡点为根的子树高不变
最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列,可以参考Fibonacci数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。
常见的平衡二叉树:

红黑树是平衡二叉树,也就是左右子树是平衡的,高度大概相等。这种情况等价于一块完全二叉树的高度,查找的时间复杂度是树的高度,为logn,插入操作的平均时间复杂度为O(logn),最坏时间复杂度为O(logn)

  • 节点是红色或黑色。
  • 根是黑色。
  • 所有叶子都是黑色(叶子是NIL节点)。
  • 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。
    avl树也是自平衡二叉树;红黑树和AVL树查找、插入、删除的时间复杂度相同;包含n个内部结点的红黑树的高度是o(logn); TreeMap 是一个红黑树的实现,能保证插入的值保证排序
    STL和linux多使用红黑树作为平衡树的实现:
    如果插入一个node引起了树的不平衡,AVL和RB-Tree都是最多只需要2次旋转操作,即两者都是O(1);但是在删除node引起树的不平衡时,最坏情况下,AVL需要维护从被删node到root这条路径上所有node的平衡性,因此需要旋转的量级O(logN),而RB-Tree最多只需3次旋转,只需要O(1)的复杂度。
    其次,AVL的结构相较RB-Tree来说更为平衡,在插入和删除node更容易引起Tree的unbalance,因此在大量数据需要插入或者删除时,AVL需要rebalance的频率会更高。因此,RB-Tree在需要大量插入和删除node的场景下,效率更高。自然,由于AVL高度平衡,因此AVL的search效率更高。
    map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说,RB-tree的统计性能是高于AVL的。
    查找总结
    既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找。二叉排序树查找,最优二叉树查找,键树查找,哈希法查找是动态查找。分块、顺序、折半、索引顺序查找均为静态。分块法应该是将整个线性表分成若干块进行保存,若动态变化则可以添加在表的尾部(非顺序结构),时间复杂度是O(1),查找复杂度为O(n);若每个表内部为顺序结构,则可用二分法将查找时间复杂度降至O(logn),但同时动态变化复杂度则变成O(n);顺序法是挨个查找,这种方法最容易实现,不过查找时间复杂度都是O(n),动态变化时可将保存值放入线性表尾部,则时间复杂度为O(1);二分法是基于顺序表的一种查找方式,时间复杂度为O(logn);通过哈希函数将值转化成存放该值的目标地址,O(1)
    二叉树的平均查找长度为O(log2n)——O(n).二叉排序树的查找效率与二叉树的高度有关,高度越低,查找效率越高。二叉树的查找成功的平均查找长度ASL不超过二叉树的高度。二叉树的高度与二叉树的形态有关,n个节点的完全二叉树高度最小,高度为[log2n]+1,n个节点的单只二叉树的高度最大,高度为n,此时查找成功的ASL为最大(n+1)/2,因此二叉树的高度范围为[log2n]+1——n.
    链式存储不能随机访问,必须是顺序存储
当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »