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.
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 }
