查找
root(查找) 线性结构 顺序查找 折半查找 分块查找 树形结构 二叉排序树 二叉平衡树 红黑树 B树、B+树 散列结构 散列表查找的基本概念
在数据集合中寻找满足某各种条件的数据元素的过程称为查找。
用于查找的数据集合称为查找表，它由同一类型的数据元素组成，可以是一个数组或链表等数据结构。对查找表的操作一般有四种：
- 查询某个特定的数据元素是否在查找表中。
- 检索满足条件的的某个特定的数据元素的各种属性。
- 在擦杭州啊表中插入一个数据元素。
- 从查找表中删除某个数据元素。
若一个查找表的操作只涉及上述操作1和2，则无须动态的改变查找表，此类查找表称为静态查找表，与此对应，需要动态的插入或删除的查找表称为动态查找表。
对应静态查找表的查找方法有顺序查找、折半查找、散列查找；适合动态查找表的查找方式有二叉排序树的查找、散列查找等。
数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中惊醒关键字的比较次数的平均值，平均查找长度是衡量查找算法效率的最主要的指标。
顺序查找
顺序查找又称为线性查找，它对顺序表和链表都是适用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，可通过指针 next 来一次扫描每个元素。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找，如果是一般线性表的顺序查找即通过“哨兵”从一端开始查找到表的另一端，如果“哨兵”找到关键字则跳出循环，查找成功；如果到另一端也没有找到关键字则查找失败，成功的ASL为 (n+1)/2。如果是有序表的顺序查找，则不需要再比较到另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度，所以其 ASL 会好一些。
顺序查询的好处是对数据元素的存储没有要求，无论是顺序和链式存储皆可，记录按关键字有序也均可，缺点就是如果 n 过大平均查找长度较大，效率低；
折半查找（二分查找）
折半查找仅适用于有序的顺序表。基本思想是首先将给定 key 与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分和后半部分，然后再缩小的范围内继续进行同样的查找，如此重复直到找到为止，或确定表中没有所需要查找的元素，则查找不成功。
::: normal-demo 二分查找(Java)
public static <T extends Comparable<T>> T binarySearch(T[] array, T target) { int left = 0; int right = array.length - 1;
while (left <= right) { int mid = left + (right - left) / 2; int result = target.compareTo(array[mid]);
if (result == 0) { return target; } else if (result < 0) { right = mid - 1; } else { left = mid + 1; } }
return null;}:::
折半查找的过程可以用二叉树来描述，称为判定树。树中的圆形结点表示一个记录，结点中的值为该记录的关键字值；树最下面叶结点表示不成功的查找条件。从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点树，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数。显然，判定树是一颗平衡二叉树。所以二分查找的平均查找长度为ASL=log2(n+1)-1。
因为折半查找需要方便的定位查找区域，所以它要求线性表必须具有随机存取的特性。因此，该查找方法仅适用于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。
分块查找
分块查找又称为索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。
分块查找的基本思想：将查找表分为若干子块。块内的元素可以无序，但块间的元素是有序的，即第一个块中的最大关键小于第二块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。
分块查找的过程分为两步：第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；第二步是在块内顺序查找。
将长度为n的查找表均匀的分为b块，每块有s个记录，平均查找长度ASL=(s^2+2s+n)/2s。
树型查找
二叉排序树（BST）
二叉排序树有称为二叉查找树，它可以是一颗空树，它具有以下特点：
- 若左子树非空，则左子树上所有结点的值均小于根结点的值。
- 若右子树非空，则右子树上所有的结点的值均大于根结点的值。
- 左右子树分别也是一颗二叉排序树。
查找
二叉排序树的查找是从根结点开始，沿着某个分支逐层向下比较的过程。若二叉排序树非空，先将给定值和根结点关键字比较，若相同则返回成功，若不相同则在根结点的左子树寻找，否则在右子树寻找。
插入
二叉排序树是一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字值等于给定值时在进行插入的。过程如下：若原二叉树为空，则直接插入，否则，若小于根结点值，则插入到左子树，否则插入到右子树。
删除
二叉排序树中删除一个结点的时候，不能把以该结点为根的子树上的结点全部删除，必须先把被删除结点从存储二叉树排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操作按照下面三种情况来处理：
- 若被删除的结点 z 是叶结点，则直接删除，不会破坏二叉树的性质。
- 若结点 z 只有一颗左子树或者右子树，则让 z 的子树成为 z 父结点的子树来代替 z 的位置即可。
- 若结点 z 既有左子树又有右子树，则令 z 的直接后继（直接前驱）代替 z，然后从二叉排序树删去找个直接后继（直接前驱），这样就转换成了第一或第二种情况。
效率分析
二叉排序树的查找效率主要取决于树的高度，若是平衡二叉树，则平均查找长度就是 O(log2n)，如果是有序的单枝树，则平均查找长度就会变成 O(n)。
平衡二叉树（AVL）
为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除结点时，要保证任意结点的左右子树高度差的绝对值不超过 1，将这样的二叉树成为平衡二叉树。
插入
基本思想：每当在二叉排序树中插入或删除一个结点的时候，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 A，然后再对 A 为根的子树保持二叉排序树特性的前提下调整各个结点的位置关系。
删除
查找
红黑树
为了保持 AVL 树的平衡性，插入和删除后非常频繁的调整全树整体拓扑结构代价太大，为此放宽条件成为红黑树：
- 每个结点或是红色或是黑色。
- 根结点是黑色的。
- 叶结点都是黑色的。
- 不存在两个相邻的红结点。
- 对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。