算法介绍与代价分析

1、由源文件拷贝数据至顺序结构中 2、倒排索引（AVL树）的插入算法 3、倒排索引（AVL树）的删除算法 4、倒排索引的建立算法 5、导出倒排文件的算法 6、访问算法（完全查询、存在查询 、统计查询、逻辑查询 ） 7、修改算法



1、由源文件拷贝数据至顺序结构中 PSeqList ConvertFile (FILE *a); 算法思路：先生成一个SeqList结构，在第一个Student 结构中存储相应的信息。 当文件没有结束且遇到’\n’（或其他特定的标志）时，生成一个新的Student结 构，并存储相应的信息。 代价分析： 时间代价：O(n) 空间代价：O(n)
谢谢大家 欢迎指正
sum2=层数 ×权数
几种思路：
1、AVL树——倒排索引—— 不等概情况下的最佳二叉排序 树（pp.214） 3 时间代价：O(n ) 时间代价过于庞大 最佳二叉排序树不适合 频繁的插入删除操作

Sum2(记录 节点检索花 费）



2、改进AVL树，改进AVL树 的插入和调整算法。 使调整 时既要考虑到各子树的高度 相差不能太大，又要考虑到 能使各关键码总的检索花费 最小。 在大规模的插入删除操作之 后，要调用调整函数，使在 保持树的平衡性的前提下 （对于插入操作，AVL树总 是比较合适的）使总的检索 花费最小。 void balance(PAVLTree ptree, PSeqList buffer, int n); 使用递归算法，从下而上调 整二叉树，调整规则见右图 思路比较可行




3、改用其他结构：hashing 把hash表的检索优势与AVL树的排序优势结合起来。 首先申请一个hash空间，每一个关键码都对应空间中的一小段散列表，将 AVL树中各节点的下标信息通过一个散列函数存贮至各个散列表中（不同的 节点所对应的散列函数可以相差一个偏移常量）。查找时再根据要查的关键 码和散列函数在hash空间中查出所需的记录。 由于散列表是在AVL树建立之后生成,所以各散列表的存储空间的大小就可以 根据AVL树中的各节点的重复键值的多少来决定，可以尽可能减少散列表被充 满的概率。 85 右图中，H为散列函数， 84 90 M为偏移量（可由关键码 小王 计算得到） 92 小张 87
Nhomakorabea

//用平衡二叉排序树记录倒排索引的信息 struct AVLNode; typedef struct AVLNode * PAVLNode; struct AVLNode //平衡二叉排序树的节点 { Student info; //关键码储存在Student结构中（也可略去） int bf; //节点的平衡因子 int position; //此节点对应在顺序结构中的位置 int snum; //与此节点关键码相同的数据的出现次数 int * same; //与此节点含有相同关键码的节点在顺序 结构中的位置 }; typedef struct AVLNode * AVLTree; typedef struct AVLTree * PAVLTree;
基于改进的AVL树的重复键 值倒排索引的建立、使用 （访问）与维护——以 student.txt为例
冯峰 00646034 2007年5月21日
问题描述及场景分析

对于给定的student.txt文件(一些学生的成绩信息)，对其中任意一 个关键码(比如id,成绩,姓名等)生成倒排索引,要求能对其中的记录 进行各种查询,修改,删除等操作。 同时，尝试能否将算法使用与更加一般的情况。
在构造AVL树时，如果考虑到
有多层次的关键码比较，可以构 造嵌套的AVL树结构，即在主 AVL树的节点下对于次要关键码 再生成一个子AVL树。 应用：足球联赛中球队排名先 比较积分，再比较净胜球，然后 比较进球数或胜负关系


出现问题：考虑重复关键码的检索概率 关键码的重复概率分布比较随机、重复的次数又比较多时，单纯的AVL 树不能满足要求，需要修改算法。




2、倒排索引（AVL树）的插入算法 int insertElement(PAVLTree ptree, Student a, int n);//n为关键码的代码，例如1 为ID,2为姓名等 算法思路： 如果二叉排序树为空，则新节点为根节点，bf=0，position=0，snum=0（根据 需要也可以将顺序结构中的节点信息拷贝至Student info中）。 若二叉排序树非空，则将新节点的关键码与根节点的关键码比较，若大于，则 比较右子树；若小于，则比较左子树；直至左（右）子树为空或有节点的关键 码与新节点的关键码相等。 若左（右）子树为空，则将新节点作为当前节点的左（右）子树，同时改写新 节点和其父节点中的position，bf，snum等信息；然后更改其比较路径上各节 点的bf信息（平衡因子），若插入破坏了树的平衡性，则调用相应的调整函数 对子树进行调整。 调整函数： PAVLNode LL(PAVLNode a, PAVLNode b); PAVLNode RR(PAVLNode a, PAVLNode b); PAVLNode LR(PAVLNode a, PAVLNode b); PAVLNode RL(PAVLNode a, PAVLNode b); 若遇到关键码与之相等的节点，则这个节点的snum++，生成一个same数组 （或连接表示），储存新节点在顺序结构中的下标。 代价分析： 时间代价： O(log2 n) 主要是比较关键码消耗的时间代价 空间代价：O(1)
程序整体结构和思想
所用数据结构




//存储学生记录信息的结构体 typedef struct { int ID; //学号 char * name;//姓名 int score1; //成绩 int score2; float ave; }Student; typedef struct Student * PStudent; //每条记录的格式：ID 姓名 成绩1 成绩2 平均分 //用顺序结构存储源文件中的记录信息 struct SeqList { int num; int MAXNUM; Student *element; } typedef struct SeqList * PSeqList;

3、倒排索引（AVL树）的删除算法 int deleteElement(PAVLTree ptree, Student a, int n); (与插入算法类似: 查找-删除-调整 此处略去) 4、倒排索引的建立算法 PAVLNode createAVL(PSeqList buffer, int(compare)(Student a, Student b) ); （对buffer中的记录不断进行插入算法） 5、导出倒排文件的算法 PSeqList outSeq (PAVLTree ptree, PSeqList buffer, int n); （中根次序周游，对于重复键值的节点特殊处理） 6、访问算法 根据访问的需要，选择使用AVL树还是生成的倒排文件
小刘 如果散 列表充 满，则 申请新 的空间
H(姓名) H(姓名)+M
小 李 小 赵
Hash空


这样，对于所有的检索，时间代价都被缩短到了常数量级，不等概率检索的 问题也就不存在了。 Hash表对于插入和删除操作也是相当方便的，只是需要的内存空间比较大。 AVL树、倒排索引、hash表的结合使得我们对含有关键码的记录的维护变得 简单易行： AVL树：记录的组织、排序 Hash表：单个元素查询 倒排索引：逻辑查询，其他应用





AVL树：完全查询、存在查询 、统计查询 倒排文件：逻辑查询

7、修改算法（单个元素修改，对关键码相同的元素进行修改） 先删除再插入

以上算法确实能够满足要求 学生的成绩一般是正态分布，AVL树的上层节点被检索的频率较大，树的 结构也接近于最佳二叉排序树，所以平均检索的花费会处于一个较低水平。