作业

7.1 字典与索引

问题1：字典在实际使用中遇到哪些问题？

//不同的值需要的空间大小不同，这样的字典难以采用顺序存储和散列存储。
  不等长元素字典问题

问题2：什么是索引，提出索引的目的是什么？

//为了解决不等长元素字典的表示问题，可以引入一种辅助的结构，称为索引。
    索引实际上就是一个从关键码到地址的转换关系。
    引入索引就可以将包含大量属性信息并且不等长元素的字典的处理，转换成仅仅包含关键码到地址对应关系的索引结构的处理。
    实际上引入索引就是将不等长结点结构转换为等长结点结构。

问题3： 什么是目录表，目录表的提出解决了什么问题？

如果这个字典中，元素的值需要空间的长度不等，可以另外建立一个字典的索引，这个索引通常称为目录表。
//
    目录表的提出可以更方便人们的查找，比如目录表中排好序之后，字典中的元素无论采用哪种排序方式，
    或者不排序，都可以在，目录表中实现二分法检索。
//
    目录表的提出可以便于原数据的操作与处理，不需要移动字典本身，只需完成目录中中的排序，原生数据度更高。

问题4：引入目录表后的字典表示，能否适应动态字典管理的需要，为什么？

可以。引入目录表后，字典原数据不需要作出任何处理，这样插入比较方便，插入之后，目录表中调整数据位置，而不在字典中操作，所以能适应。

问题5： page205倒数四段内容，描述的知识精髓在于？（请仔细体会）

索引的方法不止适用于字典，还适用于多个方面，比如栈和队列也可以适用，这样的话，栈和队列不止可以存储一种数据类型，而是可以存储多种数据类型，
//借用java语言的一个特性就是叫做泛化。

问题6： 索引与散列的相同点，不同点在于？

相同点：都是给出一种从关键码到存储地址的映射方法。
不同点：映射方法不同。
       散列法是通过函数定义，而索引法是通过辅助的索引表解决。

问题7： 密集索引与稀疏索引的定义。

每个索引项如果是对应字典中每一个元素，这种索引称为密集索引。反之，每个索引项对应字典中一组元素，这种索引称为稀疏索引。

    //补充：倒排索引
   比如 索引表a l love math !
       索引表b i love English !
   关键字   记录表
    l        a
    love     a,b
    i        b 
    math     a
    !        a,b
 好处就是可以直接找到记录

7.2 字符树

问题8： 字符树建立字典（索引）的原理。

//假设所有关键码都是一个字符串
   每个结点表示关键码中的一个字符，一个字典中的所有关键码，可以用一个字符树（林）中从根部到其他结点路径对应字符串的集合表示。

问题9： 字符树中如何检索给定关键码。

首先用待查关键码的每一个字符与树林的各个根的字符相比较，然后下一步的检索在前此比较相等的那棵树上进行。用待查关键码的第二个字符与选定的这颗树根的各个子女进行比较，然后再沿着前次比较相等的分支进行下面的检索。直到进行到关键码完全匹配成功，并且字符数中所有结点有指向外部结点（*）的指针，检索成功；或者该层所有结点的字符都与待查关键码
相应位置的字符不同，检索失败。

递归查找

问题10： 存储字符树的常见方法有哪两种？各自是如何实现的。

//双链树 和 多链表示
双链树：
    把字符树转换成对应的二叉树并用左指针和右指针进行存储，叫做双链树。
多链表示：
    如果将字符树中所有字符的信息全部隐藏起来，使用代表各种字符出现的指针指向不同的子字符树，
    整个字符树变换成一颗以指针数组为结点的树，通常称为多链表示，又称trie结构
    trie树

7.3 二叉排序树（重点，难点内容）

7.3 二叉排序树（重点，难点内容）

问题11：什么是二叉排序树？

//二叉排序树也成为二叉搜索树，它是以关键码为结点的二叉树。
如果任一结点的左子树非空，则左子树中的所有结点的关键码小于根节点的关键码；
如果任一结点的右子树非空，则右子树中的所有结点的关键码都大于根节点的关键码。
    
   /** 
       中序遍历会得到一个关键码从小到大的顺序。
   **/

问题12：二叉排序树的存储结构

一般采用二叉树的左子右兄法表示，其存储结构定义如下：

struct BinSearchNode;
typedef struct BinSearchNode *pBinSearchNode;

struct BinSearchNode{
    KeyType KeyValue;
    pBinSearchNode left;
    pBinSearchNode right;
};

typedef struct BinSearchNode* BinSearchTree;  //二叉排序树
typedef BinSearchTree *pBinSearchTree;

问题13：按对称序周游二叉排序树，得到一个什么特点的序列，为什么？

按对称序周游二叉排序树，得到一个所有关键码从小到大排成的序列。因为二叉排序树的性质就是，
如果任一结点的左子树非空，则左子树中的所有结点的关键码小于根节点的关键码；如果任一结点
的右子树非空，则右子树中的所有结点的关键码都大于根节点的关键码。

问题14：二叉排序树的检索及算法7.1（重点&难点）

//二叉排序树的检索算法
int Search(pBinSearchTree ptree,KeyType key,pBinSearchNode *position){
    pBinSearchNode  p,q;
    p=*ptree;
    q=p;
    while (p!= nullptr){
        q=p;
        if(p->KeyValue=key){
            *position=p;
            return 1;
        }
        else if(p->KeyValue>key)
            p=p->left;
        else
            p=p->right;
        *position=q;       //返回原位置  好插入元素或者删除元素
        return 0;
    }
}

