数据结构——平衡二叉树树试验报告-Read.DOCVIP

数据结构第三部分——平衡二叉树树实验报告 一、题目理解： 插入结点 在平衡二叉排序树BBST上插入一个新数据元素e的递规算法可以描述如下： 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增加1； 若e的关键字和BBST的根结点的关键字相等，则不进行插入； 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加1时，分别就下列情况处理之： BBST的根结点的平衡因子为－1（右子树深度大于左子树深度）：则将根结点的平衡因子更改为0，BBST的深度不变； BBST的根结点的平衡因子为0（左，右子树深度相等）：则将根结点的平衡因子更改为1，BBST的深度增加1； BBST的根结点的平衡因子为1（左子树深度大于右子树深度）：若BBST的左子树根结点的平衡因子为1，则需要进行单向右旋平衡处理，并且在右旋处理之后将根结点和右子树根结点的平衡因子更改为0，树的深度不变； 若BBST的左子树根结点的平衡因子为－1，这需进行先向左后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变； 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加1时，分别就不同情况处理。 删除结点 删除结点过程与插入结点的操作类似，基本过程是：平衡二叉树-》找到要删除的结点----》删除一个结点-变成二叉树旋转变回平衡二叉树 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点； 　　 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点； 　　 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整； 　　 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突； 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。