Golang AVL Tree with Example

1. Introduction

The AVL Tree is a self-balancing binary search tree, where the height difference between the left and right child nodes (known as the balance factor) is never more than one. Named after its inventors, Adelson-Velsky and Landis, the AVL tree adjusts itself on every insert or delete operation to maintain the balance factor, ensuring that the tree remains balanced, and search operations are optimized.

2. Implementation Steps

1. Define a Node structure with fields for data, height, left, and right.

2. Implement the rotation operations to maintain the tree's balance: rightRotate, leftRotate, leftRightRotate, and rightLeftRotate.

3. Implement methods for insertion (Insert) which self-balances.

4. Enhance the tree with a method to get balance factor (getBalance) and update height (updateHeight).

3. Implementation in Golang

package main
import (
	"fmt"
	"math"
)
type Node struct {
	data   int
	height int
	left   *Node
	right  *Node
}
func (n *Node) updateHeight() {
	n.height = 1 + int(math.Max(float64(height(n.left)), float64(height(n.right))))
}
func height(n *Node) int {
	if n == nil {
		return 0
	}
	return n.height
}
func (n *Node) getBalance() int {
	if n == nil {
		return 0
	}
	return height(n.left) - height(n.right)
}
func rightRotate(y *Node) *Node {
	x := y.left
	T3 := x.right
	x.right = y
	y.left = T3
	y.updateHeight()
	x.updateHeight()
	return x
}
func leftRotate(x *Node) *Node {
	y := x.right
	T2 := y.left
	y.left = x
	x.right = T2
	x.updateHeight()
	y.updateHeight()
	return y
}
func (n *Node) Insert(value int) *Node {
	if n == nil {
		return &Node{data: value, height: 1}
	}
	if value < n.data {
		n.left = n.left.Insert(value)
	} else if value > n.data {
		n.right = n.right.Insert(value)
	} else {
		return n
	}
	n.updateHeight()
	balance := n.getBalance()
	if balance > 1 {
		if value < n.left.data {
			return rightRotate(n)
		}
		return leftRotate(n)
	}
	if balance < -1 {
		if value > n.right.data {
			return leftRotate(n)
		}
		return rightRotate(n)
	}
	return n
}
func main() {
	var root *Node
	root = root.Insert(10)
	root = root.Insert(20)
	root = root.Insert(30)
	root = root.Insert(40)
	root = root.Insert(50)
	root = root.Insert(25)
	fmt.Println("Root node:", root.data)
}

Output:

Root node: 30

Explanation:

1. The Node struct represents each node of the AVL tree, holding the data, height (of that node), and pointers to its left and right children.

2. The updateHeight and height methods are used to maintain and retrieve the height of a node.

3. The getBalance method calculates the balance factor of a node.

4. The rotation methods (rightRotate, leftRotate, etc.) are used to ensure the AVL tree remains balanced after every insert operation.

5. The Insert method inserts a value into the AVL tree while ensuring that it remains balanced after the insertion.

6. The main function demonstrates insertion of several values into the AVL tree.

The AVL Tree ensures that the tree remains approximately balanced after every insert operation, ensuring that operations like search, insert, and delete can be performed in logarithmic time.