当前位置: 首页 > news >正文

如何做私彩网站华为手机网络营销策划方案

如何做私彩网站,华为手机网络营销策划方案,单页网站 jquery,专业建设企业网站题目要求: AVL 树是一种自平衡的二叉搜索树。在 AVL 树中,任何节点的两个子子树的高度最多相差一;如果在任何时候它们相差不止一,则进行重新平衡以恢复此属性。图 1-4 说明了旋转规则。 图1 图2 图3 图4 现在给定一系列插入,您应该…

 题目要求:

AVL 树是一种自平衡的二叉搜索树。在 AVL 树中,任何节点的两个子子树的高度最多相差一;如果在任何时候它们相差不止一,则进行重新平衡以恢复此属性。图 1-4 说明了旋转规则。

 

                                图1

                                图2

                                图3

                                图4

现在给定一系列插入,您应该分辨生成的 AVL 树的根。

输入规格: 

 每个输入文件都包含一个测试用例。对于每种情况,第一行都包含一个正整数N(<=20),这是要插入的键的总数。然后N不同的整数键在下一行中给出。一行中的所有数字都用空格分隔。

输出规格: 

 对于每个测试用例,将生成的 AVL 树的根打印在一行中。

示例输入 1: 

 5
88 70 61 96 120

 示例输出 1:

 70

题解: 

        思路如注释所示,可通过所有测试点。

#include<bits/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;cin>>t;while(t--){int num;cin>>num;T = Insert(T,num);}cout<<T->Data;
}

此题有以下几个要注意的点:

        1.Hight是指把 一个给定结点作为根节点时,其代表的树的树高,这样当左右子树树高差大于等于2时,可以发现平衡树失衡。

        2.树高取左右子树的最大值。

        3.左右双旋的时候在代码层面实际是先右单旋再左单旋,右左单旋时同理。

这里感觉何老师的ppt很清晰,(引一下,侵删)重点是找到“麻烦结点”对“不平衡发现者”是怎样破环的

 

http://www.ritt.cn/news/19995.html

相关文章:

  • 新闻网站怎么做漯河搜狗关键词优化排名软件
  • 建网站一条龙免费网页模板网站
  • 公众号电影网站是怎么做的电脑优化大师哪个好
  • 网页翻译软件seo关键词优化培训
  • 临沂做商城网站设计营销推广计划书
  • asp网站开发全程视频内蒙古seo
  • 人与马做的网站网络营销渠道名词解释
  • 网站漏洞谷歌seo查询
  • 什么是网站结构网页设计基础
  • 做招聘网站需要多少钱网站开发公司排行榜
  • 樟木头电子网站建设报价四川seo推广公司
  • 网站怎么改版自适应百度网盘人工客服
  • 网站开发(源代码)百度指数十年
  • 西安做网站xamokj上海牛巨微seo
  • 天津做网站的百度统计代码
  • 建设工程监理 精品课网站怎么给自己的公司建立网站
  • 怎么投诉网站制作公司哪家网站推广好
  • 客户关系管理系统的特点百度seo快速
  • 洛阳东翔科技做的网站广告公司品牌营销推广
  • 网站做app的软件有哪些8个公开大数据网站
  • php网站开发实例电子版seo引擎搜索
  • app和网站趋势网络营销推广经验总结
  • 易时代网站提高百度搜索排名
  • seo优化系统哪个好优化大师官网下载
  • 网站设计模板项目平台
  • 个人网站备案做论坛长沙靠谱seo优化费用
  • 北京有几家宽带网络公司谷歌seo视频教程
  • 企业品牌网站有哪些代写文章
  • 什么网站可以做图赚钱吗网站关键词百度自然排名优化
  • 盘县网站开发电商运营去哪里学比较好