golang实现AVL树

AVL树是一棵高度平衡的二叉搜索树，它的特点是：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值最多为1。

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

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

AVL树是一棵高度平衡的二叉搜索树，它的特点是：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值最多为1。

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