当前位置: 传客网 > PAT: Root of AVL Tree (25),Go语言

PAT: Root of AVL Tree (25),Go语言

2016-11-01 作者:skyqqcloud

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Root of AVL Tree (25),Go语言" title="PAT: Root of AVL Tree (25),Go语言" />    Root of AVL Tree (25),Go语言" title="PAT: Root of AVL Tree (25),Go语言" />
Root of AVL Tree (25),Go语言" title="PAT: Root of AVL Tree (25),Go语言" />    Root of AVL Tree (25),Go语言" title="PAT: Root of AVL Tree (25),Go语言" />

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print ythe root of the resulting AVL tree in one line.

Sample Input 1:
5
88 70 61 96 120
Sample Output 1:
70
Sample Input 2:
7
88 70 61 96 120 90 65
Sample Output 2:
88
--------------------------------------------------------------------------------

代码参考了这位博主http://blog.csdn.net/tiantangrenjian/article/details/12891091,并将其改写为了Go语言的版本

 ---------------------------------------------------------------------------------------------------------------

001 package main
002 
003 import (
004     "fmt"
005     "math"
006 )
007 
008 type Node struct{
009     value int
010     leftChild *Node
011     rightChild *Node
012     height int
013 }
014 
015 func getHeight(node *Node) (height int){
016     if node == nil{
017         return -1
018     }
019     return node.height
020 }
021 
022 func isBalanced(parent *Node) (balanced bool){
023     diff := getHeight(parent.leftChild) - getHeight(parent.rightChild)
024     diff_Abs := math.Abs(float64(diff))
025     if diff_Abs <</SPAN> 2{
026         balanced = true
027     }else{
028         balanced = false
029     }
030     return balanced
031 }
032 
033 func max(n1 int,n2 int) (num int){
034     num = n1
035     if n2 > n1{
036         num = n2
037     }
038     return num
039 }
040 
041 func rotate_LL(parent *Node) (child *Node){
042     child = parent.leftChild
043     parent.leftChild = child.rightChild
044     child.rightChild = parent
045     
046     parent.height = max(getHeight(parent.leftChild),getHeight(parent.rightChild)) + 1//节点的高度一定是两个子节点高度的最大值+1
047     child.height = max(getHeight(child.leftChild),getHeight(child.rightChild)) + 1//破坏者的高度没变不用处理
048     return child
049 }
050 
051 func rotate_RR(parent *Node) (child *Node){
052     child = parent.rightChild
053     parent.rightChild = child.leftChild
054     child.leftChild = parent
055     
056     parent.height = max(getHeight(parent.leftChild),getHeight(parent.rightChild)) + 1
057     child.height = max(getHeight(child.leftChild),getHeight(child.rightChild)) + 1
058     return child
059 }
060 
061 func rotate_RL(parent *Node) (child *Node){
062     child = parent.rightChild
063     parent.rightChild = rotate_LL(child)
064     return rotate_RR(parent)
065 }
066 
067 func rotate_LR(parent *Node) (child *Node){
068     child = parent.leftChild
069     parent.leftChild = rotate_RR(child)
070     return rotate_LL(parent)
071 }
072 
073 func InsertNode(root *Node, newValue int) (*Node){
074     if root == nil {
075         Root = &Node{newValue,nil,nil,0}
076         return Root
077     }
078     if newValue > root.value {//在右边插入
079         root.rightChild = InsertNode(root.rightChild,newValue);
080         if !isBalanced(root) {
081             if newValue > root.rightChild.value {
082                 Root = rotate_RR(root)
083             }else{
084                 Root = rotate_RL(root)
085             }
086         }
087     }else{//在左边插入
088         root.leftChild = InsertNode(root.leftChild,newValue)
089         if !isBalanced(root) {
090             if newValue > root.leftChild.value {
091                 Root = rotate_LR(root);
092             }else{
093                 Root = rotate_LL(root)
094             }
095         }
096     }
097     Root.height = max(getHeight(Root.leftChild),getHeight(Root.rightChild)) + 1
098     return Root;
099 }
100 
101 func main() {
102     var N int
103     _, err := fmt.Scanf("%d\n",&N)
104     if err != nil {
105         fmt.Println("error", err)
106     }
107     var root *Node = nil
108     for i := 0; i <</SPAN> N; i++{
109         var data int
110         _, err = fmt.Scanf("%d",&data)
111         if err != nil {
112             fmt.Println("error", err)
113         }
114         root = InsertNode(root,data)
115     }
116     fmt.Println(root.value)
117 }


