Golang program for implementation of AVL Trees

AVL trees are height balancing binary search tree. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor.
// AVL Tree in Golang
package main
 
import (
    "encoding/json"
    "fmt"
)

type Key interface {
    Less(Key) bool
    Eq(Key) bool
}
 

type Node struct {
    Data    Key
    Balance int
    Link    [2]*Node
}
 

func opp(dir int) int {
    return 1 - dir
}
 
// single rotation
func single(root *Node, dir int) *Node {
    save := root.Link[opp(dir)]
    root.Link[opp(dir)] = save.Link[dir]
    save.Link[dir] = root
    return save
}
 
// double rotation
func double(root *Node, dir int) *Node {
    save := root.Link[opp(dir)].Link[dir]
 
    root.Link[opp(dir)].Link[dir] = save.Link[opp(dir)]
    save.Link[opp(dir)] = root.Link[opp(dir)]
    root.Link[opp(dir)] = save
 
    save = root.Link[opp(dir)]
    root.Link[opp(dir)] = save.Link[dir]
    save.Link[dir] = root
    return save
}
 
// adjust valance factors after double rotation
func adjustBalance(root *Node, dir, bal int) {
    n := root.Link[dir]
    nn := n.Link[opp(dir)]
    switch nn.Balance {
    case 0:
        root.Balance = 0
        n.Balance = 0
    case bal:
        root.Balance = -bal
        n.Balance = 0
    default:
        root.Balance = 0
        n.Balance = bal
    }
    nn.Balance = 0
}
 
func insertBalance(root *Node, dir int) *Node {
    n := root.Link[dir]
    bal := 2*dir - 1
    if n.Balance == bal {
        root.Balance = 0
        n.Balance = 0
        return single(root, opp(dir))
    }
    adjustBalance(root, dir, bal)
    return double(root, opp(dir))
}
 
func insertR(root *Node, data Key) (*Node, bool) {
    if root == nil {
        return &Node{Data: data}, false
    }
    dir := 0
    if root.Data.Less(data) {
        dir = 1
    }
    var done bool
    root.Link[dir], done = insertR(root.Link[dir], data)
    if done {
        return root, true
    }
    root.Balance += 2*dir - 1
    switch root.Balance {
    case 0:
        return root, true
    case 1, -1:
        return root, false
    }
    return insertBalance(root, dir), true
}
 
// Insert a node into the AVL tree.
func Insert(tree **Node, data Key) {
    *tree, _ = insertR(*tree, data)
}

// Remove a single item from an AVL tree.
func Remove(tree **Node, data Key) {
    *tree, _ = removeR(*tree, data)
}

func removeBalance(root *Node, dir int) (*Node, bool) {
    n := root.Link[opp(dir)]
    bal := 2*dir - 1
    switch n.Balance {
    case -bal:
        root.Balance = 0
        n.Balance = 0
        return single(root, dir), false
    case bal:
        adjustBalance(root, opp(dir), -bal)
        return double(root, dir), false
    }
    root.Balance = -bal
    n.Balance = bal
    return single(root, dir), true
}
 
func removeR(root *Node, data Key) (*Node, bool) {
    if root == nil {
        return nil, false
    }
    if root.Data.Eq(data) {
        switch {
        case root.Link[0] == nil:
            return root.Link[1], false
        case root.Link[1] == nil:
            return root.Link[0], false
        }
        heir := root.Link[0]
        for heir.Link[1] != nil {
            heir = heir.Link[1]
        }
        root.Data = heir.Data
        data = heir.Data
    }
    dir := 0
    if root.Data.Less(data) {
        dir = 1
    }
    var done bool
    root.Link[dir], done = removeR(root.Link[dir], data)
    if done {
        return root, true
    }
    root.Balance += 1 - 2*dir
    switch root.Balance {
    case 1, -1:
        return root, true
    case 0:
        return root, false
    }
    return removeBalance(root, dir)
}
 

type intKey int 
func (k intKey) Less(k2 Key) bool { return k < k2.(intKey) }
func (k intKey) Eq(k2 Key) bool   { return k == k2.(intKey) }
 
func main() {
    var tree *Node
    fmt.Println("Empty Tree:")    
	avl,_ := json.MarshalIndent(tree, "", "   ")
	fmt.Println(string(avl))

    fmt.Println("\nInsert Tree:")
    Insert(&tree, intKey(4))
    Insert(&tree, intKey(2))
    Insert(&tree, intKey(7))
    Insert(&tree, intKey(6))
	Insert(&tree, intKey(6))
    Insert(&tree, intKey(9))
    avl,_ = json.MarshalIndent(tree, "", "   ")
	fmt.Println(string(avl))
 
    fmt.Println("\nRemove Tree:")
    Remove(&tree, intKey(4))
    Remove(&tree, intKey(6))
    avl,_ = json.MarshalIndent(tree, "", "   ")
	fmt.Println(string(avl))
}

Thanks for reading. Please leave your valuable feedback and comments.

* Required Fields