§8 查找

§8.1 查找的概念

查找，顾名思义。在查找的同时对表做修改称为 动态查找表，否则是静态查找表。

把查找过程中对关键字执行的 平均比较次数（平均查找长度, Average Search Length, ASL）作为衡量一个查找算法效率优劣的标准，这定义为查找每个元素所需进行的比较次数的加权均值。分为 成功查找 和 不成功查找，这两者是不一样的。

采用顺序存储结构顺序表组织方式。

查找成功时的 ASL $=\Theta(n)$，不成功时的 ASL $=n$。

也就是通常说的二分。查找成功时的 ASL $=\Theta(\log{2} n)$，不成功时的 ASL $=\lceil \log{2}(n+1) \rceil$。

索引存储结构的索引是顺序的。

先找到索引，然后直接定位元素。

主数据表可以分成 若干块，每一块中的元素是无序的，但块与块之间元素是有序的。那先折半找到是在哪个块，然后采用顺序查找方法找到元素。

本质上是 两层多叉树，是二分查找树的变形，其性能介于顺序查找和二分查找之间。

二叉搜索树：不仅区分左子树和右子树，而且整个树的结点是有序的，具体来说，左子树都比根小，右子树都比根大。当然，由于二叉搜索树是一棵二叉树，它可能是空的。

查找成功时的 ASL $=\Theta(\log_{2}n)$，最坏可能到 $\mathrm{O}(n)$。

平衡二叉树：二叉搜索树的每个结点的左、右子树的高度至多相差一。二叉树中每个结点设置一个 平衡因子，表示该结点 左子树的高度减去右子树的高度，它的绝对值小于或等于一。

相较于二叉搜索树的优势就是平衡，查找成功时的 ASL $=\Theta(\log_{2}n)$。