相关文献：
数据结构与算法(一)：基础理论
数据结构与算法(二)：线性表的实现
数据结构与算法(三)：线性表算法设计练习
数据结构与算法(四)：斐波那契数列
数据结构与算法(五)：LRU
数据结构与算法(六)：栈
数据结构与算法(七)：栈/队列的算法解题思想
数据结构与算法(八)：队列
数据结构与算法(九)：树形结构/二叉树/线索化二叉树
数据结构与算法(十)：哈夫曼树
数据结构与算法(十一)：图形结构
数据结构与算法(十二)：图的应用-最小生成树-Prim/Kruskal
数据结构与算法(十三)：图的应用-最短路径-Dijkstra/Floyd
数据结构与算法(十四)：图的应用-拓扑排序/关键路径
数据结构与算法(十五)：查找算法-顺序查找/二分查找/二叉搜索树/平衡二叉树/散列表查找
数据结构与算法(十六)：排序算法
本文掌握知识点：
1.静态查找：顺序查找、二分查找、差值查找、斐波那契查找
2.动态查找：二叉搜索树(创建/查找/删除)（二叉搜索树 = 二叉排序树 = 二叉查找树）
3.平衡二叉树的分析与实现
4.散列表查找（哈希公式的设计与哈希冲突的解决方案）
静态查找表(Static Search Table) (只作查找操作的查找表)
1.查询某个”特定的”数据元素是否在查找表中;
2.检索某个"特定的"数据元素和各种属性;
动态查找表(Dynamic Search Table): 在查找过程中同时插⼊查找表中不存在的数据元素, 或者从查找表中删除已经存在的某个数据元素; 显然动态查找表的操作就是2个动作
1.查找时插⼊数据元素;
2.查找时删除数据元素;
一、静态查找
1.顺序查找（线性查找）
顺序查找(Sequential Search), ⼜称为线性查找. 是最基本的查找技术.
查找过程: 从表中的第⼀个(或最后⼀个)记录开始,逐个进⾏记录关键字和给定值⽐较;
1.若某个记录的关键字和给定值相等,则查找成功,找到所查记录;
2.如果直到最后⼀个(或第⼀个)记录, 其关键字和给定值⽐较都不等
时, 则表中没有所查的记录,查找不成功;
//1.顺序查找
//a为数组,n为查找的数组个数,key为要查找的关键字;
int Sequential_Search(int *a,int n,int key){
for (int i = 1; i <= n ; i++)
if (a[i] == key)
return i;
return 0;
}
这样写呢，每一次都需要对空间是否越界作为判断 ( i <= n )，下面做一个查找优化：
//2.顺序查找_哨兵
int Sequential_Search2(int *a,int n,int key){
int i;
//设置a[0]为关键字值,称为'哨兵'
a[0] = key;
//循环从数组尾部开始
i = n;
while (a[i] != key) {
i--;
}
//返回0,则说明查找失败
return i;
}
2.折半查找（二分查找）
折半查找(Binary Search)⼜称为⼆分查找：
• 它的前提是线性表中的记录必须是关键码有序(通常是从⼩到⼤有序),线性表必须采⽤顺序存储。
• 折半查找的基本思想:
在有序表中,取中间记录作为⽐较对象,若给定值与中间记录的关键字相
等则查找成功;
若给定值⼩于中间的记录关键字,则在中间记录的左半区继续查找;
若给定的值⼤于中间记录的关键字,则在中间记录的右半区继续查找;
不断重复以上的过程,直到查找成功,或所以查找区域⽆记录,查找失败
为⽌。
若本身无序的话，记录量不算大则建议使用顺序查找。
//3.折半查找算法
//假设数组a,已经是有序的(从小到大)
int Binary_Search(int *a,int n,int key){
int low,high,mid;
//定义最低下标为记录首位
low = 1;
//定义最高下标为记录末位
high = n;
while (low <= high) {
//折半计算
mid = (low + high) /2;
if (key < a[mid]) {
//若key比a[mid] 小,则将最高下标调整到中位下标小一位;
high = mid-1;
}else if(key > a[mid]){
//若key比a[mid] 大,则将最低下标调整到中位下标大一位;
low = mid+1;
}else
//若相等则说明mid即为查找到的位置;
return mid;
}
return 0;
}
3.差值查找 (折半查找的优化)
设想：既然我们每次查找的时候能把有序的范围缩短一半，那可不可以缩短到更短呢？或者说定位更精确一些呢？
折半查找的优化：插值查找
折半查找的公式
理解为: mid 等于最低下标low 加上最⾼下标high 与 low 的差的⼀半
那么考虑将1/2进⾏改进. 改进如下⾯的计算⽅案:
折半查找公式优化
由于low/high不是固定的折半而是浮动的，所以这个算法更加适合有序且比较均匀的数据。
举例
//4. 插值查找
int Interpolation_Search(int *a,int n,int key){
int low,high,mid;
low = 1;
high = n;
while (low <= high) {
//插值
mid = low + (high-low)*(key-a[low])/(a[high]-a[low]);
if (key < a[mid]) {
//若key比a[mid]插值小,则将最高下标调整到插值下标小一位;
high = mid-1;
}else if(key > a[mid]){
//若key比a[mid]插值 大,则将最低下标调整到插值下标大一位;
low = mid+1;
}else
//若相等则说明mid即为查找到的位置;
return mid;
}
return 0;
}
4.斐波那契查找(折半查找的优化)
利用黄金分割原理来实现的，要使用斐波那契查找先要得到一个斐波那契数列。
- a.案例一：
F为斐波那契数列、a为被查找的数组
n为a数组有多少个元素，key是查找的关键字。
a[11]和a[12]是补齐的位
黄金分割原理计算出 mid
若是key找到在a数组中越界了，则回退
- b.案例二：
思想是缩小查找范围
//5.斐波拉契查找
int F[100]; /* 斐波那契数列 */
int Fibonacci_Search(int *a,int n,int key){
int low,high,mid,i,k;
//最低下标为记录的首位;
low = 1;
//最高下标为记录的末位;
high = n;
k = 0;
//1.计算n为斐波拉契数列的位置;
while (n > F[k]-1) {
k++;
}
//2.将数组a不满的位置补全值;
for(i = n;i < F[k]-1;i++)
a[i] = a[n];
//3.
while (low <= high) {
//计算当前分隔的下标;
mid = low+F[k-1]-1;
if (key < a[mid]) {
//若查找的记录小于当前分隔记录;
//将最高下标调整到分隔下标mid-1处;
high = mid-1;
//斐波拉契数列下标减1位;
k = k-1;
}else if(key > a[mid]){
//若查找的记录大于当前的分隔记录;
//最低下标调整到分隔下标mid+1处
low = mid+1;
//斐波拉契数列下标减2位;
k = k-2;
}else{
if (mid <= n) {
//若相等则说明,mid即为查找的位置;
return mid;
}else
{
//若mid>n,说明是补全数值,返回n;
return n;
}
}
}
return 0;
}
5.测试代码
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 静态查找!\n\n");
int a[MAXSIZE+1],i,result;
int arr[MAXSIZE] = {0,1,16,24,35,47,59,62,73,88,99};
for (i = 0; i<= MAXSIZE; i++) {
a[i] = i;
}
//1,顺序查找
result=Sequential_Search(a,MAXSIZE,MAXSIZE);
printf("顺序查找:%d\n",result);
//2,顺序查找_哨兵
result=Sequential_Search2(a,MAXSIZE,1);
printf("顺序查找_哨兵:%d \n",result);
//3.折半查找
result=Binary_Search(arr,10,62);
printf("折半查找:%d \n",result);
//4.插值查找
result=Interpolation_Search(arr,10,62);
printf("插值查找:%d \n",result);
//5.斐波拉契查找
//斐波拉契数列计算;
F[0]=0;
F[1]=1;
for(i = 2;i < 100;i++)
{
F[i] = F[i-1] + F[i-2];
}
result=Fibonacci_Search(arr,10,99);
printf("斐波拉契查找:%d \n",result);
result=Fibonacci_Search(arr,10,59);
printf("斐波拉契查找:%d \n",result);
printf("\n");
return 0;
}
公式演变，都是在缩小查找范围
二、动态查找
在我们对线性表的顺序存储的时候，使用二分查找/差值查找/斐波那契查找去查找一条记录，若是关乎于插入删除操作的话，就会显得格外的棘手：
它需要将要插入的元素找到合适的位置，别的元素需要先挪位置再插入，就会显得非常麻烦。
而使用二叉树就可以很好地解决这个困扰。
大的放右边，小的放左边
1.二叉搜索树
⼆叉排序树(Binary Sort Tree),⼜称为⼆叉查找树. 它或者是⼀颗空树.或者是⼀颗具有下列性质的⼆叉树：
- 若它的左⼦树不空,则左⼦树上所有结点的值均⼩于它的根结构的值;
- 若它的右⼦树不空,则右⼦树上的所有结点的值均⼤于它的根结点的值;
- 它的左右⼦树也分别是⼆叉排序树;
⼆叉树的⼆叉链表结点结构定义:
//结点结构
typedef struct BiTNode
{
//结点数据
int data;
//左右孩⼦指针
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
以该数据为例 [62,88,58,47,35,73,51,99,37,93] 去构建二叉树：
设计⼀个查找算法,在⼆叉排序树.找到关键字 key = 93 的结点:
1.使⽤什么样的⽅式进⾏查找?
2.怎么判断查找失败?
定义二叉树
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;
//二叉树的二叉链表结点结构定义
//结点结构
typedef struct BiTNode
{
//结点数据
int data;
//左右孩子指针
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
二叉排序树--查找
//1.二叉排序树--查找
/*
递归查找二叉排序树T中,是否存在key;
指针f指向T的双亲,器初始值为NULL;
若查找成功,则指针p指向该数据元素的结点,并且返回TRUE;
若指针p指向查找路径上访问的最后一个结点则返回FALSE;
*/
Status SearchBST(BiTree T,int key,BiTree f, BiTree *p){
if (!T) /* 查找不成功 */
{
*p = f;
return FALSE;
}
else if (key==T->data) /* 查找成功 */
{
*p = T;
return TRUE;
}
else if (key<T->data)
return SearchBST(T->lchild, key, T, p); /* 在左子树中继续查找 */
else
return SearchBST(T->rchild, key, T, p); /* 在右子树中继续查找 */
}
二叉排序树--插入
ps: 我这里是保证节点的唯一性，实战中得根据自己的需求来插
//2.二叉排序树-插入
/* 当二叉排序树T中不存在关键字等于key的数据元素时， */
/* 插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key) {
BiTree p,s;
//1.查找插入的值是否存在二叉树中;查找失败则->
if (!SearchBST(*T, key, NULL, &p)) {
//2.初始化结点s,并将key赋值给s,将s的左右孩子结点暂时设置为NULL
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
//3.
if (!p) {
//如果p为空,则将s作为二叉树新的根结点;
*T = s;
}else if(key < p->data){
//如果key<p->data,则将s插入为左孩子;
p->lchild = s;
}else
//如果key>p->data,则将s插入为右孩子;
p->rchild = s;
return TRUE;
}
return FALSE;
}
二叉排序树--删除
删除叶子节点
删除中间节点
我们可以找到与47相近的节点去代替47，能完成这一查找相近节点操作的可以通过中序遍历
当然我们不需要通过中序遍历去拿到节点，这样太麻烦。
47的中序遍历前驱一定是47的左子树的第一个右孩子。
47的中序遍历的后继一定是47的右子树最后一个左孩子。
将37代替到47的位置
将48代替到47的位置
代码以37替换掉47为例：
//3.从二叉排序树中删除结点p,并重接它的左或者右子树;
Status Delete(BiTree *p) {
BiTree temp,s;
if((*p)->rchild == NULL){
//情况1: 如果当前删除的结点,右子树为空.那么则只需要重新连接它的左子树;
//①将结点p临时存储到temp中;
temp = *p;
//②将p指向到p的左子树上;
*p = (*p)->lchild;
//③释放需要删除的temp结点;
free(temp);
}else if((*p)->lchild == NULL){
//情况2:如果当前删除的结点,左子树为空.那么则只需要重新连接它的右子树;
//①将结点p存储到temp中;
temp = *p;
//②将p指向到p的右子树上;
*p = (*p)->rchild;
//③释放需要删除的temp结点
free(temp);
}else{
//情况③:删除的当前结点的左右子树均不为空;
//①将结点p存储到临时变量temp, 并且让结点s指向p的左子树
temp = *p;
s = (*p)->lchild;
//②将s指针,向右到尽头(目的是找到待删结点的前驱)
//-在待删除的结点的左子树中,从右边找到直接前驱
//-使用`temp`保存好直接前驱的双亲结点
while (s->rchild) {
temp = s;
s = s->rchild;
}
//③将要删除的结点p数据赋值成s->data;
(*p)->data = s->data;
//④重连子树
//-如果temp 不等于p,则将S->lchild 赋值给temp->rchild
//-如果temp 等于p,则将S->lchild 赋值给temp->lchild
if(temp != *p)
temp->rchild = s->lchild;
else
temp->lchild = s->lchild;
//⑤删除s指向的结点; free(s)
free(s);
}
return TRUE;
}
//4.查找结点,并将其在二叉排序中删除;
/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{
//不存在关键字等于key的数据元素
if(!*T)
return FALSE;
else
{
//找到关键字等于key的数据元素
if (key==(*T)->data)
return Delete(T);
else if (key<(*T)->data)
//关键字key小于当前结点,则缩小查找范围到它的左子树;
return DeleteBST(&(*T)->lchild,key);
else
//关键字key大于当前结点,则缩小查找范围到它的右子树;
return DeleteBST(&(*T)->rchild,key);
}
}
测试代码
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 二叉排序树(Binary Sort Tree)!\n");
int i;
int a[10]={62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i=0;i<10;i++)
{
InsertBST(&T, a[i]);
}
BiTree p;
int statusValue = SearchBST(T, 99, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",p->data,statusValue);
statusValue = DeleteBST(&T,93);
printf("二叉排序树删除93是否成功:%d (1->YES/0->NO)\n",statusValue);
statusValue = DeleteBST(&T,47);
printf("二叉排序树删除47是否成功:%d (1->YES/0->NO)\n",statusValue);
statusValue = DeleteBST(&T,12);
printf("二叉排序树删除12是否成功:%d (1->YES/0->NO)\n",statusValue);
statusValue = SearchBST(T, 93, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",93,statusValue);
statusValue = SearchBST(T, 47, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",47,statusValue);
statusValue = SearchBST(T, 99, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",99,statusValue);
printf("\n");
return 0;
}
二叉搜索树也是有缺点的，比如说我们的数据是升序/降序的，它的二叉树就是只有左子树/只有右子树的斜树，那么二叉搜索树的查找就会变得非常慢，而且更坏的情况是没有办法得到我们想要的结果。
斜树
既然它是一个不平衡的二叉树，那么我们就将它调平衡，下面就介绍我们的平衡二叉树。
三、平衡二叉树（AVL树）
平衡⼆叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)，是⼀种⼆叉排序树。其中每⼀个结点的左⼦树和右⼦树的⾼度差最多等于1。在设计一棵树的时候，把它达到高度平衡。
（平衡二叉树只是对二叉排序树进行优化，以解决二叉排序树出现斜树的问题）
⾼度平衡：要么它是⼀颗空树,要么它的左⼦树和右⼦树都是平衡⼆叉树. 且左⼦树和右⼦树的深度之差的绝对值不超过1; 我们将⼆叉树上结点的左⼦树深度减去右⼦树深度的值称为平衡因⼦BF(Balance Factr)
图1是平衡二叉树，图2都不是二叉排序树了更不是平衡二叉树了(58<59)。
图3不是平衡二叉树，在58的节点它的左子树的高度是3，它的右子树的高度是0，它的BF就是两者相减的绝对值等于3。而平衡二叉树的BF不能超过1。
BF = | 左子树高度 - 右子树高度 | // BF <= 1
图4是平衡二叉树。
在平衡二叉树中查找/删除是和二叉排序树一样的，不同在于插入。把一个个节点设计成平衡二叉树才是最难的；
在设计一个平衡二叉树的时候，一定要找到最小不平衡子树。
最小不平衡子树：距离插⼊点最近的,且平衡因⼦BF绝对值⼤于1的结点为根的⼦树,我们称为最⼩不平衡⼦树。
平衡⼆叉树构建的基本思想: 就是在构建⼆叉排序树的过程中, 每当插⼊⼀个结点时,先检查是否因插⼊⽽破坏了树的平衡性. 若是,则找到最⼩不平衡⼦树.在保持⼆叉排序树特性的前提下,调整最⼩不平衡⼦树中各结点之间的链接关系.进⾏相应的旋转,使之成为新的平衡⼦树。
数组a[10] = {3,2,1,4,5,6,7,10,9,8}
- 构建⼆叉排序树：
- 构建平衡二叉树
那么如何去构建平衡二叉树呢？下面就来一步步模拟。
（每插入一个节点都需要更新树的节点的BF值。）
BF = | 左子树高度 - 右子树高度 | （BF <= 1）
构建平衡二叉树的原理
图1中当插入到节点1的时候，发现节点3的BF值大于1，所以需要右旋到图2的样式。(节点2与节点1此时都为正数选择右旋)
注意：1.旋转不可以打乱平衡性(出现其中节点的BF值>1)；2.左子树比根节点大或者右子树比根节点小。
图4中插入5节点，出现了BF绝对值>1，则需要找到最小不平衡子树(3/4/5)，进行左旋到图5的样式。（节点3和节点4此时都为负数选择左旋）
为什么要找到最小不平衡子树？是因为根节点2的失衡是节点3的失衡导致的。
图6中插入节点6，导致根节点2失衡，此时整棵树就是最小不平衡树，通过左旋调整，但是节点4本身拥有左子树是节点3，需要更新成节点2，而节点2的右子树调整成节点3。（节点4和节点2都是负数选择左旋）
图8中插入节点7时，会导致节点5的BF绝对值大于1，需要找到需要找到最小不平衡子树(5/6/7)，通过左旋调整成图9的样式。
错误的旋转
图11中插入节点9的时，会导致节点6/节点7的BF绝对值大于1，需要找到需要找到最小不平衡子树(7/10/9)，通过左旋调整成图12的样式；
但是此时节点10/7/9又出现问题了，它不满足二叉排序树的规则(9比10小却成了10的右子树)；出现不满足二叉排序树的规则的原因呢是 节点7此时是负数，而节点10此时是正数，一正一负就会导致违反规则。
此时图12的调整是错误的。
一正一负需要选择双旋：第一次旋转是调整正负统一，第二次旋转是调整平衡。
第一次旋转：
对节点10和节点9进行一次右旋，得到图13的样式。
第二次旋转：
图13中此时节点7和节点9的符号是一样的，都是负数进行左旋操作，得到图14。
图15插入节点8导致，以节点6为根节点的最小不平衡子树，由于节点6和节点9此时又是一正一负的情况，需要进行双选调整：
图15第一次需要旋转的部分，图16第二次需要旋转的部分，最终得到图17.
平衡二叉树的实现
- 1.平衡二叉树的数据结构
//⼆叉树的⼆叉链表结点结构定义
//结点结构
typedef struct BiTNode{
//结点数据
int data;
//结点的平衡因⼦
int bf;
//结点左右孩⼦指针
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
- 2.右旋操作
- P做为右旋的根结点;
- L的右⼦树 成为了 P的左⼦树;
- P成为了L 的右⼦树;
- L 替换了P,成为⼆叉排序树新的根结点
右旋
//1.右旋
/*
对以p为根的二叉排序树作右旋处理;
处理之后p指向新的树根结点,即旋转处理之前的左子树的根结点;
*/
void R_Rotate(BiTree *p){
BiTree L;
//① L是p的左子树;
L = (*p)->lchild;
//② L的右子树作为p的左子树
(*p)->lchild = L->rchild;
//③ 将p作为L的右子树
L->rchild = (*p);
//④ 将L替换原有p的根结点位置
*p = L;
}
- 3.左旋操作
- P做为左旋的根结点;
- R的左⼦树 成为了 P的右⼦树;
- P成为了R 的左⼦树;
- R 替换了P,成为⼆叉排序树新的根结点
左旋
/*
2.左旋
对以P为根的二叉排序树作左旋处理
处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点
*/
void L_Rotate(BiTree *p){
BiTree R;
//① R是p的右子树
R = (*p)->rchild;
//② R的左子树作为R的右子树
(*p)->rchild = R->lchild;
//③ 将p作为R的左子树;
R->lchild = (*p);
//④ 将R替换原有p的根结点的位置
*p = R;
}
- 4.左⼦树失衡
用于判断失衡的常量
#define LH +1 /* 左⾼，需要右旋 */
#define EH 0 /* 等⾼ */
#define RH -1 /* 右⾼，需要左旋 */
- 4.1 左子树失衡 右旋
1.判断T的BF值与L的BF值是否是同符号;
2.将T的BF值与L的BF值更新为平衡后的BF值.等于0;
3.将最⼩不平衡⼦树T进⾏右旋
左子树失衡需要右旋
- 4.2 左子树失衡 双旋
插入前的树（其它没有用到的节点没画出来）
插入后的树（其它没有用到的节点没画出来）需要左旋统一符号
- 判断T的BF值与L的BF值是否是同符合;
根结点T为正(LH),
左⼦树L为负(RH).
所以要进⾏双旋处理; - 获取左⼦树L的右⼦树Lr;
Lr的BF值为正(LH) - 修改T与左孩⼦L的BF值,⽬的是将符号改为⼀致;
• 如果Lr.BF为LH(正)时,则将根结点T的BF值改为RH,且L的BF值改为EH;
• 如果Lr.BF为EH(0)时,则将根结点T与左⼦树L的BF值都改为EH;
• 如果Lr.BF为RH(负)时,则将根结点T的BF值改为EH,左⼦树L改为LH;
- 将Lr的BF值改为EH(0);
- 对T的左⼦树进⾏左旋处理;
- 对T做右旋处理.
#define LH +1 /* 左高 */
#define EH 0 /* 等高 */
#define RH -1 /* 右高 */
/*
3. 对指针T所指结点为根的二叉树作左平衡旋转处理,算法结束后,指针T指向平衡处理后新的根结点
*/
void LeftBalance(BiTree *T)
{
BiTree L,Lr;
//1.L指向T的左子树根结点
L=(*T)->lchild;
//2.检查T的左子树的平衡度，并作相应平衡处理
switch(L->bf)
{
//① 新结点插入在T的左孩子的左子树上，要作单右旋处理(如图1-平衡二叉树右旋解释图)
case LH:
//L的平衡因子为LH,即为1时,表示它与根结点BF符合相同,则将它们(T,L)的BF值都改为EH(0)
(*T)->bf=L->bf=EH;
//对最小不平衡子树T进行右旋;
R_Rotate(T);
break;
//② LH的平衡因子为RH(-1)时,它与跟结点的BF值符合相反.此时需要做双旋处理(2次旋转处理)
// 新结点插入在T的左孩子的右子树上，要作 双旋处理
case RH:
//Lr指向T的左孩子的右子树根
Lr=L->rchild;
//修改T及其左孩子的平衡因子
switch(Lr->bf)
{
case LH:
(*T)->bf=RH;
L->bf=EH;
break;
case EH:
(*T)->bf=L->bf=EH;
break;
case RH:
(*T)->bf=EH;
L->bf=LH;
break;
}
Lr->bf=EH;
//对T的左子树作左旋平衡处理
L_Rotate(&(*T)->lchild);
//对T作右旋平衡处理
R_Rotate(T);
}
}
- 5.右子树失衡
用于判断失衡的常量
#define LH +1 /* 左⾼，需要右旋 */
#define EH 0 /* 等⾼ */
#define RH -1 /* 右⾼，需要左旋 */
- 5.1 右子树失衡 左旋
- 判断最⼩不平衡⼦树T的BF值与根结点T的右⼦树R的BF值符合是否⼀致( 都为负数 )
- 将T的BF值与R的BF值更新为平衡后的BF值.等于0;
- 将最⼩不平衡子树T进行左旋
- 5.2 右子树失衡 双旋
- 判断T的BF值与R 的BF值是否是同符合;
根结点T为负(RH),
左⼦树R为正(LH).
所以要进⾏双旋处理; - 获取右⼦树R的左⼦树RL;
RL的BF值为正(EH) - 修改T与右孩⼦R的BF值,⽬的是将符号改为⼀致;
• 如果RL.BF为RH(负)时,则将根结点T的BF值改为LH,且R的BF值改为EH;
• 如果RL.BF为EH(0)时,则将根结点T与左⼦树R的BF值都改为EH;
• 如果RL.BF为LH(正)时,则将根结点T的BF值改为EH,右⼦树R改为RH;
- 将RL的BF值改为EH(0);
- 对T的右⼦树进⾏右旋处理;
- 对T做左旋处
/*
4. 右平衡树失衡处理
对以指针T所指结点为根的二叉树作右平衡旋转处理
本算法结束时，指针T指向新的根结点
*/
void RightBalance(BiTree *T)
{
BiTree R,Rl;
//1.R指向T的右子树根结点
R=(*T)->rchild;
//2. 检查T的右子树的平衡度，并作相应平衡处理
switch(R->bf)
{
//① 新结点插入在T的右孩子的右子树上，要作单左旋处理
case RH:
(*T)->bf=R->bf=EH;
L_Rotate(T);
break;
//新结点插入在T的右孩子的左子树上，要作双旋处理
case LH:
//Rl指向T的右孩子的左子树根
Rl=R->lchild;
//修改T及其右孩子的平衡因子
switch(Rl->bf)
{
case RH:
(*T)->bf=LH;
R->bf=EH;
break;
case EH:
(*T)->bf=R->bf=EH;
break;
case LH:
(*T)->bf=EH;
R->bf=RH;
break;
}
Rl->bf=EH;
//对T的右子树作右旋平衡处理
R_Rotate(&(*T)->rchild);
//对T作左旋平衡处理
L_Rotate(T);
}
}
- 6.平衡二叉树的插入实现
若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否
思路:
- 如果T为空时,则创建一个新结点;
- 如果T不为空,判断是否存在相同的结点.如果二叉树中存在相同结点,则不需要插入;
- 如果新结点值e小于T的根结点值,则在T的左子树查找;
- 如果能在左子树中查找到,则不插入进去.返回False; 如果没有找到,则插入
- 插入成功taller为TRUE,说明新结点e已经插入进去; 此时需要判断T的平衡因子;
- 如果平衡因子是1,则说明左子树高于右子树,那么需要调用leftBalance进行左平衡旋转处理;
- 如果为0或者-1,则说明新插入的结点没有让整颗二叉排序树失去平衡性,只需要修改BF值即可;
- 如果新结点值e大于T的根结点值,则在T的右子树查找;
- 如果能在右子树中查找到,则不插入进去.返回False; 如果没有找到,则插入
- 插入成功taller为TRUE,说明新结点e已经插入进去; 此时需要判断T的平衡因子;
- 如果平衡因子是-1,则说明右子树高于左子树,那么需要调用RightBalance进行右平衡旋转处理;
- 如果为0或者1,则说明新插入的结点没有让整颗二叉排序树失去平衡性,只需要修改BF值即可;
Status InsertAVL(BiTree *T,int e,Status *taller)
{
if(!*T)
{ //1.插入新结点，树“长高”，置taller为TRUE
//① 开辟一个新结点T;
*T=(BiTree)malloc(sizeof(BiTNode));
//② 对新结点T的data赋值,并且让其左右孩子指向为空,T的BF值为EH;
(*T)->data=e;
(*T)->lchild=(*T)->rchild=NULL;
(*T)->bf=EH;
//③ 新结点默认"长高"
*taller=TRUE;
}
else
{
if (e==(*T)->data)
{ //2.树中已存在和e有相同关键字的结点则不再插入
*taller=FALSE;
return FALSE;
}
if (e<(*T)->data)
{
//3.应继续在T的左子树中进行搜索
if(!InsertAVL(&(*T)->lchild,e,taller))
//未插入
return FALSE;
//4.已插入到T的左子树中且左子树“长高”
if(*taller)
//5.检查T的平衡度
switch((*T)->bf)
{
case LH:
//原本左子树比右子树高，需要作左平衡处理
LeftBalance(T);
*taller=FALSE;
break;
case EH:
//原本左、右子树等高，现因左子树增高而使树增高
(*T)->bf=LH;
*taller=TRUE;
break;
case RH:
//原本右子树比左子树高，现左、右子树等高
(*T)->bf=EH;
*taller=FALSE;
break;
}
}
else
{ //6.应继续在T的右子树中进行搜索
//未插入
if(!InsertAVL(&(*T)->rchild,e,taller))
return FALSE;
//已插入到T的右子树且右子树“长高”
if(*taller)
// 检查T的平衡度
switch((*T)->bf)
{
//原本左子树比右子树高，现左、右子树等高
case LH:
(*T)->bf=EH;
*taller=FALSE;
break;
//原本左、右子树等高，现因右子树增高而使树增高
case EH:
(*T)->bf=RH;
*taller=TRUE;
break;
// 原本右子树比左子树高，需要作右平衡处理
case RH:
RightBalance(T);
*taller=FALSE;
break;
}
}
}
return TRUE;
}
- 6.平衡二叉树的查找实现
/*6.二叉排序树查找*/
Status SearchBST(BiTree T,int key,BiTree f, BiTree *p){
if (!T) /* 查找不成功 */
{
*p = f;
return FALSE;
}
else if (key==T->data) /* 查找成功 */
{
*p = T;
return TRUE;
}
else if (key<T->data)
return SearchBST(T->lchild, key, T, p); /* 在左子树中继续查找 */
else
return SearchBST(T->rchild, key, T, p); /* 在右子树中继续查找 */
}
- 7.平衡二叉树的测试代码
int main(int argc, const char * argv[]) {
// insert code here...
printf("平衡二叉树 !\n");
int i;
int a[10]={3,2,1,4,5,6,7,10,9,8};
//调整数组的顺序,最终生成的平衡二叉树高度是一样的.
//int a[10]={8,9,1,4,5,6,7,10,2,3};
//int a[10]={9,4,1,2,7,6,5,10,3,8};
BiTree T=NULL;
Status taller;
int sum = 0;
for(i=0;i<10;i++)
{
InsertAVL(&T,a[i],&taller);
sum += taller;
printf("插入%d,是否增加树的高度(%d)[YES->1 / NO->0]\n",a[i],taller);
}
printf("将数组a插入到平衡二叉树后,最终形成高度为%d的平衡二叉树\n",sum);
BiTree p;
int statusValue = SearchBST(T, 10, NULL, &p);
printf("查找%d是否成功:%d (1->YES/0->NO)\n",p->data,statusValue);
return 0;
}
四、散列表查找
散列技术是记录的存储位置和它的关键字之间建⽴⼀个确定的对应关系f，使得每个关键字key对应⼀个存储位置f(key)。 查找时根据这个对应关系找到给定值key的映射f(key)。若查找集合中存在这个记录，则必定在f(key)的位置上。（不需要像前面的查找方式一样从头遍历。）
注意：哈希是一种思想，不是固定的一种算法。是根据不同的需求去设计算法。
// f：散列函数（哈希函数）
// key：要查找的关键字
存储位置 = f(key)
1.存储时，通过散列函数计算并记录散列地址；
2.查找时，key通过散列函数计算得到散列地址，再从散列地址中获取查找的东西。
设计散列表原则：1.简单；2.均匀；3.存储利用率高；4.不会容易产生冲突。
设计散列函数的方法：1.直接定址法；2.数字分析法；3.平方取中法；4.折叠法；5.除留余数法；6.随机数法
如何取舍设计一个哈希函数？需要考虑什么？
1.计算公式花费时间
2.关键字长度;
3.散列表⼤⼩
4.关键字分布情况
5.记录查找概率
1.直接定址法
比如说我有一张这样的表格，要根据年龄去查人数，此时的f(key)中的key就是年龄，通过f(key)直接查到那条记录。再比如说通过出生年份去查人数，可以优化成 f(key-1980)得到那条记录。
f(key) = a * key + b (a,b为常数);
直接定址法缺点：预先知道关键字的分布情况；查找的表小且连续；适合定向查找。
2.数字分析法
分析数字相同的特性，从特性中找到一个个散列的地址分布。
像我们这样的手机号码我们不能全都存起来，可以通过key是一串数字设计一个散列函数让这些数字变得更小，进行地址的存储。
3.平方取中法
key是一串数字，对数字进行平方计算，得到的结果里去中间位。
4.折叠法
折叠法就是将关键字从左到右分割成位数相等的⼏部分(注意最后⼀部分位数不够可以稍微短些); 然后将⼏部分叠加求和,并按散列表表⻓,取后⼏位作为散列地址。
得到962就是存储上面一串数字的地址，查找时不再需要从一串数字从头查到尾，而是直接通过962就可以获取。
5.除留余数法
f(key) = key mod p ( p <= m )
比较常用，但是这种方法容易产生哈希冲突。
比如此时p是12，要存储key= 24 / 36 / 48 这些数。f(key)的结果都是为0，但0的位置只能存储一个数字，此时就是哈希冲突。下面会讲到如何解决哈希冲突。
6.随机数法
f(key) = random(key)
解决哈希冲突
任何一种哈希算法都会有可能会出现哈希冲突。
解决哈希冲突方法：1.开放定址法
- 1.开放定址法（线性探索法）
开放定址法就是⼀旦发⽣了冲突,就去寻找下⼀个空的散列地址.只有散列表⾜够⼤,空的散列地址总能找到,并将记录存⼊。
开放定址法公式
注意：开放定址法公式不是必须也不是一定是这样的。思想就是当我发生冲突的时候，我去开放一个开放定址法公式，在原有基础上再设计一个散列可以重新定位一个地址。
举例：
如果你觉得开放定址法依旧容易产生冲突，那就可以把公式变得更复杂，di是变化的：
- 2.再散列函数法
对于散列表来说, 我们事先准备多个散列函数：
这样能降低冲突。
- 3.链地址法
发生冲突后，将所有的关键字为同义词的记录存储在⼀个单链表中,我们称为这种同义词⼦表. 在散列表中只存储所有同义词⼦表的头指针(头地址).
- 4.公共溢出法
这种方式很低效。
代码展示散列表查找
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
typedef int Status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 //存储空间初始分配量
#define SUCCESS 1
#define UNSUCCESS 0
//定义散列表长为数组的长度
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct
{
//数据元素存储基址，动态分配数组
int *elem;
//当前数据元素个数
int count;
}HashTable;
int m=0; /* 散列表表长，全局变量 */
//1.初始化散列表
Status InitHashTable(HashTable *H)
{
int i;
//① 设置H.count初始值; 并且开辟m个空间
m=HASHSIZE;
H->count=m;
H->elem=(int *)malloc(m*sizeof(int));
//② 为H.elem[i] 动态数组中的数据置空(-32768)
for(i=0;i<m;i++)
H->elem[i]=NULLKEY;
return OK;
}
//2. 散列函数
int Hash(int key)
{
//除留余数法
return key % m;
}
//3. 插入关键字进散列表
void InsertHash(HashTable *H,int key)
{
//① 求散列地址
int addr = Hash(key);
//② 如果不为空，则冲突
while (H->elem[addr] != NULLKEY)
{
//开放定址法的线性探测
addr = (addr+1) % m;
}
//③ 直到有空位后插入关键字
H->elem[addr] = key;
}
//4. 散列表查找关键字
Status SearchHash(HashTable H,int key,int *addr)
{
//① 求散列地址
*addr = Hash(key);
//② 如果不为空，则冲突
while(H.elem[*addr] != key)
{
//③ 开放定址法的线性探测
*addr = (*addr+1) % m;
//④H.elem[*addr] 等于初始值或者循环有回到了原点.则表示关键字不存在;
if (H.elem[*addr] == NULLKEY || *addr == Hash(key))
//则说明关键字不存在
return UNSUCCESS;
}
return SUCCESS;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};
int i,p,key,result;
HashTable H;
//1.初始化散列表
InitHashTable(&H);
//2.向散列表中插入数据
for(i=0;i<m;i++)
InsertHash(&H,arr[i]);
//3.在散列表查找key=39
key=39;
result=SearchHash(H,key,&p);
if (result)
printf("查找 %d 的地址为：%d \n",key,p);
else
printf("查找 %d 失败。\n",key);
//4.将数组中的key,打印出所有在散列表的存储地址
for(i=0;i<m;i++)
{
key=arr[i];
SearchHash(H,key,&p);
printf("查找 %d 的地址为：%d \n",key,p);
}
return 0;
}
网友评论