分享
  1. 首页
  2. 文章

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

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

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

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

用户登录

没有账号?注册
或
(追記) (追記ここまで)

今日阅读排行

    加载中
(追記) (追記ここまで)

一周阅读排行

    加载中

关注我

  • 扫码关注领全套学习资料 关注微信公众号
  • 加入 QQ 群:
    • 192706294(已满)
    • 731990104(已满)
    • 798786647(已满)
    • 729884609(已满)
    • 977810755(已满)
    • 815126783(已满)
    • 812540095(已满)
    • 1006366459(已满)
    • 692541889

  • 关注微信公众号
  • 加入微信群:liuxiaoyan-s,备注入群
  • 也欢迎加入知识星球 Go粉丝们(免费)

给该专栏投稿 写篇新文章

每篇文章有总共有 5 次投稿机会

收入到我管理的专栏 新建专栏