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

u013564276 · · 1061 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

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

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

Input Specification:

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

Output Specification:

For each test case, print ythe root of the resulting AVL tree inone 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    valueint
010    leftChild *Node
011    rightChild *Node
012    heightint
013 }
014 
015 func getHeight(node *Node)(heightint){
016    ifnode ==nil{
017       return -1
018    }
019    returnnode.height
020 }
021 
022 func isBalanced(parent *Node)(balancedbool){
023    diff:= getHeight(parent.leftChild) - getHeight(parent.rightChild)
024    diff_Abs := math.Abs(float64(diff))
025    ifdiff_Abs <</SPAN>2{
026       balanced = true
027    }else{
028       balanced = false
029    }
030    returnbalanced
031 }
032 
033 func max(n1 int,n2int) (num int){
034    num= n1
035    ifn2 >n1{
036       num = n2
037    }
038    returnnum
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    returnchild
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    returnchild
059 }
060 
061 func rotate_RL(parent *Node)(child *Node){
062    child= parent.rightChild
063    parent.rightChild = rotate_LL(child)
064    returnrotate_RR(parent)
065 }
066 
067 func rotate_LR(parent *Node)(child *Node){
068    child= parent.leftChild
069    parent.leftChild = rotate_RR(child)
070    returnrotate_LL(parent)
071 }
072 
073 func InsertNode(root *Node,newValue int) (*Node){
074    ifroot ==nil {
075       Root = &Node{newValue,nil,nil,0}
076       return Root
077    }
078    ifnewValue >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    returnRoot;
099 }
100 
101 func main() {
102    varN int
103    _, err:= fmt.Scanf("%d\n",&N)
104    iferr != nil {
105       fmt.Println("error", err)
106    }
107    varroot *Node = nil
108    fori := 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 }

有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:u013564276

查看原文:PAT: Root of AVL Tree (25),Go语言

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1061 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传