AVL tree in go programming language *Data structure* ,any one can take this as a challenge and *implement it in python programing language

Any guru here who can attemp this

Tree.go
Package avltree

import (
"errors"
)

type Tree struct {
root *Node
}

func NewTree(comparator func(a, b *Node) int) (*Tree) {
comp = comparator
return &Tree{}
}

func (tree *Tree) Insert(value interface{}) {
n := create(value)
rootNode := tree.root
if rootNode == nil {
n.height = 0
tree.root = n
} else {
rootNode.add(n, tree)
}
}

func (tree *Tree) InOrderTraversal(do func(a *Node)) {
inOrderTraversal(tree.root, do)
}

func (tree *Tree) PreOrderTraversal(do func(a *Node)) {
preOrderTraversal(tree.root, do)
}
func (tree *Tree) PostOrderTraversal(do func(a *Node)) {
postOrderTraversal(tree.root, do)
}

func (tree *Tree) Delete(node *Node) error {
if node == nil {
return errors.New("Couldn't found node with the value specified"
}

if node.IsLeave() {
parent := node.parent
parent.detachChild(node)
tree.rebalance(parent)
}

if node.left != nil && node.right == nil {
parent := node.parent
parent.setLeft(node.left)
tree.rebalance(parent)
} else if node.left == nil && node.right != nil {
parent := node.parent
parent.setRight(node.right)
tree.rebalance(parent)
}

if node.left != nil && node.right != nil {
_, successor := tree.Successor(node)
node.Value = successor.Value
tree.Delete(successor)
}

return nil
}

func (tree *Tree) Find(value interface{}) (error, *Node){
n := create(value)
foundNode := tree.compare(n, tree.root)
if foundNode == nil {
return errors.New("Node was not found", nil
}
return nil, foundNode
}

func (tree *Tree) Successor(node *Node) (error, *Node) {
if node.right != nil {
return nil, tree.min(node.right)
} else {
return errors.New("Node has no right child", nil
}
}

func (tree *Tree) min(node *Node) *Node{
if node.left == nil {
return node
}
return tree.min(node.left)
}

func (tree *Tree) compare(node, current *Node) (*Node) {
if current == nil {
return nil
}
comparison := comp(current, node)
if comparison == 0 {
return current
} else if comparison > 0 {
return tree.compare(node, current.right)
} else {
return tree.compare(node, current.left)
}
}

func (tree *Tree) rebalance(node *Node) {
if node != nil {
node.updateHeight()
if !node.IsBalanced() {
bf := balancedFactor(node)
if bf > 0 {
bfNext := balancedFactor(node.left)
if bfNext == 0 || bfNext == 1{
leftLeftRotation(node, tree)
} else {
leftRightRotation(node, tree)
}
} else {
bfNext := balancedFactor(node.right)
if bfNext == 0 || bfNext == 1{
rightRightRotation(node, tree)
} else {
rightLeftRotation(node, tree)
}
}
} else {
tree.rebalance(node.parent)
}
}
}

func inOrderTraversal(node *Node, do func(a *Node)) {
if node != nil {
inOrderTraversal(node.left, do)
do(node)
inOrderTraversal(node.right, do)
}
}

func preOrderTraversal(node *Node, do func(a *Node)) {
if node != nil {
do(node)
preOrderTraversal(node.left, do)
preOrderTraversal(node.right, do)
}
}

func postOrderTraversal(node *Node, do func(a *Node)) {
if node != nil {
postOrderTraversal(node.left, do)
postOrderTraversal(node.right, do)
do(node)
}
}
• Node .go
• package avltree
•
• import (
• "math"
• "errors"
• )
•
• type Node struct {
• parent *Node
• Value interface{}
• left *Node
• right *Node
• height int
• }
•
• var comp func(a, b *Node) int
•
• func create(value interface{}) (node *Node) {
• return &Node{Value:value}
• }
•
• func getHeight(node *Node) int {
• if node != nil {
• return node.height
• }
• return -1
• }
•
• func balancedFactor(node *Node) int {
• left := getHeight(node.left)
• right := getHeight(node.right)
• return left - right
• }
•
• func (n *Node) add(child *Node, tree *Tree) {
• greaterFactor := comp(n, child)
• if greaterFactor > 0 {
• if n.right != nil {
• n.right.add(child, tree)
• } else {
• n.setRight(child)
• }
• } else {
• if n.left != nil {
• n.left.add(child, tree)
• } else {
• n.setLeft(child)
• }
•
• }
•
• n.updateHeight()
• if !n.IsBalanced() {
• rotate(n, tree)
• }
•
• }
•
• func (n *Node) updateHeight() {
• hleft := getHeight(n.left)
• hright := getHeight(n.right)
• n.height = int(math.Max(float64(hleft), float64(hright))) + 1
• }
•
• func (n *Node) Left() (*Node) {
• return n.left
• }
•
• func (n *Node) Right() (*Node) {
• return n.right
• }
•
• func (n *Node) IsLeave() bool {
• return n.right == nil && n.left == nil
• }
•
• func (n *Node) IsBalanced() bool {
• return math.Abs(float64(balancedFactor(n))) < 2
• }
•
• func (n *Node) GetHeight() int {
• return n.height
• }
•
• func (n *Node) GetParent() (*Node) {
• return n.parent
• }
•
• func (n *Node) setLeft(node *Node) {
• n.left = node
• if node != nil {
• node.parent = n
• }
• }
•
• func (n *Node) setRight(node *Node) {
• n.right = node
• if node != nil {
• node.parent = n
• }
• }
•
• func (n *Node) detachChild(node *Node) error {
• if n.left == node {
• n.left = nil
• node.parent = nil
• return nil
• }
•
• if n.right == node {
• n.right = nil
• node.parent = nil
• return nil
• }
•
• return errors.New("Node wasn't found"
• }
•
• func rotate(n *Node, tree *Tree) {
• if !n.IsBalanced() {
• bf := balancedFactor(n)
• if bf > 0 {
• bfNext := balancedFactor(n.left)
• if bfNext > 0 {
• leftLeftRotation(n, tree)
• } else {
• leftRightRotation(n, tree)
• }
• } else {
• bfNext := balancedFactor(n.right)
• if bfNext > 0 {
• rightLeftRotation(n, tree)
• } else {
• rightRightRotation(n, tree)
• }
• }
• }
• }
•
• func leftLeftRotation(pivot *Node, tree *Tree) {
• child := pivot.left
•
• // House keeping
• fixTree(pivot, child, tree)
•
• pivot.setLeft(child.right)
• child.setRight(pivot)
•
• updateChild(child)
•
• }
•
• func leftRightRotation(pivot *Node, tree *Tree) {
• rightRightRotation(pivot.left, tree)
• leftLeftRotation(pivot, tree)
• }
•
• func rightRightRotation(pivot *Node, tree *Tree) {
• child := pivot.right
•
• fixTree(pivot, child, tree)
•
• pivot.setRight(child.left)
• child.setLeft(pivot)
•
• updateChild(child)
• }
•
• func rightLeftRotation(pivot *Node, tree *Tree) {
• leftLeftRotation(pivot.right, tree)
• rightRightRotation(pivot, tree)
• }
•
• func fixTree(pivot, pivotChild *Node, tree *Tree) {
• if tree.root == pivot {
• tree.root = pivotChild
• pivotChild.parent = nil
• } else {
• if pivot.parent.left == pivot {
• pivot.parent.setLeft(pivotChild)
• } else {
• pivot.parent.setRight(pivotChild)
• }
• }
• }
•
• func updateChild(child *Node) {
• if child.left != nil {
• child.left.updateHeight()
• }
•
• if child.right != nil {
• child.right.updateHeight()
• }
• child.updateHeight()
• }