后来发现当插入点的子树已经有三棵的时候还需要回溯到父结点重新执行插入动作,而此时的插入为插入子树, 并非插入结点,于是便把这两个操作分开,分别为 InsertNode 和 InsertTree 。 3. 开始由于思路上不是非常清晰,分类讨论插入结点情况时,造成好几处都忘记修改 lma x 和 mmax 的值,造成许多不必要的麻烦。 4. 由于把 Insert 的方法直接交给结点对象来做,于是在修改根结点的时候便会有一些麻烦, 因为子结点无法直接修改根结点的指向,于是便想到使用 Insert 方法的返回值来传递被修改过的新根结点,最后令 Tree23 类对象的 root 域指向新根结点。 5. 本算法正如教科书上所分析, 最多进行了 2-3 树的深度次递归, 所以时间复杂性为 O(log 2 n)。但是由于算法的缘故,每个结点对象比原计划多出了一个 rmax 域,造成了空间复杂性的上升,但是并不增加空间耗费的级别。 6. 由于在算法中出现了许多层次的判断, 所以不可避免地使得算法的效率并不是如理论上的那样快,但是比普通算法比起仍然要快许多,这个是由时间复杂性的级别决定的。五、用户手册 1. 本程序运行环境为控制台( Console ) ,执行文件为 2-3Tree.exe 。 2. 只需运行该程序便可看到演示结果。六、说明本程序开发环境为 Microsoft Visual Studio .NET 2003 ,使用高级语言为 Visual C++ .NET 7.0 。七、附录源程序文件名清单: 文件名说明 2-3Tree.cpp 主程序 S tdafx.cpp 系统生成连接用文件 Tree23.h 定义了 Tree23 类的头文件 Tree23Node.h 定义了 Tree23Node 类的头文件 Random.h 定义了随机数相关函数的头文件 Stdafx.h 系统生成头文件
全文预览
