建站优化信息推广,软件开发公司排名国内,苏州和城乡建设局网站首页,研发和开发的区别题目要求#xff1a; AVL 树是一种自平衡的二叉搜索树。在 AVL 树中#xff0c;任何节点的两个子子树的高度最多相差一;如果在任何时候它们相差不止一#xff0c;则进行重新平衡以恢复此属性。图 1-4 说明了旋转规则。 图1 图2 图3 图4 现在给定一系列插入#xff0c;您应该… 题目要求 AVL 树是一种自平衡的二叉搜索树。在 AVL 树中任何节点的两个子子树的高度最多相差一;如果在任何时候它们相差不止一则进行重新平衡以恢复此属性。图 1-4 说明了旋转规则。 图1 图2 图3 图4 现在给定一系列插入您应该分辨生成的 AVL 树的根。 输入规格 每个输入文件都包含一个测试用例。对于每种情况第一行都包含一个正整数N(20)这是要插入的键的总数。然后N不同的整数键在下一行中给出。一行中的所有数字都用空格分隔。 输出规格 对于每个测试用例将生成的 AVL 树的根打印在一行中。 示例输入 1 5 88 70 61 96 120 示例输出 1 70 题解 思路如注释所示可通过所有测试点。
#includebits/stdc.h
using namespace std;
typedef struct AVLNode *Position;
typedef Position AVLTree;
typedef int ElementType;
struct AVLNode{ElementType Data;AVLTree Left;AVLTree Right;int Hight;
}; int Max(int a,int b){return a b ? a:b;
}int GetHight(AVLTree A)
{return A NULL ? -1 : A-Hight;
}AVLTree SingleLeftRotation(AVLTree A){AVLTree B A-Left;A-Left B-Right;B-Right A;A-Hight Max( GetHight(A-Left), GetHight(A-Right) ) 1;B-Hight Max( GetHight(B-Left), A-Hight ) 1;return B;
}AVLTree SingleRightRotation(AVLTree A){AVLTree B A-Right;A-Right B-Left;B-Left A;A-Hight Max( GetHight(A-Left), GetHight(A-Right) ) 1;B-Hight Max( GetHight(B-Right), A-Hight ) 1;return B;
}AVLTree DoubleLeftRightRotation(AVLTree A){/* 注意A必须有一个左子结点B且B必须有一个右子结点C *//* 将A、B与C做两次单旋返回新的根结点C *//* 将B与C做右单旋C被返回 */A-Left SingleRightRotation(A-Left);/* 将A与C做左单旋C被返回 */return SingleLeftRotation(A);
}AVLTree DoubleRightLeftRotation(AVLTree A){A-Right SingleLeftRotation(A-Right);return SingleRightRotation(A);
}AVLTree Insert(AVLTree T,ElementType X){if(!T){ //若插入空树。则新建一个结点 T (AVLTree)malloc(sizeof(struct AVLNode));T-Data X;T-Hight 0;T-Left NULL;T-Right NULL;} else if(X T-Data){ //插入左树 T-Left Insert(T-Left,X);if(GetHight(T-Left)-GetHight(T-Right) 2){ //出现不平衡 if(X T-Left-Data)T SingleLeftRotation(T); //插入在左树的左边-单左旋elseT DoubleLeftRightRotation(T); //插入再左树的右边-左右双旋 }}else if(X T-Data){ //插入右树T-Right Insert(T-Right,X);if(GetHight(T-Right)-GetHight(T-Left) 2){ //出现不平衡 if(X T-Right-Data)T SingleRightRotation(T); //单右旋 elseT DoubleRightLeftRotation(T); //右左旋 }} else return T;T-Hight Max(GetHight(T-Left),GetHight(T-Right))1;return T;
}int main(){AVLTree T NULL;int t;cint;while(t--){int num;cinnum;T Insert(T,num);}coutT-Data;
}
此题有以下几个要注意的点 1.Hight是指把 一个给定结点作为根节点时其代表的树的树高这样当左右子树树高差大于等于2时可以发现平衡树失衡。 2.树高取左右子树的最大值。 3.左右双旋的时候在代码层面实际是先右单旋再左单旋右左单旋时同理。
这里感觉何老师的ppt很清晰引一下侵删重点是找到“麻烦结点”对“不平衡发现者”是怎样破环的
