基于AVL树表示的集合ADT实现与应用

1 项目介绍

1.1 设计目的

平衡二叉树(AVL)作为一种重要的查找表结构，能有效地支持数据的并行处理。本设计使学生牢固掌握AVL树及其实现方法，并应用该结构实现集合抽象数据类型，提升学生对数据结构与数据抽象的认识，提高学生的综合实践与应用能力。

1.2 设计内容

本设计分为三个层次：

以二叉链表为存储结构，设计与实现AVL树-动态查找表及其6种基本运算

以AVL树表示集合，实现集合抽象数据类型及其10种基本运算

以集合表示个人微博或社交网络中好友集、粉丝集、关注人集，实现共同关注、共同喜好、二度好友等查询功能

1.3 主要数据对象

好友集、粉丝集、关注人集等

1.4 主要数据关系

抽象层面AVL可以表示数据元素之间层次关系或一对多关系

实际应用层面，所讨论的人物关系为集合内元素间的关系。立足于集合建立数据的逻辑模型

1.5 主要运算与功能要求

交互式操作界面(并非一定指图形式界面)

AVL树的6种基本运算：InitAVL、DestroyAVL、SearchAVL、InsertAVL、DeleteAVL、TraverseAVL

基于AVL表示及调用其6种基本运算实现集合ADT的基本运算：初始化set_init，销毁set_destroy，插入set_insert，删除set_remove，交set_intersection，并set_union，差set_diffrence，成员个数set_size，判断元素是否为集合成员的查找set_member，判断是否为子集set_subset，判断集合是否相等set_equal

基于集合ADT实现应用层功能：好友集、粉丝集、关注人集等的初始化与对成员的增删改查，实现共同关注、共同喜好、二度好友等查询

主要数据对象的数据文件组织与存储

1.6 设计提示

参考有关文献，实现AVL树的删除操作，维护其动态平衡，这可能是设计中较为复杂的算法；要求提供关键算法的时间与空间复杂度分析

要求从互联网上获取测试数据集或随机生成测试数据集，数据集的大小具有一定规模；数据与结果以文件保存

1.7 结构特点

对一棵查找树（search tree）进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(log n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree（平衡树）。非平衡树会影响树中数据的查询，插入和删除的效率。比如当一个二叉树极不平衡时，即所有的节点都在根的同一侧，此时树没有分支，就变成了一个链表。数据的排列是一维的，而不是二维的。在这种情况下，查找的速度下降到O(N)，而不是平衡二叉树的O(logN)。

AVL树是典型的平衡二叉树，定义如下：

AVL树，它或者是一颗空二叉树，或者是具有下列性质的二叉树：

其根的左右子树高度之差的绝对值不能超过1

其根的左右子树都是二叉平衡树

1.8 应用场景

由于在查询以及插入上具有优良的特性，AVL树常用来构造动态查找表(Dynamic Search Table)，可以在对数时间内完成插入或者查询操作。

我们常常需要查询某一个元素是否在集合中，或者向集合中插入元素，因此集合可以认为是一种典型的动态查找表，基于AVL树实现的集合(称为TreeSet)因此在插入以及查询上具有非常好的性能，而集合的交并补差操作又可以基于查询和插入实现，因此也具有良好的性能。而常用社交软件微博中粉丝、朋友、关注以及兴趣皆可以抽象为一个集合，朋友是粉丝和关注的交集，共同好友是两个用户好友的交集，二度好友是两个用户好友的差集，基于TreeSet实现的微博应用也因此继承了AVL树优良的特性。

点击下载源码