大话数据结构-8.查找（上）

大家好，欢迎来到IT知识分享网。

8.1 顺序表查找（线性表）

8.2.1 折半查找

中间值取值为：$$mid=\frac{low+high}{2}=low+\frac{1}{2}(high-low)$$

8.2.2 插值查找

中间值取值为：$$mid=low+\frac{key-a[low]}{a[high]-a[low]}(high-low)$$

8.2.3 斐波那契查找

/*斐波那契查找*/ int Fibonacci_Search(int *a,int n,int key) { 
    int low,high,mid,i,k; low = 1; /*定义最低下标为记录首位*/ high = n; /*定义最高下标为记录末位*/ k = 0; while (n>F[k]-1) /*计算n位于斐波那契数列的位置*/ k++; for (i=n;i<F[k]-1;i++) /*将不满的数值补全*/ a[i] = a[n]; while (low<=high) { 
    mid = low + F[k-1]-1; /*计算当前分隔的下标*/ if (key<a[mid]) /*若查找记录小于当前分隔记录*/ { 
    high = mid-1; /*最高下标调整到分隔校标mid-1处*/ k = k-1; /*斐波那契数列下标减1位*/ } else if (key>a[mid]) /*若查找记录大于当前分隔记录*/ { 
    low = mid+1; /*最低下标调整到分隔下标mid+1处*/ k= k-2; /*斐波那契数列下标减2位*/ } else { 
    if (mid <= n) return mid; /*若相等则说明mid即为查找到的位置*/ else return n; /*若mid>n说明是补全数值，返回n*/ } } return 0; } 

• 为什么当key>a[mid]$时，k = k-2 ?

1.k为斐波那契数列元素下标，F[k]为待查数组元素下标； 2.理解'F[k]-1'中为什么要'-1'： 每个F[k]都是分割点，通过减1将分割点排除。 3.理解'F[k]-1=(F[k-1]-1)+(F[k-2]-1)+1'; 4.理解'k=k-2'： key值大于分割点，意味着可以分布在'F[k-2]-1'的区域，见下图。 5.理解'mid=low+F[k-1]-1'； 

• 斐波那契查找算法核心在于：
  1. 当key= a[mid]时，查找成功；
  2. 当key<a[mid]时，新范围是第low个到mid-1个，此时范围内个数为F[k-1]-1个；
  3. 当key>a[mid]时，新范围是第mid+1个到high个，此时范围内个数为F[k-2]-1个；
• 与折半查找、插值查找比较：
  1. 时间复杂度均为O[logn]，但平均性能优于折半。但极端情况如key=1，斐波那契查找始终处于左侧长半区查找，效率低于折半。
  2. 折半使用加法和除法运算$mid=\frac{low+high}{2}$，插值使用四则运算$mid=low+\frac{[key-a[low]]}{a[high]-a[low]}\times (high-low)$。斐波那契查找则仅使用加减法，海量查找时很有优势。

8.3线性索引查找

8.4 二叉排序树

8.4.1 二叉排序树结构

/*二叉树的二叉链表结点结构定义*/ type struct BiTNode /*结点结构*/ { 
    int data; /*结点数据*/ struct BiTNode *lchild,*rchild; /*左右孩子指针*/ } BiTNode,*BiTree; 

8.4.2 查找

/*递归查找二叉排序树T中是否存在key，*/ /*指针f指向T的双亲，其初始调用值为NULL*/ /*若查找成功，则指针p指向该数据元素结点，并返回TRUE*/ /*否则指针p指向查找路径上访问的最后一个结点并返回FALSE*/ Status SearchBST(BiTree T,int key,BiTree f, BiTree *p) { 
    if (!T) /*查找不成功的2种情况：一是空树；二是递归至叶子节点的下一级为空，返回双亲结点即叶子结点*/ { 
    *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); /*在右子树继续查找*/ } 

• 理解4个参数：

1. 指针T指向二叉树根结点，代表要查询的整棵二叉树； 2. key为查询值； 3. 指针f指向当前结点的双亲节点。因根结点没有双亲，f初始为NULL； 4. 指针p匹配成功指向目标结点，不成功指向双亲结点。 

8.4.3 插入

/*当二叉排序树T中不存在关键字等于key的数据元素时，*/ /*插入key并返回TRUE，否则返回FALSE*/ Status InsertBST (BiTree *T,int key) { 
    BiTree p,s; if (!SearchBST(*T,key,NULL,&p)) /*查找不成功*/ { 
    s = (BiTree)malloc(sizeof(BiTNode)); s->data=key; s->lchild = s->rchild= NULL; if(!p) /*T为空树*/ *T = s; /*插入s为新的根结点*/ else if (key<p->data) p->lchild = s; /*插入s为左孩子*/ else p->rchild = s; /*插入s为右孩子*/ } else return FALSE; /*树中已有关键字相同的结点，不再插入*/ } 

• 理解代码中的’&p’、’!p’和p的位置

