1 一．实验内容分析： 1.实验目的：模拟用户登录系统，在O（lgn ）时间内完成用户登录、删除、修改等工作。 2.设计思路： 主要分以下四个类： AVLTreeNode:存储平衡树节点； AVLTree:AVL 平衡树的主要实现算法； UserInfo:存储用户信息； Interface:界面,与用户交互； 3.流程图以及类的主要包含和调用关系： 二.实验验证分析 （1）输入的形式和输入值的范围； 控制台的输入： 2 如图，输入为数字，超出范围将提示不正确并返回重新输入 文件的输入： 程序会找寻当前目录的database.data 文件，并读入数据，如果未找到则自创此 文件，创建空树 （2 ）输出的形式； 程序退出时析构函数保存文件到database.data 并覆盖原文件。 （3 ）程序所能达到的功能； 在O(lgn)时间内添加、查找、删除、修改用户信息。 （4 ）测试数据： 本系统包含三个测试函数样例： 1.顺序插入测试（分别在debu g 和 release 环境下和 STL map 比较速度） 2.随机插入测试（分别在debu g 和 release 环境下和 STL map 比较速度） 3.删除测试 测试函数均在main 文件里 void randomTest();//随机数测试 void orderTest();//顺序插入测试 void deleteTest();//删除测试 void main_interface();//主界面 1,2 均在debug 模式下插入100W 数据，在release 模式下插入1000W 数据。 顺序插入的实现是用整数1~n 转换为string，位数不够的在前面补‘0’。 3 测试结果： 1.debug 下顺序插入测试： 2.Release 下顺序插入测试 4 3.debug 下随机插入测试 4.release 下随机插入测试 实践证明map的红黑树在顺序插入测试时慢于我的avl 树，但随机插入测试表现比AVL 树要好。 5 3.删除数据的图形化表示（‘R’‘L’‘=’为平衡因子以检验正确性） 下面删除3（树中无 3）： 还是一样，下面删除2 6 删除成功，下面删除7 删除成功。 三.调试分析 （1 ）讨论分析调试过程中的主要技术问题以及具体的解决方法（至少３个）； 1.代码重复问题： 有重复的代码不是好代码。左右旋和左旋右旋有大量重复，经过分析发现左右旋可以分解为先左旋后右旋，但平衡因子调整方法不一。所以分解左旋和右旋为两个函数，调整平衡因子单分一个函数。 2.空间占用问题： 平衡因子只有 3 个取值却占了一个 int 4 个字节是极大的浪费，所以改用 char型。编程实践中发现树高也可以取消，也极大的节省了空间。 3.时间浪费...
