目录导读
┃
1.几个概念
2.查找分类
3.顺序表查找
4.有序表查找
折半查找(二分查找)
插值查找
斐波那契查找(只涉及加减运算)
5.线性索引查找
6.二叉排序树
7.平衡二叉树
8.多路查找树(B树)
9.散列表查找(哈希表)概述
查找(Searching): 就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素(或记录).
如搜索引擎中的搜索某个关键字，它的过程就是查找
1.几个概念
查找表(Search Table)：是由同一类型的数据元素(或记录)构成的集合。它是需要被查找的数据的集合
关键字(Key)：是数据元素中某个数据项(字段)的值，又称为键值。用它可以标识一个数据元素(记录)，也可以标识一个记录的某个数据项，
次关键字(Secondary Key)：不以唯一标识一个数据元素的关键字
数据元素：又称为记录
数据项：又称为字段
查找：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素(或记录).
2.查找分类
┃
静态查找(Static Search Table)：只做查找操作的查找表，即在现有的数据(不会变动)中查找
顺序查找
主要操作：
1)查询某个"特定的"数据元素是否在查找表中
2)检索某个"特定的"数据元素和各种属性
动态查找(Dynamic Search Table)：在查找过程中同时插入查找表中不存在的数据元素，或者从
查找表中删除已经存在的某个数据元素。
主要操作：
1)查找时插入数据元素
2)查找是删除数据元素
注意：从逻辑上来说，查找所基于的数据结构是集合，这个集合中的记录(即数据)之间没有本质关系。
但是为了获得较高的查找性能，我们就需要改变这些数据元素之间的关系，例如在存储时可以将
查找集合组织成表、树等结构。
3.顺序表查找
又叫线性查找，是最基本的查找技术
思想：从表中第一个(或最后一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录
的关键字和给定值相等，则查找成功，找到所查找的记录；若直到最后一个(或第一个)记录，其
关键字和给定值比较都不相等时，则表中没有所查找的记录，查找不成功。
算法分析：
时间复杂度(比较次数)：
最好的情况：O(1)
最坏情况：O(n) , 平均比较次数：(n+1)
平均情况：O(n)， 平均比较次数：(n+1)/2
算法简单，但是效率低下
//---------------------------------------------------------------------------------------------
"代码描述"
public int sequential_search(int[] a, int key) {
for(int i = 0; i < a.length; i++) {
if(key == a[i]) {
return i;
}
}
return 0;
}
评价：上面这段代码，不但要判断 "key == a[i]",还要判断 i < a.length。 因此，可以设置一个哨兵，这样
就不需要没让i与a.length比较。
"代码"
public sequential_search(int[] a, int key) {
a[0] = key; //设置a[0]为关键字值，让其作为哨兵
int i = a.length; //循环从数组尾部开始
while(a[i] != key) {
i --;
}
return i; //返回0则表明没有查找的，返回非0就表明查找到了
}
4.有序表查找
将数据事先进行排序后存放，在查找时就很有帮助了。
核心思想时：每次查找时，选择分割点(这里是最重要的地方)，在不同的区域进行查找。
(1)折半查找(二分查找)
前提要求：线性表中的记录必须是关键码有序(通常是从小到大)，线性表必须采用'顺序存储'。
基本思想：在'有序'的表中，取中间记录作为比较对象，
若给定值等于中间记录的关键字，则查找成功。
若给定值小于中间记录的关键字，则在中间记录的左半区继续查找
若给定值大于中间记录的关键字，则在中间记录的右半区继续查找
不断重复上述过程，知道查找成功为止，或查遍所有记录均没有查到为止。
将折半查找的过程绘制成二叉树，尽管该二叉树并不是完全二叉树，但是仍可以依据完全二叉树的
结构推导概述的深度：logn+1, 即最坏的查找次数为 logn+1
算法分析：
时间复杂度：
最好的情况：O(1)
最坏的情况：O(logn)， 这个相对于顺序查找已经好很多了
缺点：
需要顺序表是有序的，这在频繁插入、删除的数据集中来说，维护有序会带来不小的
工作量。
"代码描述"
/**
* 折半查找
*/
public int binarySearch(int[] a, int key) {
int low = 0; //最小位置处,初始值为0处，
int high = a.lenght - 1; //最大位置处
int mid; //中间位置处
while(low <= high) {
mid= (low + high) / 2 ;
if(key == a[mid]) {
return mid;
} else if(key < a[mid]) {
high = mid - 1;
} else if(key > a[mid]) {
low = mid + 1;
}
}
return -1; //返回-1则表明没有查找到
}
/*********************************************************************/
(2)插值查找
是对折半查找的改进，
将 mid = (low + high) / 2;
改进为：
mid = low + (key - a[low])/(a[high - a[low]])*(high - low);
/**
* 插值查找
*/
public int interpolationSearch(int[] a, int key) {
int low = 0; //最小位置处,初始值为0处，
int high = a.lenght - 1; //最大位置处
int mid; //中间位置处
while(low <= high) {
//改进的地方
mid = low + (key - a[low])/(a[high - a[low]])*(high - low);
if(key == a[mid]) {
return mid;
} else if(key < a[mid]) {
high = mid - 1;
} else if(key > a[mid]) {
low = mid + 1;
}
}
return -1; //返回-1则表明没有查找到
}
/*******************************************************************/
(3)斐波那契查找
利用黄金分割原理来实现的，即利用斐波那契数列来分割,
算法分析：
1)时间复杂度：O(logn)
平均行能斐波那契查找性能较折半查找好，但是在最坏的情况下，比如要查找的数在数列
的最前面，那每次只能向前移动 （1- 0.618）个长度，而折半查找可以移动 0.5 个长度，
因此，这种情况下折半查找的性能略优点
2)斐波那契查找只用加减运算就实现了查找，而'折半查找'与'插值查找'都使用了加减法、除法
运算。因此，在海量的数据查找中，斐波那契查找是有优势的
斐波那契数列：
F: 0 1 1 2 3 5 8 13 21 34 ...
下标 (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) ...
"代码描述"
/**
* @param a 所有的记录
* @param key 待查的关键字
* @return 返回查找结果,-1表名没有查找到相关记录
*/
public int fiboSearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;
int mid;
int k = 0;
//为了计算a数组的长度在斐波那契数列的位置
while(a.length > fo(k) - 1) {
k++;
}
int[] new_a = new int[fo(k) - 1];
//要将给数列补全至 fo(k) -1 时才能使用斐波那契进行分割
for(int i = 0; i < fo(k) - 1; i++) {
if(i >= a.length) {
new_a[i] = a[a.length - 1]; //将剩余部分补齐至fo(k) - 1
}else {
new_a[i] = a[i]; //将a中的数组全部复制到新的数组
}
}
a = new_a; //将新的数组赋予以前的数组
//开始进行查找
while(low <= high) {
mid = low + fo(k-1) - 1; //计算当前分割的下标
if(key < a[mid]) {
//在前半分继续查找
high = mid - 1;
/**
* 这个k是为了控制在数列中的前半段的位置fo(k)
* 此时前半段有fo(k - 1) - 1个元素，因此k=k-1
*/
k = k - 1;
}else if(key > a[mid]) {
//在后半部分继续查找
low = mid + 1;
/**
* 这个k是为了控制在数列中的后半段的位置fo(k)
* 此时后半段有fo(k - 2) - 1个元素，因此k=k-2
*/
k = k - 2;
}else {
//说明key = a[mid]
if(mid <= a.length) {
//说明是在数组的原始部分查找的
return mid;
}else {
//表明是在补全的那一部分查找到的
return a.length;
}
}
}
return -1; //返回-1表明没有查找到该关键字
}
/**
* 产生斐波那契数列
* @param k
* @return
*/
private int fo(int k) {
if(0 == k) {
return 0;
}else if(1 == k) {
return 1;
}else {
return fo(k - 1) + fo(k - 2);
}
}
5.线性索引查找
有序表的查找是基于有序的基础之上的，因此比较高效。但事实，有许多数据集由于数量极多，
通常是按其先后产生时间顺序存储的，对这类数据集只能设立索引。
索引：就是把一个关键字与它对应的记录相关联的过程。它是为了加快查找速度而设计的一种"数据结构"。
一个索引由若干个索引项构成，每个索引项至少应该包含关键字和其对应的记录在存储器中的位置等信息。
索引分类(按结构分)：
┃
线性索引：就是将'索引项'集合组织为线性结构，也称为索引表
┃
稠密索引(空间要求很大)
分块索引(多用于数据库中的查找)
倒排索引
树形索引
多级索引
(1)稠密索引(空间要求很大)
稠密索引：是指在线性索引中，将数据集中的每个记录对应一个'索引项'（理解为记录）。
换言之，就是将数据集中的每一个数据(记录)与索引表中的索引项是一一对应。（数据集中有多少个数据索引表就有多长）
为了快速找到相关关键码在索引表中的位置，将索引项按照关键码有序排列。(这样就可以使用
前面介绍的折半查找、插入产找、斐波那契查找方法在索引表中查找相应的关键码)
(索引表数据结构) (数据集)
下标 关键码 指针 关键码 其他数据项
┌──┬──────┐ ┌──┬────────┐
0 │5 │0x002 │ 0x001 │32│ ... │
├──┼──────┤ └──┴────────┘
1 │26│0x004 │ ┌──┬────────┐
├──┼──────┤ 0x002 │5 │ ... │
2 │32│0x001 │ └──┴────────┘
├──┼──────┤ ┌──┬────────┐
3 │89│0x003 │ 0x003 │89│ ... │
└──┴──────┘ └──┴────────┘
┌──┬────────┐
0x004 │26│ ... │
└──┴────────┘
注意：
从逻辑上来说，查找所基于的数据结构是集合，这个集合中的记录稠密索引虽然方便查找，但是不适合海量数据。因为索引表的长度会和数据集的数据量一样。这样会
造成频繁访问磁盘，反而是性能下降了。
2)分块索引(多用于数据库中的查找)
由于稠密索引的空间代价很大，为了减少索引项的个数，可以对数据集进行分块，使其分块有序，然后
再对每一个块建立一个索引项，从而减少索引项的个数。
注意：
1)分块索引的各个块需要满足的条件：
块间有序：块与块之间是由顺序的，即后面的块中所有记录的关键字均要大于前面块中的所有记录的关键字
块内无序：块内的记录不要关键字有序，当然有序是最好的。
2)分块索引表中的每一条索引项要有三个数据项：
最大关键码：用于存储该块中的所有记录的最大的关键码
块中记录的个数
指向块首数据的指针
(分块索引表数据结构)
最大关键码 块长 块首指针
┌───┬───┬────────┐
│27 │4 │0x001 │
├───┼───┼────────┤
│57 │2 │0x007 │
├───┼───┼────────┤
│96 │3 │0x012 │
└───┴───┴────────┘
分块索引的查找步骤：
1.在分块索引表中查找待查关键字所在的块(即位置)
因为块间是有序的，因此可以使用折半查找、插入查找、斐波那契查找迅速的定位
2.在块内顺序查找待查关键码具体所在地方
因为块内通常是无序的，因此只能使用顺序查找。
分块索引的平均长度分析：
设数据集记录个数为n，平均分为m个块，每个块中有t个记录。
容易得：
m = n / t 或 t = n / m
索引表中查找的平均查找长度(即次数) Lb = (m + 1) / 2,
块中查找的平均查找长度(即次数) Lw = (t + 1) / 2
则，分块索引查找的平均查找长度为：
ASLw = Lb + Lw = (m + 1)/2+(t+1)/2
= 1/2(n/t+t)+1
最佳的情况就是分的块数和块中记录数相同，即 m = t
那么，n = m*t = t^2
ASLw = n^(1/2)+1
因此，分块查找的时间复杂度：O(n^(1/2)),
这个效率比折半查找的O(logn)低一些，但是，它不要求块内有序，从而大大增加了
整体的速度，所以普遍被用于数据库表查找等技术应用中。
3)倒排索引
多用于在搜索引擎中搜索数据，这种查询过程是由记录的属性值来确定相应记录的位置，与
通常由记录来确定属性值的过程是相反的，因次被称为倒排索引。
倒排索引的索引表的数据结构：
次关键码 记录号表(如所在文章编号)
┌────┬──────────┐
│and │ 2,3,5 │
├────┼──────────┤
│be │ 1,2 │
├────┼──────────┤
│free│ 2,3,4 │
├────┼──────────┤
│hand│ 4,8 │
└────┴──────────┘
次关键码：可能被查询记录的属性(即该记录的字段、次关键字，即通常在搜索引擎中输入的关键字)
记录号表：存储具有相同次关键字的所有记录的记录号(可以是指向记录的指针或是该记录的主关键字)
6.二叉排序树
二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一颗空树，或者
是具有下列特点的二叉树：
1)若它的左子树不空，则左子树上所有结点的值均'小于'它的根结点的值
2)若它的右子树不空，则右子树上所有结点的值均'大于'它的根结点的值
3)它的左右子树也分别为二叉排序树。
注意：递归的定义方法定义二叉排序树
构造二叉排序树并不是为了排序，而是为了提高查找和插入删除关键字的速度。
算法分析：
1.同样的数组可以构造不同的二叉排序树(主要表现在树的深度不同)，
2.插入删除性能较好，对于查找操作，整个过程走的就是同根结点到要待查找结点的路径，
其比较次数等于关键字结点所在的二叉树的层数。因此，至少需要比较1次，最多比较次数
不超过树的深度。换言之，二叉排序树的查找性能取决于树的形状。
最优的情况：
二叉排序树是比较平衡的，其深度与完全二叉树相同，均为 logn+1
时间复杂度：O(logn)
最坏的情况
二叉排序树是斜树，深度为n
时间复杂度：O(n)
因此，二叉排序树越平衡越好
"代码描述"
1.二叉树结点的数据结构
public class BinTreeNode<T> {
T data; //结点的值
BinTreeNode<T> lChild; //结点的左子树
BinTreeNode<T> rChild; //结点的右子树
}
2.二叉排序树的查找
/**
* 输入二叉排序树root, 待查找的关键字为key
* f为指向tr的双亲，初始值为null
* p是个临时变量，方法执行完毕，如果找到，它指向查找的结点，
* 如果没有查找到时，它指向查找路径上访问的最后那个结点。
* 如果查找到了，就返回true，否则就返回false
*/
/**
* 查找结点
* @param r 二叉树
* @param key 要查找的关键字
* @param f
* @param p
* @return
*/
public boolean search(BinTreeNode r, int key, BinTreeNode f, BinTreeNode p) {
if(r == null) {
//表明没有查找到
p = f;
return false;
}else if(key == r.data) {
//查找成功
p = r;
return true;
}else if(key < r.data) {
return search(r.lChild, key, r, p); //在左子树中继续查找
}else if(key > r.data) {
return search(r.rChild, key, r, p); //在右子树中继续查找
}
}
3.二叉排序树的插入操作
/**
* 向二叉排序树中插入结点
* @param tree 二叉树
* @param key 要插入的内容
* @return
*/
public int insertBinTree(BinTreeNode tree, int key) {
BinTreeNode p = null;
BinTreeNode s = null; //新的根结点
//插入前先看看该结点存在吗
if(!search(tree, key, null, p)) {
//表明该结点不存在，则需要插入
s = new BinTreeNode();
s.data = key;
s.lChild = null;
s.rChild = null;
if(p == null) {
//表明此树为空树，因此将s作为根结点
tree = s;
}else if(key < p.data) {
p.lChild = s; //插入s为左孩子
}else if(key > p.data){
p.rChild = s; //插入s为右孩子
}
return 1; //插入成功
}
return -1; //表明树种已有关键字相同的结点，则不再插入
}
4.二叉排序树的删除操作
/**
* 删除而二叉排序树的结点
* 情况稍显复杂，需要分情况处理
* @param tree 待删除的那个子树
* @param key
* @return 返回-1表明没有删除，返回1则表明删除成功
*/
public int deleteBinTree(BinTreeNode tree, int key) {
BinTreeNode p = null;
if (tree != null) {
return -1; //不存在关键字为key的结点
}else {
if(key == p.data) {
//找到关键字等于key的结点
return delete(p);
}else if(key < p.data) {
return deleteBinTree(p.lChild, key);
}else {
return deleteBinTree(p.rChild, key);
}
}
}
/**
* 辅助方法，用于删除结点
* @param p
* @return
*/
private int delete(BinTreeNode p) {
BinTreeNode q;
BinTreeNode s;
if(p.rChild == null) {
//右子树为空，只有左子树
p = p.lChild;
}else if(p.lChild == null) {
//左子树为空，只有右子树
p = p.rChild;
}else {
//左右子树都存在的
q = p; //
s = p.lChild;
//寻找要删除结点的左子树的最右结点
while(s.rChild != null) {
q = s;
s = s.rChild;
}
//至此，s指向左子树的最右结点,即要删除结点的直接前驱结点
p.data = s.data; //这里为了后面方便（因为删除叶子结点比较容易）
if(q != p) {
//q和p指向不一致
q.rChild = s.lChild; //将s的左子树接到q的右子树上
}else {
//q和p指向一致，则表明该删除点没有右子树
q.lChild = s.lChild; //将s的左子树接到q的左子树上
}
}
return 1;
}
7.平衡二叉树(AVL树, AVL是两位科学家名字的缩写)
(1)"平衡二叉树"含义：
平衡二叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)，是
一种二叉排序树，其中每一个结点的左子树和右子树的高度最多差1
注意：平衡二叉树的前提是二叉排序树
(2)平衡因子(Balance Factor)
将二叉树结点的左子树深度减去右子树深度的值称为平衡因子，由平衡二叉树的含义可知，
该平衡因子取值只能为：-1， 0， 1
因此，只要，一颗二叉树上有一个结点的平衡因子的绝对值大于1，就表明该二叉树不是平衡二叉树
(3)最小不平衡子树
距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称之为最小不平衡子树
(4)平衡二叉树的实现
1.实现原理
就是在构建二叉排序树的过程中，每当输入一个结点后，先检查是否因为插入这个结点而破坏了
树的平衡性。若是，则找出最小不平衡子树(|BF| > 1)，保持二叉排序树特性的前提下，调整最
小不平衡子树中各结点之间的链接关系，进行相应的旋转(左旋或右旋转)，使之成为新的平衡子树。
注：二叉排序树还有另外的平衡算法，如红黑树
2.算法的具体实现
/**
* 平衡二叉树的实现
* @author Administrator
*/
public class AVLTree {
/**
* 不平衡子树右旋操作
* @param p 不平衡子树的根结点
*/
private void right_Rotate(AVLTreeNode p) {
AVLTreeNode newNode; //辅助变量
newNode = p.lChild; //让newNode指向p的左子树
p.lChild = newNode.rChild; //将newNode的右子树挂接到p的右子树的位置处
newNode.rChild = p; //将现在的p挂接到newNode的右子树的位置处
p = newNode; //让P指向newNode
}
/**
* 不平衡子树左旋转
* @param p 不平衡子树的根结点
*/
private void left_Rotate(AVLTreeNode p) {
AVLTreeNode newNode; //辅助变量
newNode = p.rChild; //让newNode指向p的右子树
p.rChild = newNode.lChild; //将newNode的左子树挂接到p的右子树上，
newNode.lChild = p; //将p挂接到newNode的左子树上
p = newNode; //让p指向newNode
}
/**
* 对以p为根结点的二叉树做左平衡旋转处理
* 注意：此时该子树p的左子树的高度已经大于右子树的高度，即p子树是不平衡的树
* 因此，整体要做右旋转处理
* @param p
*/
private void leftBalance(AVLTreeNode p) {
AVLTreeNode newTree;
AVLTreeNode newTree_Right;
newTree = p.lChild; //newTree指向p的左子树的根结点
switch (newTree.bf) {
//检查T的左子树的平衡度，并做相应的平衡处理
case 1:
//新结点插入在p的左孩子的左子树上，要做单右旋转处理。
//记得要处理相应结点的平衡因此bf
p.bf = newTree.bf = 0;
right_Rotate(p); //做右旋转
break;
case -1:
/**
* 新结点插入在p的左孩子的右子树上(此时会造成p的左子树根结点
* 的bf和p.lChild的右子树的bf符号不一致)，因此，要作双旋处理
* p.lChild的左子树高度低于其右子树的高度，因此，这部分的子树
* 要做左单旋的处理
*/
//左单旋转处理前，先将p的左孩子的右子树的根结点的bf调整为与p的bf符号一致。
newTree_Right = newTree.rChild; //newTree_Right指向p的左孩子的右子树根
switch (newTree_Right.bf) {
//修改P及其左孩子的平衡因子
case 1:
p.bf = -1;
newTree.bf = 0;
break;
case 0:
p.bf = newTree.bf = 0;
break;
case -1:
p.bf = 0;
newTree.bf = 1;
break;
}
newTree_Right.bf = 0;
left_Rotate(p.lChild); //对p的左子树做单左旋转平衡处理
right_Rotate(p); //对p做右旋转的平衡处理
break;
}
}
/**
* 若在平衡的二叉排序树P中不存在和e有相同关键字的结点，则插入一个
* 数据元素为e的新结点并返回1，否则返回0，若因为插入而使二叉排序树
* 失去平衡，则做平衡旋转处理。
* @param p
* @param e
* @param isTaller 反映P树长高与否
* @return
*/
public boolean insertAVL(AVLTreeNode p, int e, boolean isTaller) {
if(p == null) {
//表明此树为空，则插入新结点，即为根结点
p = new AVLTreeNode();
p.data = e;
p.lChild = null;
p.rChild = null;
p.bf = 0; //平衡因子为0
isTaller = true;
}else {
if(e == p.data) {
//p树中已存在和e相同关键字的结点，那么就不用插入
isTaller = false;
return false; //没有插入新的元素，就返回0
}
if(e < p.data) {
//待插入的元素小于p树的根结点关键字,故在左子树上进一步寻找合适的插入位置
if(!insertAVL(p.lChild, e, isTaller)) {
return false ;//未插入
}
if(isTaller) {
//已插入到p的左子树中且左子树“长高”
switch (p.bf) { //检查p的平衡度
case 1:
//原本左子树比右子树高，需要做左平衡处理
leftBalance(p);
isTaller = false;
break;
case 0:
//原本左右子树登高，现因左子树增高而树高度增加
p.bf = 1;
isTaller = true;
break;
case -1: //原本右子树比左子树高，先左右子树等高
p.bf = 0;
isTaller = false;
break;
}
}
}else {
//在p的右子树上进行寻找相应的适合的插入位置
if(!insertAVL(p.rChild, e, isTaller)) {
return false;
}
if(isTaller) {
//已插入到p的右子树且右子树“长高”
switch (p.bf) { //检查p的平衡度
case 1:
//原本左子树比右子树高，现在左右子树等高
p.bf = 0;
isTaller = false;
break;
case 0:
//原本左右子树登高，现因右子树增高而整个树的高度增高
p.bf = -1;
isTaller = true;
break;
case -1:
//原本右子树比左子树高，需要做右平衡处理
rightBalance(p); //待完成
isTaller = false;
break;
}
}
}
}
return true;
}
}
8.多路查找树(B树)
为了处理海量数据(是存放在外存磁盘中)，比如从成千上问的文件中寻找一个文件，如果采用之前的树的结构(如每个节点
中只能存放一个元素,二叉树中只能有两个孩子结点)，那么对于这些海量数据建立的树结构，将会
变得十分庞大(表现在树的度和树的高度上)，这会使内存存取外存中数据的次数非常多，造成时
间效率上的瓶颈。因此，为了解决这些问题，要打破每个结点只存储一个元素的限制。
多路查找树(Muitl-way search tree)，其每一个结点的孩子数可以多于两个，且每一个结点处
可以存储多个元素。
注意：由于它是查找树，所有元素之间存在某种特定的排序关系。
至于每一个结点可以存储多少个元素，以及它可以拥有几个孩子，这是很关键的。
这里只讨论4个特殊的形式：
2-3树
2-3-4树
B 树
B+ 树
(1)2-3树
定义：其中的每一个结点都具有两个孩子(称为2结点)或三个孩子(称为3结点)
注意：
1) 一个结点要么有两个孩子要么有三个孩子，要么没有孩子，不可能出现一个孩子的情况
2) 2结点包含：1个元素和两个孩子(或没有孩子)，其结构类似二叉排序树。区别在于：这
个2结点要么有2个孩子要么没有孩子，不能是只有一个孩子
3结点包含：2个元素(一小一大)和三个孩子(或没有孩子)。如果3结点有孩子的话，左孩子的所有元素
小于较小元素，右孩子的所有元素大于较大元素。中间孩子元素介于这个两个元素之间。
3) 2-3树所有叶子都在同一层次上。
插入操作：
2-3树的插入操作一定是发生在叶子结点上。但是这个插入过程有可能会对该树的其余结构
造成连锁反应。(这是因为插入一个新元素有可能会破坏2-3树的定义，因此需要改变树的其余结
构使其符合2-3树的定义)
具体可分为三种情况：
1)对于空树，插入一个2结点即可
2)插入结点到一个2结点的叶子上，由于该叶子本身只有一个元素，因此只需将其升级为3结点即可
3)插入结点到一个3结点中，这是情况最复杂的，需要调整树的相应结构，甚至增加树的高度
删除操作：
2-3树的删除操作同插入思想一致，删除相应位置的元素后，就需要调其余部分结构，以使该树
符合2-3树的定义。
具体可分为三种情况：
1)删除元素位于3结点的叶子结点上，直接删除即可。(删除后该结点自动变成2结点)
2)删除元素位于2结点上，此时是最复杂的情况,甚至降低整颗树的高度来满足2-3树的定义
3)所删除的元素位于非叶子的分支结点。此时通常是将树按中序遍历后得到此元素的前驱或后继
元素，考虑让其来补充位置即可。
(2)2-3-4树
含义：是2-3树的扩展，增加了一个4结点的使用。一个4结点包含小中大三个元素和四个孩子(或者
就没有孩子)。
注意：4结点有么有4个孩子要么没有孩子
4结点的结构：
┌─────────┐
│ 3 5 8 │
└─────────┘
╱ ╱ ╲ ╲
┌───┐ ┌───┐ ┌───┐ ┌─┐
│1 2│ │ 4 │ │6 7│ │9│
└───┘ └───┘ └───┘ └─┘
(3)B树(B-tree)
含义：是一种平衡的多路查找树，2-3树、2-3-4树都是B树的特例。结点最大的孩子数目称为B树的
阶(order)，因此，2-3树是3阶B树，2-3-4树是4阶B树。
一个m阶的B树具有如下属性：
1.如果根结点不是叶结点，则至少有两颗子树
2.每一个非根的分支结点都有k-1个元素和k个孩子，其中[m/2]≤k≤m; [m/2]表示不小于m/2的最小整数
3.所有叶子结点都位于同一层次上
4.所有分支结点包含下列信息数据：(n,A0,K1,A1,K2,A2,...,Kn,An)
其中，Ki(i=1,2,...n)为关键字，且Ki<Ki+1; Ai(i=1,2,...n)为指向子树根结点的指针，且
指针Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn，
n（[m/2]-1≤n≤m-1）为关键字的个数,n+1为子树的个数
在B树上查找的过程是一个顺指针查找结点和在结点中查找关键字的交叉过程。
例如，要查找某个关键字，首先从外存中读取根结点信息，如果发现待查找关键字不在里面，则
读取该待查找关键字应该在的子树根结点，以此查找，直至成功或查找结束都没有找到而失败为止
对于具有n个关键字的m阶B树，最坏情况下要查找几次呢？
第一次层至少有1个结点，第二层至少有2个结点，除根结点外每个分支结点至少有[m/2]棵子树，则
第三层至少有 2*[m/2] 个结点，...，这样第 k+1 层至少有 2*([m/2])^(k-1) 个结点，而实际上
k+1层的结点就是叶子结点。若m阶B树有n个关键字，那么当找到了叶子结点，其实也就等于查找
不成功的结点为n+1，
因此，n+1 ≥ 2*([m/2])^(k-1)
k ≤ log[m/2]((n+1)/2) + 1
也就是说，在含有n个关键字的B树上查找时，从根结点到关键字结点的路径上涉及的结点树
不超过 log[m/2]((n+1)/2) + 1
(4)B+树
B树虽然好处多，但也是有缺陷的，对于树结构而言，可以通过中序遍历来顺序查找树中的元素，
这都是在内存中进行。但是，这期间要进行多次外存和内存之间的交互，即使是已经访问过的
外存中的资源所在页面(同一页面的不同数据)。
因此，为了能够解决所有元素遍历等基本问题，在原有的B树结构基础上增加了新的元素组织方式
这就是B+树。它是应文件系统所需而设计的一种B树的变形树，从严格意义上讲，它已不再是前面
章节中定义的树了。
结构特点：在B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者(叶子结点)中再
次列出。此外，每个叶子结点都会保存一个指向后一叶子结点的指针。
一棵m阶的B+树和m阶的B树的差异在于(是B+树的特点)：
1.有n棵子树的结点中包含有n个关键字
2.所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身以
关键字的大小自小而大顺序链接
3.所有分支结点应该看成是索引，结点中仅含有其子树中的最大(或最小)关键字
注意：它只能用来索引，而不能提供实际记录的访问，最终还是需要到达包含此关键字的终端结点(即叶子结点)
B+的优点：
1.如果需要从最小到最大的关键字进行顺序查找，就可以从叶子结点层(所有的叶子结点是在
同一层的)最左侧不用经过分支结点，顺序访问下去即可遍历所有的关键字。
2.B+树特别适合带有范围的查找，比如查找班级 18~22 岁之间的学生人数，只需从根结点出发
找到第一18岁的学生，然后在叶子结点中安顺序依次查找符合范围的所有记录
3.B+树的插入和删除是在叶子结点上进行的
9.散列表查找(哈希表)总述
前面的'顺序查找'和'有序表查找'等都是通过待查找关键字与记录中的关键字"比较" 来查找的，但是这种
比较并非非用不可，在某种方式中，可以直接通过待查找关键字就能得到其在内存中的位置。
(1)散列技术
查找某个关键字时，不用比较就可以通过某种方式(函数)直接获得其存储位置，这就是散列技术。
准确来说：散列技术是在记录的存储位置和它的关键字之间建立了一个确定的对应关系f，使得每个
关键字key对应一个存储位置 f(key) 。那么在查找时，根据这个对应关系f直接找到key的映射f(key)，即
其存储位置。换言之，如果查找集合中存在这个记录key，则必定在f(key)的位置上
注：这里讲的对应关系f，就称是哪里额为'散列函数'或'哈希(Hash)函数'
采用散列技术将记录(即关键字)存储在一块连续的存储空间中，该存储空间被称为'散列表'或'哈希表'
这些记录对应的存储位置，被称为'散列地址'或'哈希地址', 这个散列地址是通过散列函数计算的存储位置
┌─────────┐ f ┌─────────────┐
│ 散列表 │ │ 散列地址 │
│(哈希表) │ ──────> │ (哈希地址) │
├─────────┤ ├─────────────┤
│ (记录1) │ │ (存储地址1) │
│ (记录2) │ │ (存储地址2) │
│ ... │ │ ... │
│ (记录n) │ │ (存储地址n) │
└─────────┘ └─────────────┘
(2)散列表的查找过程
整个散列过程就是两步：
1.存储。通过散列函数，计算记录的散列地址，并按该地址存储该记录
2.查找。查找是，我们通过同样的散列函数，计算待查找记录的散列地址，按此地址去访问该记录
散列技术的优缺点：
优点：适合求解查找与给定值相等的记录。由于查找过程没有了比较过程，效率提高了很多
缺点：不适合那种同样的关键字，对应不同的记录的情况。例如，一根班级的男生，
散列表也不适合范围查找
想获得表中记录的排序情况也不可能，如最大、最小值等
(3)散列技术中的核心问题
1.散列函数的设计
如何设计出简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题
2.冲突(collision)的解决
理想中，是不同的记录对用不同的存储地址。但是，在实际中，这是很难的一件事，往往
会出现 key1 ≠ key2，但 f(key1) == f(key2), 这种现象被称为'冲突', 并把 key1 和 key2称为
散列函数的同义词(synoym)
注意：冲突不可能完全解决，只能尽量避免
10.散列函数的设计
什么样的散列函数才是好的？
•'计算简单'
在查找过程中，时间性能是很重要的，因此，散列函数不宜设计的过于复杂，否则导致计算存
储地址时花费大量的时间，得不偿失了
•'散列地址分布均匀'
分布越均匀，存储空间越能被有效利用，并能减少冲突的发生。进一步，减少为了处理冲突而耗费的时间
几种常用的散列函数构造方法
(1)直接定址法(实际中很少使用)
含义: 取关键字的某个线性函数值作为散列地址，即
' f(key) = a*key + b ; a, b 均为常数 '
优缺点：
优：简单、均匀、也不会产生冲突
缺：需要事先知道关键字的分布情况
适合查找表较小且连续的情况
(2)数字分析法
含义：所谓的分析法就是对关键字的各个部分进行分析，选取其中某些部分(往往是那些取值较分散的部分)来计算散列地址
当关键字的位数比较大时(如手机号)，如果事先知道这些关键字的分布且关键字的若干位(即某些部分)分布较为均匀，
就可以考虑用分析法。
为了解决冲突，可以将这些部分进行折叠，循环移位，叠加等处理，其目的就是为了提供一个散列函数，能够
合理的将关键字分配到散列表的各位置。
(3)平方取中法
含义：将关键字平方后，取平方值的中间几位(具体是几位具体分析)，作为散列地址
平方取中的目的就是扩大差别(防止计算出来的散列地址堆积到一起)，同时平方值的中间各位又能受到整个关键字中各位的影响。
适合于：不知道关键字的分布，而且位数又不是很大的情况，
或者关键字中每一位都有某些数字重复出现频度很高的现象
(4)折叠法
含义：是将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然取它们的叠加
和(舍去进位)做散列地址
适用于：事先不需要知道关键字的分布，适合关键字位数较多的情况
具体分为：移位叠加法(低位对齐相加)
间界叠加法(来回折叠相加)
例如：对于关键字 0442205864， 散列表长取为4(即按4为划分部分)
移位叠加法 间界叠加法
5864 5864
4220 0224
+ 04 + 04
─────────── ───────────
10088 6092
散列地址：0088 散列地址：6092
(5)除留余数法(重要)
最常用的构造散列函数的方法。对于散列表长为m的散列函数公式：
'f(key) = key mod p, 其中 P ≤ m '
mod是取模操作，即求余数。
实际，该方法不仅可以对关键字直接进行取模，还可以在折叠、平方取中后再取模
该方法的关键在于p的选取，如果选的不好，易产生冲突。
根据前人的经验，若散列表的表长为m，通常p为小于或等于表长(最好接近m)的最小质数或不包含
小于20的质因子的合数
(6)随机数法
含义：选择一个随机数，取关键字的随即函数值为它的散列地址，即
' f(key) = random(key) , random是随机函数'
适合于：关键字的长度不等时
注意：关键字不一定非得是常见的数字形式才行，因为，那些字符串等是可以转换为某种数字的，本质还是数字
/*-------------------------------------------------------------------------------------*/
总结：
实际中，应视具体情况选取合适的散列函数，通常考虑如下：
1.计算散列地址所需的时间
2.关键字的长度
3.散列表的大小
4.关键字的分布情况
5.记录查找的频率。
11.处理散列冲突的方法
既然冲突无法避免，那就用勇敢的面对吧。
(1)开放定址法(重要)
'核心思想'：就是一旦发生了冲突，就去寻找下一个空的散列地址，并将记录存入。只要散列表足够大，空的散列地址总能找到。
具体的处理方法：
1.线性探测法
' fi(key) = (f(key) + di) mod m , (di=1,2,3, ... , m-1)，m为散列表长 '
对于每一个关键字计算散列地址时，若发现f(key)冲突了，则将di依次取1,2,..., 计算新的fi(key)
注意：
·只能向前寻找新的存储位置
·堆积：那些本来不是同义词的关键字，现在却在存储过程中会出现争夺同一个地址的情况(即产生冲突)，称这种现象为堆积。
·堆积的现象会使存入和查找效率大大降低
2.二次探测法
' fi(key) = (f(key) + di) mod m , (di=1^2, -1^2, 2^2, -2^2, ..., q^2, -q^2) , q≤m/2 '
注意：
可以双向寻找可能的空位置(提高的空间利用率)
3.随机探测法
位移量di采用随机函数计算得到(生成为随机数叫伪随机数)
' fi(key) = (f(key) + di) mod m , (di是一个随机数列) '
注意：
·这里位移量di是伪随机数，所谓的伪随机数就是通过一定的算法生成的一系列数，因此随机
种子如果是一样的，那么这个随机序列就是固定的。因此，存入和查找仍然是一致的。
(2)再散列函数法
'核心思想'：另起炉灶，即当前发生冲突时，就更换散列函数，重新计算散列地址。
' fi(key) = RHi(key) , (i = 1,2,...,k) , RHi代表不同的函数'
RHi可以是除留余数法、平方取中法、折叠法等前面介绍的那些散列函数
缺点：要更换散列函数重新计算散列地址，因此在时间性能上就要打折扣了
(3)链地址法
白话：我就要做老赖，既然看上这个房子了，就是不走，你能住我也能住 ^_^？
'核心思想'：将所有发生冲突的关键字存储在单链表中(该链表被称为同义词子表)，挂接在发生冲突的这个散列地址处。
如下图所示：
用除留余数法做散列函数
关键字：[12,67,56,16,25,37,22,29,15,47,48,34]
m = 12
┌────┐
0 │ │→ 48 → 12
├────┤
1 │ │→ 37 → 25
├────┤
2 │ ^ │
├────┤
3 │ │→ 15
├────┤
...
注意：
优点：该方法对于那些容易产生冲突的散列函数而言，是绝不会出现找不到地址的保障。
缺点：查找是需要遍历单链表，这就使得查找性能受到影响
(4)公共溢出区法
白话：将那些不安分的家伙，单独关起来(即放到公共区)
'核心思想'：将产生冲突的关键字单独顺序存储到溢出区中。
基本表 溢出表
┌────┐ ┌─────┐
0 │ 12 │ 0 │ 37 │
├────┤ ├─────┤
1 │ 25 │ 1 │ 48 │
├────┤ ├─────┤
2 │ ^ │ 2 │ 34 │
├────┤ ├─────┤
3 │ 15 │ 3 │ ^ │
├────┤ ├─────┤
... ...
查找过程：
通过散列函数计算关键字的散列地址，在基本表中相应位置对比；
如果相等，则查找成功；
如果不想等，则到溢出表中进行'顺序查找'。
注意：
该方法适合于冲突情况较少的情况。这样溢出表就不会过大了。
12.散列表查找的代码实现
'代码实现'
public class HashTableSearch {
private int hashSize; //定义散列表长
private int[] elem; //关键字存放的数组
private int count; //当前元素的个数
private final int NULLKEY = -32768; //用于标识没有元素存入
private int m;
//初始化
private void init0(int hashSize) {
this.hashSize = hashSize;
this.m = hashSize;
elem = new int[hashSize];
for(int i = 0; i < hashSize; i++) {
elem[i] = NULLKEY;
}
}
//定义散列函数:也可以是其他的函数
private int hash(int key) {
return key % m; //采用除留余数法
}
//对关键字进行插入操作
public void insertHash(int[] keyArr) {
init0(keyArr.length); //初始化
int addr; //表示地址
int d; //线性探测的移位步长
for(int i = 0; i < keyArr.length; i++) {
addr = hash(keyArr[i]);
int addr0 = addr;
d = 1; //线性探测的移位步长
while(elem[addr] != NULLKEY) {
//说明位置已经被占了，需要解决冲突：可以是开发定址法、再散列法、链地址法等
addr = (addr0 + d++) % m; //使用开发定址法的线性探测法
}
//说明已经找到了空的位置
elem[addr] = keyArr[i]; //插入关键字
}
}
/**
* 通过散列表查找记录
* 返回-1表示没有该关键字
* @param key
* @return
*/
public int search(int key) {
int addr = hash(key);
int addr0 = addr;
int d = 1; //线性探测的移位步长
while(elem[addr] != key) {
addr = (addr0 + d++) % m;
if(elem[addr] == NULLKEY || addr0 == addr) {
//搜索到NULLKEY或搜索了一圈回到起点，则表明没有该关键字
return -1; //
}
}
return addr;
}
}
13.散列表查找性能分析
如果没有冲突(实际是不可能的)的话，时间复杂度：O(1)
实际其查找长度取决一下几点：
1.选取的散列函数
散列函数是否均匀？
2.处理冲突的方法
即使相同的关键字、相同的散列函数，但处理冲突的方法不同，会使平均查找长度不同。
比如，线性探测处理就可能产生堆积，显然没有二次探测好
链地址法不会产生任何堆积，因而其平均查找性能更好点
3.散列表的装填因子
含义：装填因子 α = 装入表中的记录个数/散列表长
α表示散列表的装满程度。α越小发生冲突的可能性越低，反之越高。
通常将散列表的长度设计的比查找集合大，这样就是α较小，从而使冲突的产生减小
一般情况下，认为选取的散列函数是均匀的，则在讨论平均查找长度ASL时只考虑处理冲突的方法和装填因子
证明得：
(1)线性探测法处理冲突：ASL≈ 1/2*(1 + 1/(1-α))
(2)平方探测法：ASL≈ -1/α*ln(1 - α)
(3)链地址法：ASL≈ 1 + α/2
网友评论