问题15：二叉排序树的插入（算法7.2重点&难点）和构造算法7.3

//插入操作
int insert(pBinSearchTree ptree,KeyType key){
    pBinSearchNode p,position;
    if(Search(ptree,key,&position)==1)
        return 1;
    p=(pBinSearchNode) malloc(sizeof (struct BinSearchNode)); //申请空间
    if(p= nullptr)
    {
        printf("Error\n");return 0;
    }
    p->KeyValue=key;
    p->left=p->right= nullptr;
    if(position== nullptr)
        *ptree=p;
    else if(key<position->KeyValue){
        position->left=p;
    }
    else
        position->right=p;
    return 1;

}

//构造二叉排序树
int createSearchTree(pBinSearchTree ptree,SetDictionary *dic){
    *ptree =nullptr;                //将二叉树置空
    for(int i=0;i<dic->n;i++)
        if(!insert(ptree,dic->element[i].key))    //将新结点插入树中
            return 0;
    return 1;
}

问题16：二叉排序树的删除及算法7.4（重点&难点）

//二叉排序树的删除
int deleteSearchTree(pBinSearchTree ptree,KeyType key){
    pBinSearchNode  parentp,p,r;
    p=*ptree;parentp= nullptr;
    
    //检索被删除结点p
    while(p!= nullptr){
        if(p->KeyValue=key)
            break;
        parentp =p;
        if(p->KeyValue>key)
            p=p->left;
        else
            p=p->right;
    }
    //不存在被删除结点p
    if(p== nullptr)
        return 0;
    
    //无左子树
    if(p->left== nullptr)
    {
        if (parentp== nullptr)   //删除根结点
            *ptree=p->right;
        else if(parentp->left==p)    //将右子树链接到父节点的左链
            parentp->left=p->left;
        else
            parentp->right=p->right;   //将右子树链接到父节点的右链
    }
    else     //有左子树
    {
        pBinSearchNode rr = p; //引入局部变量rr 并初始化为p
        for(r=p->left;r->right!= nullptr;r=r->left)
            rr=r;                  //在p的左子树中找最右下节点 *r *rr保存*r
        p->KeyValue=r->KeyValue;  //复制结点信息
        
        if(rr==p)
            p->left=r->left;
        else
            rr->right=r->left;
        p=r;
    }
    free(p);
    return 1;
}

7.4 最佳二叉排序树（自学）

问题17：什么是最佳二叉排序树，为什么要引入最佳二叉排序树

检索中平均比较次数最小的二叉排序树称为最佳二叉排序树。
    最佳二叉查找树就是平均查找长度最短的二叉查找树，它的结点构成上的特点是：除了最下一层可以不满外，其他各层都是充满了的。
    因为查询二叉排序树的时间复杂度与树的深度有关，而查询最佳二叉排序树的时间复杂度是最低的

7.5 平衡二叉排序树（重点，难点内容）

问题18：什么是平衡二叉排序树？为什么要引入AVL树？

假设所有字典元素的检索概率相等，但与等概的最佳二叉排序树不同，
不要求所有结点都存储在最接近根结点的位置以保持最佳的检索效率，
而仅仅要求从整体上看，在动态插入或者删除后，每个结点的左、右子树能够基本保持平衡。
这种便于动态保持平衡的二叉排序树，称为平衡二叉排序树。
    
因为最佳二叉排序树不仅构造的时间代价大，而且很难动态地保持。经过若干次插入和删除运算，
二叉排序树的检索效率就可能降低，甚至变得很差。为了更好的取代最佳二叉排序树，由此引入AVL树。

问题19：平衡因子的定义

结点右子树高度与左子树高度之差称为该结点的平衡因子。
    //平衡二叉排序树中每个结点的平衡因子只能是0、-1、1。

问题20：最小不平衡字树的定义

离插入结点最近，且以平衡因子绝对值大于1的结点为跟的树。

问题21：调整平衡的模式有哪几种，各自的实现方法是？

1 LL型调整

PAVLNode lL(PAVLNode a,PAVLNode b){
    a->bf=0;a->llink=b->rlink;b->bf=0;b->rlink=a;
    return b;
}

2 RR型调整

PAVLNode rR(PAVLNode a,PAVLNode b){
    a->bf=0;a->rlink=b->llink;b->bf=0;b->llink=a;
    return b;
}

3 LR型调整

PAVLNode lR(PAVLNode a,PAVLNode b){
    PAVLNode c = b->rlink;
    a->llink = c->rlink;b->rlink=c->llink;c->llink=b;c->rlink=a;
    switch(c->bf){
        case 0:a->bf=0;b->bf=0;break;
        case 1:a->bf=1;b->bf=0;break;
        case -1:a->bf=0;b->bf=-1;break;
            
    }
}

4 RL型调整

PAVLNode rL(PAVLNode a,PAVLNode b){
    PAVLNode c = b->llink;
    a->rlink = c->llink;b->llink=c->rlink;c->llink=a;c->rlink=b;
    switch(c->bf){
        case 0:a->bf=0;b->bf=0;break;
        case 1:a->bf=0;b->bf=1;break;
        case -1:a->bf=-1;b->bf=0;break;
            
    }
    c->bf=0;
    return c;
}