查找表: 由同一类型的数据元素(记录)组成的集合。
记作: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 二分查找

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

3 索引顺序表

查找效率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所在的域:这就和第二个删除一样的
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 = 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给出了一个更加直接的结论,可以下载文档查看:

代码:

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月15日