前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构–查找专题

数据结构–查找专题

作者头像
用户7267083
发布2022-12-08 14:04:43
4620
发布2022-12-08 14:04:43
举报
文章被收录于专栏:sukuna的博客

数据结构–查找专题

于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计算:每一个结点所在的层数求和/总的结点个数 满二叉树:公式:

\frac{n+1}{n}log_2(n+1)-1
\frac{n+1}{n}log_2(n+1)-1
3 索引顺序表

查找效率

O(b+s)
O(b+s)

● 条件 (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:ZJU

ASL: 最好情况(为满二叉树) ASL=

\frac{n+1}{n}log2(n+1)-1
\frac{n+1}{n}log2(n+1)-1

= 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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020年11月9日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 数据结构–查找专题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档