相关推荐

  • mycncart操作使用教程 - 语言设置

    mycncart是多语言多货币网站,默认带有三种语言,分别是英文、简体中文、繁体中文。如果你想新增或者删除语言,操作路径为网站后台【系统设置】->【参数设置】->【语言设置】。注意新增语言时,请根据各个语言的国际编码来填写相关信

  • python中的  语言 解释器  标准库  build in

    (1)语言规定了一些基本的语法,当然可以包含一些基本的数据类型,但是要知道语言的核心是规则,也就是形成Python程序语句的一些规则,它的重点不是某些特定的对象或类型。他的重点是有关构成程序语句的关键字以及单词如何排列。(2)解释器是按照语

  • Linux 系统下 C 语言程序设计 Linux腺呜衣氖敢tfqc

      目前Linux已经被广泛的使用,因此有必要简单介绍一下,在Linux系统下如何进行C  语言程序设计。首先介绍在Linux下如何编辑C语言源程序,接下来介绍如何编译C语言  源程序,  最好介绍如何调试与运行C语言源程序。  本节用一个

  • go 语言开发工具安装

    Go语言是Google新推出的结合了动态语言和静态语言优势的一个新兴的语言。下面介绍一下如何在Mac系统下安装和使用这个语言。设置环境变量$GOROOTGO语言的根目录,通常是$HOME/go,当然也可以是任何其他目录。$GOOS和$GOA

  • 3.1 语言的设计

    书名:《代码的未来》作者:松本行弘(YukihiroMatsumoto)译者:周自恒本试读章节摘自:『第3章编程语言的新潮流』接下来,我们从语言设计的角度,来比较一下Java、JavaScript、Ruby和Go这4种语言。这几种语言看起来

  • 第三章 语言的困境

    大多数语言的消亡,不是以人的意志为转移的、也不是想保护就能保护的,它们在让人不知不觉中消亡——是历史的必然。这也是人类的一种悲哀。美国国家地理创建有声字典:记录世界濒危语言在人类发展史上,语言的纷乱是因为隔绝,其实各种语言诞生的过程应该是近

  • ♥_ .☆☆____<莫小春专属>._ C 语言入门教程

    QQ:1326718615每晚与你们一起分享好看的情感日志和搞笑笑话?一、C语言的产生与发展C语言是1972年由美国的DennisRitchie设计发明的,并首次在UNIX操作系统的DECPDP-11计算机上使用。它由早期的编程语言BCPL

  • 如何设置Facebook 语言为中文??

    最近发现有人在玩FB但是很多人登录之后,显示的不是中文简体,然后也不知道要怎么改语言,因为看不懂!看不懂!看不懂!其实很简单,看图看图看图1.首先登录脸书之后点击主页,在整个界面的最右下角或者左下角是语言设置,点击下。2.点击语言设置,弹出

  • C 语言编译全过程

    C语言编译全过程一.编译的概念:编译程序读取源程序(字符流),对之进行词法和语法的分析,将高级语言指令转换为功能等效的汇编代码,再由汇编程序转换为机器语言,并且按照操作系统对可执行文件格式的要求链接生成可执行程序。二.编译的完整过程:C源程

  • C 语言的前世今生

    本篇是应《程序员》杂志约稿所写。原本要求是写篇谈C语言的短文。4000字以内。我刚列了个提纲就去了三千多字。-_-现放在这里,接管大师的攻讦斧正。勿转载。C语言的宿世此生C语言,从1970年月设计并实现之初,它就注定了带有强烈工程师文化的语

  • ARM  Architecture C 语言寻址解析—— 从U-Boot relocation所展开的探索(三)

    ARMArchitectureC语言寻址解析——从U-Bootrelocation所展开的探索(三)byLazyCatDesignwww.lazycatdesign.comARMArchitectureC语言PIC寻址方式解析(续)继续讨论

  • 第一章  语言

    语言是人类之所以成为人类的标志,它伴随着人类的起源而出现,也将随着人类的消失而泯灭,没有语言,就没有人类。语言极大地促进人类的发展。人是自然的一部分,人作为地球生物进化的高级阶段,是大自然和人类自身演化的产物。开始,人是和其它动物一样生长于

  • ARM  Architecture C 语言寻址解析—— 从U-Boot relocation所展开的探索(一)

    ARMArchitectureC语言寻址解析——从U-Bootrelocation所展开的探索(一)byLazyCatDesignwww.lazycatdesign.com文章的名字有点长也有点拗口,但它却很好的表达了本文的主题和来历。这个

  • 上海图书公司图书专营店-古文观止(注音版)  李梦生 等著 语言文字 商城 正版

    上海图书公司图书专营店-古文观止(注音版)李梦生等著语言文字商城正版商品【古文观止(注音版)李梦生等著语言文字商城正版】是来自于天猫店铺上海图书公司图书专营店所经营的商品,其上海图书公司图书专营店主要经营的商品有:365作文启蒙,小米商城,

  • 课题研究计划《在小学英语教学中培养学生的 语言交际能力的研究》

    一、课题研究的目的意义:新的《英语课程标准》强调义务教育阶段英语课程的目的之一就是:使学生掌握一定的语言基本知识和基本技能,建立初步的语感,获得初步运用英语的能力,为真实交际打下基础”。新课程标准特别强调突出语言的实践性特征,目的就是培养学

  • C 语言的32个关键字

    程序中数据分两种:常量和变量。C语言中规定标识符只能由字母、数字、下划线三种字符组成。而且第一个字符只能是字母或下划线。注意:C语言是区分大小写的。ANSIC没有限定标识符的长度,编程时要根据不同版本的C编译环境制定标识符(主要是变量名)的

  • Go 语言初步(转载自云风的BLOG)

    Go语言初步(转载自云风的BLOG)原著连接:http://blog.codingnow.com/2010/11/go_prime.html这几天认真玩起了Go。所谓认真玩,就是拿Go写点程序,前后大约两千行吧。据说Go的最佳开发平台是Ma

  • Python、 R 语言、SAS、SPSS 优缺点比较

    Python、R语言、SAS、SPSS优缺点比较最近一直想入门数据分析的小伙伴问我,如果要入事数据分析一直来说要学那些语言呢?其实小编跟企业部门部门与侯选人接触下来,给我的感觉是对于这个初级的数据分析师来,一般前二年做差不多都是老大让你做的

  • MATLAB 与 C 语言的接口

    MATLAB到C语言程序的转换可以由两种途径完成,其一是MATLAB自己提供的C语言翻译程序mcc,另一种是原第3方公司MathTools开发的MATCOM。后者出现较早,功能远比MATLAB自己的翻译程序强大,所以MathTools公司已

  • Swift 语言指南【转】

    Swift语言指南@SwiftLanguage更新于2016-3-7,更新内容详见Issue47。往期更新回顾详见《收录周报》  这份指南汇集了Swift语言主流学习资源,并以开发者的视角整理编排。对于精选项目及文章,可直接访问《Swift

返回
顶部