|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
平衡二叉树又称为AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左、右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1；若将二叉树节点的平衡因子定义为该节点的左子树的深度减去其右子树的深度，则平衡树上所有节点的平衡因子只可能是-1、0和1；只要树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
|
|
|
|
平衡二叉树上的插入操作。失去平衡后进行调整的规律可归纳为4种情况：①单向右旋平衡处理；②单向左旋平衡处理；③双向旋转（从左到右）平衡处理；④双向旋转（从右到左）平衡处理。
|
|
|
|
平衡二叉树上的删除操作：若删除节点的两个子树都不为空，就用该节点左子树上的中序遍历的最后一个节点（或其右子树上的第一个节点）替换该节点，将情况转化为待删除的节点只有一个子树后再进行处理。当一个节点被删除后，从被删节点到树根的路径上所有节点的平衡因子都需要更新，对于每一个位于该路径上的平衡因子为±2的节点来说，都要进行平衡处理。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
折半查找的基本思想是：设查找表的元素存储在一维数组r[1…n]中，那么在表中的元素已经按关键字递增（或递减）的方式排序的情况下，可进行折半查找。其方法是：首先将待查的key值与表r中间位置上（下标为mid）记录的关键字进行比较，若相等则查找成功；若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1…n]中，下一步应在后半个子表中再进行折半查找；若key<r[mid].key，说明待查记录只可能在前半个子表r[1…mid-1]中，下一步应在r的前半个子表中进行折半查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。
|
|
|
折半查找的性能分析：折半查找的过程可以用一棵二叉树描述，不妨设节点总数为n=2h-1，则判定树是深度为h=log2(n+1)的满二叉树。在等概率情况下，折半查找的平均查找长度为 。
|
|
|
|
当n值较大时，ASLbs≈log2(n+1)-1。
|
|
|
|
折半查找比顺序查找的效率高，但它要求查找表进行顺序存储并且按关键字有序排列，因此对表进行元素的插入和删除时，需要移动大量的元素，所以折半查找适用于表不易变动，且又经常进行查找的情况。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
|
|
|
|
|
|
折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
|
|
|
|
|
|
在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。
|
|
|
|
|
|
根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
判定树是判定表的变形。一般情况下，判定树比判定表更直观，而且易于理解和使用。判定树结构如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