1. &运算符用于获取变量的地址，通过传递变量的地址，可以在函数内部修改该变量的值； p值通过searchBST函数获取：找到返回匹配结点，找不到则返回最后搜索位置的双亲结点； 2. !p表示最后搜索位置的双亲结点为空，即该二叉排序树为空树； 3. p的位置：SearchBST查找函数的作用是，无论T是否存在key，将key应该出现的位置赋值给p。 

• 创建二叉排序树

/*尝试在脑中形成代码执行过程动画*/ 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]); } 

8.4.4 删除

/*若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点，*/ /*并返回TRUE；否则返回FALSE */ Status DeleteBST(BiTree *T,int key) { 
    if (!*T) /*不存在关键字等于key的数据元素*/ return FALSE; else { 
    if（key==（*T）->data) /*找到关键字等于key的数据元素*/ return Delete(T); else if (key<(*T)->data) return DeleteBST (&(*T)->lchild,key) else return DeleteBST (&(*T)->rchild,key) } } 

/*从二叉排序树中删除结点p，并重接它的左或右子树*/ Status Delete(BiTree *p) { 
    BiTree q,s; if((*p)->rchild==NULL) /*右子树空则只需重接它的左子树*/ { 
    q = *p; *p= (*p)->lchild; free(q); } else if ((*p)->lchild==NULL) /*只需重接它的右子树*/ { 
    q = *p; *p= (*p)->rchild; free(q); } else /*左右子树均不为空*/ { 
    q = *p; s = (*p)->lchild; /*转左，*/ while(s->rchild) /*然后向右到尽头（找待删结点的前驱）*/ { 
    q=s; s=s->rchild; } (*p)->data = s->data; /*s指向被删除的直接前驱*/ if (q!=*p) /*路径向左再向右，q指向p的子树*/ q->rchild = s->lchild; /*重接q的右子树*/ else /*路径向左没有再向右，q和p指向同一结点*/ q->lchild = s->lchild; /*重接q的左子树*/ free(s); } return TRUE; } 

8.4.5 总结

• 二叉排序树的形状，因数组中元素顺序不同而不同；
• 形状不同的二叉排序树，时间复杂度也不一致，如图：
  
  
• 平衡二叉排序树复杂度为 O[ logn]，斜树复杂度为 O[n]

8.5 平衡二叉树（基础为二叉排序树）

8.5.1 概念

• 平衡二叉树：在二叉排序树的基础上，保证每一个结点的左子树和右子树的高度差至多等于1。
• 平衡因子F：二叉树上结点的左子树深度减去右子树深度的值。
• 最小不平衡子树：距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树。

8.5.2 实现原理

1. 出现不平衡时，在保证二叉排序树的前提下，通过旋转最小不平衡树恢复平衡；
2. 平衡因子为正时顺时针旋转，为负时逆时针旋转；
3. 旋转最小不平衡树前，需要先确保其子树平衡因子F与根结点正负一致。如果不一致，通过旋转子树使其一致。

8.5.3 算法实现（简单了解，不以本书为准）

/*二叉树的二叉链表结点结构定义*/ typedef struct BiTNode /*结点结构*/ { 
    int data; /*结点数据*/ int bf ; /*结点平衡因子*/ struct BiTNode *lchild, *rchild; /*左右孩子指针*/ } BiTNode, *BiTree; 

/*对以p为根的二叉排序树作右旋处理，*/ /*处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */ void R_Rotate(BiTree *P) { 
    BiTree L; L=(*P)->1child; /* L指向P的左子树根结点*/ (*P)->lchild=L->rchild;L->rchild-(*P); /*L的右子树挂接为P的左子树*/ *p=L; /*P指向新的根结点 */ } 

/*对以P为根的二叉排序树作左旋处理，*/ /*处理之后卫指向新的树根结点，即旋转处理之前的右子树的根结点0 */ void L_Rotate (BiTree *P) { 
    BiTreeR; R=(*P)->rchild; /*R指向P的右子树根结点 */ (*P)->rchild=R->lchild; /*R的左子树挂接为P的右子树 */ R->lchild=(*P): *P=R; /*P指向新的根结点*/ } 

#define LH +1 /*左高*/ #define EH 0 /*等高*/ #define RH -1 /*右高*/ /*对以指针T所指结点为根的二叉树作左平衡旋转处理*/ /*本算法结束时，指针T指向新的根结点 */ void LeftBalance(BiTree *T) { 
    BiTree L,Lr; L=(*T)->lchild;/* L指向的左子树根结点 */ switch(L->bf) { 
   /* 检查T的左子树的平衡度，并作相应平衡处理 */ case LH:/*新结点插入在T的左孩子的左子树上，要作单右旋处理 */ (*T)->bf=L->bf=EH; R Rotate(T); break; case RH: /*新结点插入在T的左孩子的右子树上，要作双旋处理 */ Lr=L->rchild;/*Lr指向T的左孩子的右子树根 */ switch(Lr->bf)/* 修改T及其左孩子的平衡因子 */ { 
    难 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; LRotate(G(*T)->lchild);/*对T的左子树作左旋平衡处理*/ R_Rotate(T);/*对作右旋平衡处理 */ } } 

• 调整原则：插入新节点后，从下往上的第一个|BiTree->bf|>1的结点，为旋转的根结点