数据结构 查找
- 顺序查找
- 折半查找
- 树形查找：1.二叉排序树 2.平衡二叉树 3.红黑树
- B树及其基本操作、B+树的基本概念
- 散列查找
概念
查找分类
- 静态查找 不改变查找表的结构 对应静态查找表
顺序查找、折半查找 - 动态查找 BST树和AVL树
二叉排序的查找、平衡二叉树的查找
根据存储结构的不同，查找方法可分为四类：
- 顺序表的查找
- 链表的查找
- 散列表的查找
- 索引查找表的查找 包括B树和B+树的查找
查找大的性能分析 关键字比较
- ASL(Average Search Length)关键字的平均比较次数
- ASL成功=总的比较次数/元素个数
- ASL失败=总的比较次数/失败的情形的个数
顺序查找
基本思想：
从表的一端开始逐个将记录的关键字和给定K值进行比较，若某个记录的关键字和给定K值相等，则查找成功；否则，若扫描完整个表，仍未找到相应记录，则查找失败
时间复杂度O(n)
折半查找
又称二分查找
前提：线性表中的记录必须是关键码有序(通常从小到大有序)，线性表必须采用顺序存储。
基本思想：
在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或者所有查找区域无记录，查找失败位置
在查找过程中，首先确定带查找记录在表中的范围，然后逐步缩小范围(每次将待查记录所在区间缩小一半)，只到找到或找不到记录为止
int bin_Search(int *a, int n, int key){
int low=0, high=n-1,mid;
while(low<=high){
mid = (low + high)/2;
if(a[mid] == key)
return mid;
else if(a[mid] > key)
high = mid-1;
else
low = mid+1;
}
return （-1）; //查找失败
}
折半查找过程：判定树 折半树 二叉搜索树
查找次数只和元素个数有关
二叉排序树 BST
BST
二叉排序树或者是空树，或者满足下列性质的二叉树：
1.若左子树不为空，则左子树上所有结点的值都小于根结点的值
2.若右子树不为空，则右子树上所有结点的值都大于根结点的值
3.左、右子树都分别是二叉树
BST树的查找操作
查找操作算法思想：从根开始
1.将给定的K值与二叉排序树的根结点的关键字进行比较；若相等，则查找成功。
2.给定的K值小于BST的根结点的关键字：继续在该结点的左子树上进行查找。
3.给定的K值大于BST的根结点的关键字：继续在该结点的右子树上进行查找
算法实现： 递归或非递归的循环
在随机情况下，二叉排序树的平均查找长度和树的深度是等数量级的
BST树的插入
每次插入的新结点都是BST树的叶子结点，即在插入时不必移动其他结点，仅需修改某个结点的指针即可。
插入思想：
在BST树中插入一个新结点x事，若BST树为空，则令新结点x为插入后BST树的根结点；否则，将结点x的关键子与根结点T的关键字进行比较
1.若相等，则不需要插入。
2.若x < T->key,则结点x插入到T的左子树中
3.若x > T->key,则结点x插入到T的右子树中
BST树的删除
从BST树上删除一个结点，仍然要保证删除后满足BST性质。
存在4种情形：
1.删除叶子结点；
2.删除只有左子树的结点
3.删除只有右子树的结点
4.删除同时具有左子树和右子树的结点（中序直接前驱或中序直接后继，改动最小原则）
BST树的创建
从空树开始，按照结点的顺序逐个插入每个结点，从而建立一颗BST树
即使相同元素，元素的顺序不同，构造出来的二叉排序树的形状也不一样
查找性能分析
在随机情况下，二叉排序树的平均查找长度和树的深度是等数量级的
最好的情况：当二叉排序树的左右子树的高度接近时，此时n个结点的二叉树最小高度为log2(n+1)，平均查找长度为log2(n)。
最坏的情况：当二叉排序树n个结点的最大高度是n，平均查找长度是n。
结论：
BST是一种查找效率比较高的组织形式，但其平均查找长度受树的形态影响较大。当形态比较均匀时，查找效率很好；当形态明显偏向某一方向时，其效率就大大降低
平衡二叉树 AVL
平衡二叉树或者是空树，或者是满足下列性质的二叉树
1.左子树和右子树深度之差的绝对值不超过1
2.左子树和右子树也都是平衡二叉树
结点的平衡因子：二叉树上结点的左子树的深度减去其右子树的深度（-1，0，1）
只要有一个结点的平衡因子的绝对值大于1，该二叉树就不是平衡二叉树
平衡二叉树和二叉排序树的关系
- 二叉排序树 关注于数值，即左子树的值小于根结点的值，根结点的值小于右子树的值
- 平衡二叉树 关注于数的形状
- 平衡二叉排序树 BBST ：二叉树既是二叉排序树，又是平衡二叉树
AVL树的平衡化旋转(AVL树的实现)
平衡化旋转：保持有序性又具有平衡性
插入和删除结点会导致AVL树不平衡
AVL树不平衡情形，共四种：LL、LR、RL、RR
判断不平衡情形：
- 插入：从新插入的结点开始向上，寻找第一个不平衡点，以该点为根，画一条从该点到新插入结点的路径。
- 删除：从被删除的结点的兄弟的最小叶子结点向上寻找，找到第一个不平衡的结点，以该点为根，画一条从该结点到被删除的结点的兄弟的路径。
调整策略
AVL树的查找和性质
平衡二叉排序树BBST的查找和BST树是一样的，而插入和删除分两种情况：
1.如果不涉及调整的问题，和BST树一致；
2.如果遇到调整的问题，需要按照调整策略进行调整；
平衡二叉排序树BBST所有左、右子树的高度基本接近，含有n个结点的平衡二叉排序树BBST的最大深度为O(log2(n))，平衡二叉排序树的平均查找长度为O(log2(n))
设深度为h的平衡二叉排序树所具有的最少结点数为Nh，则由BBST的性质可知
N0=0;
N1=1;
N2=2;
......
Nh=Nh-1 +Nh-2 +1；
红黑树
Red Black Tree
一种特殊平衡二叉查找树。
红黑树的每个结点上都由存储位表示结点的颜色，可以是红色或者黑色。通过任意一条从根结点到叶子结点简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的两倍，因此近似平衡。
特性：
1.每个结点是黑色或红色
2.根结点是黑色
3.每个叶子结点是黑色，叶子结点即指树尾端NULL结点
4.如果一个结点是红色的，那么他的子结点必须是黑色的(注意，如果结点是黑色的，那么它的子结点可以是黑色的，也可以是红色的)
5.从一个结点到该结点的子孙结点的所有路径上都包含相同数目的黑色结点，并且将从某结点（不包含该结点）到叶子结点的任意一条路径上黑色结点的个数称为该结点的 黑高。
定理：一棵含有n个结点的红黑树的高度至多为2log(n+1)
变色，左旋和右旋
- 叔红要变色 父叔变黑色、爷爷变红色
- 叔黑看左右 右子要左旋 左子要右旋
索引查找
B树（B-树）
1.阶 ：子树的个数
2.结点子树范围 ：一棵m阶B-树，除根结点之外，所有非终端结点至少有[m/2,向上取整]，至多有m棵子树
3.根结点比较特殊 根结点是叶子或至少有两棵子树，至多有m棵子树。
4.所有叶子结点都在树的同一层上，即B-树是一个多路平衡的树形结构。
5.B-树的结点包含多个关键字，并且B-树的结点中关键字是有序的
6.非终端结点中关键字的个数范围：[m/2,向上取整]-1 <= n <= m-1, n+1为子树个数
B树 查找
从根结点开始查找 结点包含多个关键字
- 结点之间 随机查找
- 结点内部 顺序查找或折半查找
B树的查找次数等价于树高，含有n个结点，m阶B-树高的范围为logm(n+1) <= h <= logm/2,向上取整
B树 插入
基本思想：
1.在B-树中查找关键字K，若找到，则表明关键字已存在，返回；否则，K的查找操作失败于某个叶子结点，转2.
2.将K插入到该叶子结点中，插入时，若叶子结点的关键字数<=m-1,则直接插入；若叶子结点的关键字数>m-1，则将结点"分裂"
"分裂" -> 将中间关键字放入到父结点中，将左右两边作为中间关键字的左、右子树
B树 删除
B+树
只在叶子结点中存储记录，所有非叶子结点可以看成索引，而其中的关键字作为"分界关键字"，用来界定某一关键字的记录所在的子树。
一棵m阶B+树与m阶B-树的主要差异：
1.若一个结点有n棵子树，则必含有n个关键字。
2.所有叶子结点中包含了全部记录的关键字信息及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接。
3.所有非叶子结点可以看成是索引部分，结点中只含有其子树的根结点中的最大(或最小)关键字
B-树与B+树总结
散列查找
哈希查找的基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系，这样不经过比较，一次存取就能得到所查元素【借助于函数映射的特征进行查找】
哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系。
哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址。
哈希查找(又称为 散列查找)：利用哈希函数进行查找的过程
哈希函数的构造
除留余数法
1.直接定址法：取关键字的某个线性函数值作为哈希地址
2.数字分析法：取关键字的若干位或组合作为哈希地址 适用于关键字位数比哈希地址位数多，并可能出现的关键字事先知道的情况
3.平方取中法：将关键字平方后取中间几位作为哈希地址 适用于不知道全部关键字的情况
4.折叠法 ：将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和作为哈希地址。 移位叠加、间界叠加
5.除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数作为哈希地址，即H(key)=key mod p (p<=m) 式中，p为不大于哈希表长的最大的质数(素数)
冲突解决方法
1.开放定址法
基本思想：当冲突发生时，形成某个探测序列，按此序列逐个探测散列表中的其他地址，直到找到给定的关键字或一个空地址(开放的地址)为止，将发生冲突的记录放到该地址中。
散列地址计算公式：Hi(key)=[H(key) + di] mod m, i=1,2,...,k(k<=m-1) 式中，H(key)为哈希函数，m为散列表长度，di为第i次探测时的增量序列，Hi(key)为经第i次探测后得到的散列地址
- 线性探测法 增量序列为di=1,2,3,...,m-1
- 优点：只要散列表未满，总能找到一个不冲突的散列地址
- 缺点：每个产生冲突的记录被散列到离冲突最近的空地址上，从而又增加了更多的冲突机会（冲突的"聚集"）
- 不成功的标志是从某个位置出发，找到空位置
- 二次探测法 增量序列为di=12,-12,22,-22,32,...,+-k2 (k<= [m/2, 向下取整])
- 优点：探测序列跳跃式地散列到整个表中，不易产生冲突的"聚集"现象。
- 缺点：不能保证探测到散列表的所有地址
2.链地址法
将所有关键字为同义词(散列地址相同)的记录存储在一个单链表中，并用一维数组存放链表的头指针。
优点：不易产生冲突的"聚集"； 删除记录也很简单。
评价哈希查找效率ASL
哈希查找时关键字与给定值比较的次数取决于：
1.哈希函数 2.处理冲突的方法 3.哈希表的装填因子α
装填因子α定义： α = 表中填入的记录数/哈希表长度
开放定址法和链地址法的对比如下：
1.只要哈希表中存在空闲的空间，开放定址法总能找到该空间，并且把元素放入到该空间中，相对较为简单，比较常用。但是，开放定址法删除元素时不能直接删除，只能作标记，因为一旦把某个元素直接删除，有可能导致后续的元素查找失败。
2.链地址法可以充分借助于链式结构按需分配的特征，进行冲突处理，不会产生聚集，但链式结构的查找往往相对较慢
3.采用开放定址法的装填因子不能超过1，但采用链地址法的装填因子远远超过1。
标签：结点,BST,二叉,关键字,查找,哈希,数据结构,408 From： https://www.cnblogs.com/yongchao/p/17156608.html