数据结构–查找专题
于2020年11月9日2020年11月9日由Sukuna发布
查找表: 由同一类型的数据元素（记录）组成的集合。 记作：ST={a1,a2,…,an} ● 关键字: 可以标识一个记录的数据项 ● 主关键字: 可以唯一地标识一个记录的数据项 ● 次关键字: 可以识别若干记录的数据项
查找—-根据给定的某个关键字值，在查找表中确定一个其关键字等于给定值的记录或数据元素。 设k为给定的一个关键字值，R[1..n]为n个记录的表,若存在R[i].key=k,1≤i≤n,称查找成功；否则称查找失败。
静态查找: 查询某个特定的元素，检查某个特定的数据元素的属性,不插入新元素或删除元素(记录) 。 动态查找: 在查找过程中，同时插入查找表中不存在的数据元素(记录)。
1 顺序查找
typedef struct node { keytype key ； //关键字类型 char name[6]； //姓名 …… //其它 } ElemType； typedef struct { ElemType elem[maxsize 1]；//maxsize 1个记录, //elem[0]为监视哨 int length; } SSTable; SSTable ST1,ST2;
不使用监视哨的判断语句:i>=1 && k!=ST.elem[i].key 监视哨:将数组第0个元素设置为要查找的元素 含有监视哨的查找表是肯定能找到的,如果在0找到就是没找到,就符合相等的直接返回下标即可
查找算法的性能分析:
● 考虑查找失败: 使用监视哨elem[0],为 n 1 不使用监视哨elem[0],为 n
假定查找成功和失败的机会相同，对每个记录的查找概率相等， Pi=1/(2*n), 则 ASL=3(n 1)/4
2 二分查找
代码语言：javascript复制int binsrch(SSTable ST,keytype k)
{
int low,mid,hig；
low=1；
hig=ST.length；
while (low<=hig)
{ mid=(low hig)/2； //计算中间记录的地址
if (k<ST.elem[mid].key)
hig=mid-1； //查左子表
else if (k==ST.elem[mid].key)
return mid； //查找成功,退出循环
else low=mid 1； //查右子表
｝
return 0;小了,往小了猜,大了,往大了猜
判定树
如果判定树只有一个儿子,那这个儿子一定是右儿子
插入方法:右子树最右,左子树最右,递归排序 ASL计算:每一个结点所在的层数求和/总的结点个数 满二叉树:公式:
3 索引顺序表
查找效率
● 条件 (1)分块表”按块有序”, 索引表”按key有序” (2)设n个记录分为b个块，每块的记录数s=n/b ● 查找方法 (1)顺序查找(或折半查找)索引表 确定k值所在的块号或块的首地址 (2)在某一块中顺序查找 ● 最佳分块 s=√n b=√n
4 二叉排序树
(1) 二叉排序树的定义 如果二叉树的任一结点大于其非空左子树的所有结点，而小于其非空右子树的所有结点，则这棵二叉树称为二叉排序树。对一棵二叉排序树进行中序遍历，所得的结点序列一定是递增有序的。
小的往左走,大的往右走,遇到NULL就插入
ASL计算:同查找树 存储结构:跟二叉树一样
查找算法:大的往右,小的往左,找到了返回,遇到NULL就失败
插入算法:
删除算法:在二叉排序树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会失去。 为保证在删除节点后二叉排序树的性质不会丢失: 1、删除叶结点，只需将其双亲结点指向它的指针置空，再释放它即可。 2、被删结点缺左子树（或右子树），可以用被删节点的右子树（或左子树）顶替它的位置，再释放它。 3、被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点(关键值最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。 这个中序下的第一个结点就是右子树最左,交换结点域之后删除右子树最左的地方
找到右子树最左:78,然后78和81值域交换,删除原来78所在的域:这就和第二个删除一样的
代码语言：javascript复制BinTree Insert( BinTree BST, ElementType X )
{
if( !BST ){ /* 若原树为空，生成并返回一个结点的二叉搜索树 */
BST = (BinTree)malloc(sizeof(struct TNode));
BST->Data = X;
BST->Left = BST->Right = NULL;
}
else { /* 开始找要插入元素的位置 */
if( X < BST->Data )
BST->Left = Insert( BST->Left, X ); /*递归插入左子树*/
else if( X > BST->Data )
BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/
/* else X已经存在，什么都不做 */
}
return BST;
}
BinTree Delete( BinTree BST, ElementType X )
{
Position Tmp;
if( !BST )
printf("要删除的元素未找到");
else {
if( X < BST->Data )
BST->Left = Delete( BST->Left, X ); /* 从左子树递归删除 */
else if( X > BST->Data )
BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
else { /* BST就是要删除的结点 */
/* 如果被删除结点有左右两个子结点 */
if( BST->Left && BST->Right ) {
/* 从右子树中找最小的元素填充删除结点 */
Tmp = FindMin( BST->Right );
BST->Data = Tmp->Data;
/* 从右子树中删除最小元素 */
BST->Right = Delete( BST->Right, BST->Data );
}
else { /* 被删除结点有一个或无子结点 */
Tmp = BST;
if( !BST->Left ) /* 只有右孩子或无子结点 */
BST = BST->Right;
else /* 只有左孩子 */
BST = BST->Left;
free( Tmp );
}
}
}
return BST;
}
Source:ZJUASL: 最好情况(为满二叉树） ASL=
= O(log2 n) 最坏情况(为单枝树): ASL=(1 2 … n)/n=(n 1)/2 平均值: ASL≈O(log2 n)
5 平衡二叉树(AVL树)
AVL树：由G.M.Adelson-Velskii和E.M.Landis提出。 结点的平衡因子：结点的左右子树的深度之差。 平衡二叉树：任意结点的平衡因子的绝对值小于等于1的二叉树。 存储类型: typedef int DataType; //结点数据类型 typedef struct node { //AVL树结点定义 DataType data; //结点数据域 int balance; //结点平衡因子域 struct node *leftChild, *rightChild; //结点左、右子树指针域 } AVLNode; typedef AVLNode * AVLTree; //AVL树
如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。 如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转, 其中一个是另一 个的镜像，其方向与不平衡的形状相关。 如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。
我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的右边的右边,就需要做左单旋转
往右的直线:做左单旋转,C的左子树变成A的右子树
我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的左边的左边,就需要做右单旋转
往左的直线:做右单旋转,B的右子树变成A的左子树
需要变换的子树都是含有麻烦结点子树的兄弟 我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的左边的右边,就需要做左右旋转
先对BEG做一次左单旋转
在对AEB做一次右单旋转
我们看:不平衡的发现者是A,麻烦结点(让A发现不平衡的结点)在A的右边的左边,就需要做右左旋转
先对CDF做一次右单旋转
在对ADC做一次左单旋转
ZJU给出了一个更加直接的结论,可以下载文档查看:
代码:
代码语言：javascript复制typedef struct AVLNode *Position;
typedef Position AVLTree; /* AVL树类型 */
struct AVLNode{
ElementType Data; /* 结点数据 */
AVLTree Left; /* 指向左子树 */
AVLTree Right; /* 指向右子树 */
int Height; /* 树高 */
};
int Max ( int a, int b )
{
return a > b ? a : b;
}
AVLTree SingleLeftRotation ( AVLTree A )
{ /* 注意：A必须有一个左子结点B */
/* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */
AVLTree B = A->Left;
A->Left = B->Right;
B->Right = A;
A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) 1;
B->Height = Max( GetHeight(B->Left), A->Height ) 1;
return B;
}
AVLTree DoubleLeftRightRotation ( AVLTree A )
{ /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
/* 将A、B与C做两次单旋，返回新的根结点C */
/* 将B与C做右单旋，C被返回 */
A->Left = SingleRightRotation(A->Left);
/* 将A与C做左单旋，C被返回 */
return SingleLeftRotation(A);
}
/*************************************/
/* 对称的右单旋与右-左双旋请自己实现 */
/*************************************/
AVLTree Insert( AVLTree T, ElementType X )
{ /* 将X插入AVL树T中，并且返回调整后的AVL树 */
if ( !T ) { /* 若插入空树，则新建包含一个结点的树 */
T = (AVLTree)malloc(sizeof(struct AVLNode));
T->Data = X;
T->Height = 0;
T->Left = T->Right = NULL;
} /* if (插入空树) 结束 */
else if ( X < T->Data ) {
/* 插入T的左子树 */
T->Left = Insert( T->Left, X);
/* 如果需要左旋 */
if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
if ( X < T->Left->Data )
T = SingleLeftRotation(T); /* 左单旋 */
else
T = DoubleLeftRightRotation(T); /* 左-右双旋 */
} /* else if (插入左子树) 结束 */
else if ( X > T->Data ) {
/* 插入T的右子树 */
T->Right = Insert( T->Right, X );
/* 如果需要右旋 */
if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
if ( X > T->Right->Data )
T = SingleRightRotation(T); /* 右单旋 */
else
T = DoubleRightLeftRotation(T); /* 右-左双旋 */
} /* else if (插入右子树) 结束 */
/* else X == T->Data，无须插入 */
/* 别忘了更新树高 */
T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) 1;
return T;
}
