golang实现AVL树

AVL树是一棵高度平衡的二叉搜索树，它的特点是：

1.本身首先是一棵二叉搜索树。

2.带有平衡条件：每个结点的左右子树的高度之差的绝对值最多为1。

不废话直接上代码（golang实现）：

package main

import (
    "log"
)

func main() {
    array := []int{5, 3, 1, 8, 9, 10, 11, 2, 4, 7, 6, 12}
    var root *AVLTreeNode
    for _, v := range array {
        root = root.InsertNode(v)
        log.Println("root=> key:", root.value, "high:", root.high)
    }
    log.Println("-----------------")
    root.PrintSortTree()
}

type AVLTreeNode struct {
    value int
    high  int
    left  *AVLTreeNode
    right *AVLTreeNode
}

func NewAVLTreeRoot(root int) *AVLTreeNode {
    return &AVLTreeNode{root, 0, nil, nil}
}

func (this *AVLTreeNode) InsertNode(v int) *AVLTreeNode {
    if this == nil {
        return &AVLTreeNode{v, 0, nil, nil}
    }
    if v < this.value {
        this.left = this.left.InsertNode(v)
        this.high = getMax(this.left.getNodeHigh(), this.right.getNodeHigh()) + 1
        if this.left.getNodeHigh()-this.right.getNodeHigh() == 2 {
            if v < this.left.value {
                return this.rightRotation()
            } else {
                return this.leftRightRotation()
            }
        }
    } else {
        this.right = this.right.InsertNode(v)
        this.high = getMax(this.left.getNodeHigh(), this.right.getNodeHigh()) + 1
        if this.right.getNodeHigh()-this.left.getNodeHigh() == 2 {
            if v < this.right.value {
                return this.rightLeftRotation()
            } else {
                return this.leftRotation()
            }
        }
    }
    return this
}

func (this *AVLTreeNode) leftRotation() *AVLTreeNode {
    node := this.right
    this.right = node.left
    node.left = this
    this.high = getMax(this.left.getNodeHigh(), this.right.getNodeHigh()) + 1
    node.high = getMax(node.left.getNodeHigh(), node.right.getNodeHigh()) + 1
    return node
}

func (this *AVLTreeNode) rightRotation() *AVLTreeNode {
    node := this.left
    this.left = node.right
    node.right = this
    this.high = getMax(this.left.getNodeHigh(), this.right.getNodeHigh()) + 1
    node.high = getMax(node.left.getNodeHigh(), node.right.getNodeHigh()) + 1
    return node
}

func (this *AVLTreeNode) leftRightRotation() *AVLTreeNode {
    this.left = this.left.leftRotation()
    return this.rightRotation()
}

func (this *AVLTreeNode) rightLeftRotation() *AVLTreeNode {
    this.right = this.right.rightRotation()
    return this.leftRotation()
}

func (this *AVLTreeNode) getNodeHigh() int {
    if this == nil {
        return -1
    }
    return this.high
}

func (this *AVLTreeNode) PrintSortTree() {
    if this == nil {
        return
    }
    this.left.PrintSortTree()
    log.Println(this.value)
    this.right.PrintSortTree()
}

func getMax(a, b int) int {
    if a > b {
        return a
    }
    return b
}