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

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寻址方式解析(续)继续讨论
  • 第一章  语言 语言是人类之所以成为人类的标志,它伴随着人类的起源而出现,也将随着人类的消失而泯灭,没有语言,就没有人类。语言极大地促进人类的发展。人是自然的一部分,人作为地球生物进化的高级阶段,是大自然和人类自身演化的产物。开始,人是和其它动物一样生长于

你的评论

就没有什么想说的吗?

最新博客

关于我们 移动版

©2017传客网    琼ICP备15003173号-2    

本站部分文章来源于互联网,版权归属于原作者。
本站所有转载文章言论不代表本站观点,如是侵犯了原作者的权利请发邮件联系站长(weishubao@126.com),我们收到后立即删除。
站内所有资源仅供学习与参考,请勿用于商业用途,否则产生的一切后果将由您自己承担!

X