Advanced Data Structures in Go

				
					package main

import (
	"fmt"
)

type Node struct {
	key    int
	left   *Node
	right  *Node
	height int
}

func newNode(key int) *Node {
	return &Node{
		key:    key,
		left:   nil,
		right:  nil,
		height: 1,
	}
}

func height(node *Node) int {
	if node == nil {
		return 0
	}
	return node.height
}

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

func balanceFactor(node *Node) int {
	if node == nil {
		return 0
	}
	return height(node.left) - height(node.right)
}

func leftRotate(x *Node) *Node {
	y := x.right
	T2 := y.left

	y.left = x
	x.right = T2

	x.height = max(height(x.left), height(x.right)) + 1
	y.height = max(height(y.left), height(y.right)) + 1

	return y
}

func rightRotate(y *Node) *Node {
	x := y.left
	T2 := x.right

	x.right = y
	y.left = T2

	y.height = max(height(y.left), height(y.right)) + 1
	x.height = max(height(x.left), height(x.right)) + 1

	return x
}

func insert(root *Node, key int) *Node {
	if root == nil {
		return newNode(key)
	}

	if key < root.key {
		root.left = insert(root.left, key)
	} else if key > root.key {
		root.right = insert(root.right, key)
	} else {
		return root
	}

	root.height = 1 + max(height(root.left), height(root.right))

	balance := balanceFactor(root)

	// Left Left Case
	if balance > 1 && key < root.left.key {
		return rightRotate(root)
	}

	// Right Right Case
	if balance < -1 && key > root.right.key {
		return leftRotate(root)
	}

	// Left Right Case
	if balance > 1 && key > root.left.key {
		root.left = leftRotate(root.left)
		return rightRotate(root)
	}

	// Right Left Case
	if balance < -1 && key < root.right.key {
		root.right = rightRotate(root.right)
		return leftRotate(root)
	}

	return root
}

func inorderTraversal(root *Node) {
	if root != nil {
		inorderTraversal(root.left)
		fmt.Printf("%d ", root.key)
		inorderTraversal(root.right)
	}
}

func main() {
	var root *Node
	keys := []int{10, 20, 30, 40, 50, 25}

	for _, key := range keys {
		root = insert(root, key)
	}

	fmt.Println("Inorder traversal of the constructed AVL tree:")
	inorderTraversal(root)
}