北邮 数据结构 平衡二叉树报告.docVIP

数 据 结 构实验报告实验名称：平衡二叉树1. 实验目的和内容根据平衡二叉树的抽象数据类型的定义，使用二叉链表实现一个平衡二叉树。二叉树的基本功能：1、平衡二叉树的建立2、平衡二叉树的查找3、平衡二叉树的插入4、平衡二叉树的删除5、平衡二叉树的销毁6、其他：自定义操作编写测试 main()函数测试平衡二叉树的正确性。2. 程序分析2.1 存储结构struct nodeint key; /值int height; /这个结点的父节点在这枝最长路径上的结点个数node *left; /左孩子指针node *right; /右孩子指针node(int k) key = k; left = right = 0; height = 1; /构造函数; 2.2 程序流程 插入结点构建排序二叉树 小于根节点？ 插入右枝插入左枝是左/右为空 根节点下移 是插入平衡？平衡否2.3 关键算法分析（由于函数过多，在此只挑选部分重要函数） 算法1： void AVL_Tree:left_rotate(node *&x) 1 算法功能：对 R-R型进行调整 2 算法基本思想：将结点右孩子进行逆时针旋转 3 算法空间、时间复杂度分析：都为0（1） 4 代码逻辑node *y = x-right; y为x的右孩子 x-right = y-left; 将y的左孩子赋给x的右孩子 y-left = x; x变为y的左孩子 fixheight(x); 修正x，y的height值 fixheight(y); x = y; 使x的父节点指向y算法2：void AVL_Tree:right_rotate(node *&x) 1 算法功能：对L-L型进行调整 2 算法基本思想：将左孩子进行顺时针旋转 3 算法空间、时间复杂度分析：都为0（1） 4 代码逻辑 node *y = x-left; /y为x的左孩子 x-left = y-right; y的右孩子赋给x的左孩子 y-right = x; x变为y的 右孩子 fixheight(x); 修正x和y的height值 fixheight(y); x = y; 使x的父节点指向y算法3：node*& AVL_Tree:balance(node *&p) 1 算法功能：对给定结点进行平衡操作 2 算法基本思想：通过平衡因子判断属于哪种情况，再依照情况进行平衡 3 算法空间、时间复杂度分析：没有递归和循环，都为O（1） 4 代码逻辑fixheight(p); /修正P的height值if (bfactor(p) = 2) 平衡因子为2，为L-？型if (bfactor(p-left) 0) P的左孩子平衡因子left); 相关平衡操作，若0，为L-L型。right_rotate(p);else if (bfactor(p) = -2) 平衡因子为2 ，为R-?型if (bfactor(p-right)0) P的右孩子平衡因子0，为R-L型right_rotate(p-right); 小于0时，为R-R型left_rotate(p);fixheight(p); 修正平衡后的P的height值return p;算法4：node* AVL_Tree:remove(node *&p, int k) 1 算法功能：删除给定key值的结点 2 算法基本思想：首先通过递归找到待删除结点，如果其没有右孩子，直接将其删除，将其左孩子链上去。若有右孩子，找到右枝中的最小结点代替待删除结点，对改变后的结点进行平衡。注意右孩子要删除其中的最小结点 3 算法空间、时间复杂度分析：有递归，递归次数最多为深度，时间复杂度0（nlogn），空间复杂度0（logn） 4 代码逻辑 if (k key) K小于根节点，在左枝中寻找p-left=remove(p-left, k); 递归else if (kp-key) K大于根节点，在右枝中寻找p-right=remove(p-right, k); 递归else 找到待删除结点node *q = p-left; q为删除结点的左孩子node *r = p-right; p为删除结点右孩子delete p;if (!r) /没有右子树return q; 直接将左孩子返回，相当于直接删除pnode* min = findmin(r); /有右子树时，找到右枝中的最小值min-right=removein(r); 使删除最小值后的右枝变为min的右枝 min-left = q; p的左孩子变为min的左孩子，相当于删除了p， balance(min); 对min进行balance操作return min;balance(p); 每次递归完都对p进行平衡操作return p;算法5：void AVL_Tree:insert(node *&p, int k) 1 算法功能：一边插入结点一边进行平衡 2 算法基本思想：按照构建排序二叉树的方法插入结点，每插入一次后判断是否需要平衡 3 算法空间、时间复杂度分析：插入节点寻找位置需要递归，时间复杂度O（logn）空间复杂度O(logn) 4 代码逻辑if (!p) 如果是插入第一个节点p = new node(k); 直接构造一个结点else if (k key) 插入值小于根节点，在左枝中寻找insert(p-left, k);if (height(p-left) - height(p-right) = 2) p的平衡因子为2if (kleft-key)right_rotate(p); /LL型elseleft_right_rotate(p); /L-R型else if (kp-key) 寻找值大于根节点，在右枝中寻找 insert(p-right, k);if (height(p-left) - height(p-right) = -2) 平衡因子为-2if (k p-right-key)left_rotate(p); R-R型elseright_left_rotate(p); R-L型else;fixheight(p); 修正P的height值算法6：node* AVL_Tree:findvalue(int key) 1 算法功能：查找key的位置 2 算法基本思想：根据排序二叉树的规则进项查找 3 算法空间时间复杂度分析：没有递归，时间复杂度0(logn)，空间复杂度O（1） 4 代码逻辑node *r = root; 初始化r为根节点，进行移动查找while (r != NULL) if (key key) 小于根节点，在左枝中寻找r = r-left;else if (keyr-key) 大于根节点，在后枝中寻找r = r-right;else return r;throw 无此值;2.4 其他使用了结构类型和类的知识。使用了STL中的算法，直接调用其寻找两个值中最小值的函数min，大大节约了时间 3. 程序运行结果分析 程序运行没有问题。编写了主函数进行了测试，测试结果正确4. 总结4.1实验的难点和关键点 本实验的难点和关键点在于大量的递归函数以及删除结点这两个方面，递归函