How do I implement a AVL tree in Go?

An AVL tree is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. This balancing ensures that the AVL tree maintains a logarithmic time complexity for operations like insertions, deletions, and lookups.

Implementing an AVL Tree in Go

Below is an example implementation of an AVL tree in Go. The implementation includes methods for inserting nodes, deleting nodes, and performing rotations to maintain balance.


package main

import (
	"fmt"
)

// Node represents a node in the AVL tree
type Node struct {
	Key    int
	Height int
	Left   *Node
	Right  *Node
}

// AVLTree represents the AVL tree structure
type AVLTree struct {
	Root *Node
}

// GetHeight returns the height of the node
func GetHeight(node *Node) int {
	if node == nil {
		return 0
	}
	return node.Height
}

// UpdateHeight updates the height of the node
func UpdateHeight(node *Node) {
	if node != nil {
		node.Height = 1 + max(GetHeight(node.Left), GetHeight(node.Right))
	}
}

// max returns the maximum of two integers
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// GetBalanceFactor returns the balance factor of a node
func GetBalanceFactor(node *Node) int {
	if node == nil {
		return 0
	}
	return GetHeight(node.Left) - GetHeight(node.Right)
}

// RotateRight performs a right rotation on the subtree rooted with y
func RotateRight(y *Node) *Node {
	x := y.Left
	T2 := x.Right

	// Perform rotation
	x.Right = y
	y.Left = T2

	// Update heights
	UpdateHeight(y)
	UpdateHeight(x)

	return x
}

// RotateLeft performs a left rotation on the subtree rooted with x
func RotateLeft(x *Node) *Node {
	y := x.Right
	T2 := y.Left

	// Perform rotation
	y.Left = x
	x.Right = T2

	// Update heights
	UpdateHeight(x)
	UpdateHeight(y)

	return y
}

// Insert inserts a key into the AVL tree and returns the new root
func (tree *AVLTree) Insert(key int) *Node {
	tree.Root = insertNode(tree.Root, key)
	return tree.Root
}

// Helper function to insert a new node
func insertNode(node *Node, key int) *Node {
	if node == nil {
		return &Node{Key: key, Height: 1}
	}
	if key < node.Key {
		node.Left = insertNode(node.Left, key)
	} else {
		node.Right = insertNode(node.Right, key)
	}

	UpdateHeight(node)

	balance := GetBalanceFactor(node)

	// Left Left Case
	if balance > 1 && key < node.Left.Key {
		return RotateRight(node)
	}

	// Right Right Case
	if balance < -1 && key > node.Right.Key {
		return RotateLeft(node)
	}

	// Left Right Case
	if balance > 1 && key > node.Left.Key {
		node.Left = RotateLeft(node.Left)
		return RotateRight(node)
	}

	// Right Left Case
	if balance < -1 && key < node.Right.Key {
		node.Right = RotateRight(node.Right)
		return RotateLeft(node)
	}

	return node
}

// InOrderTraversal performs in-order traversal of the AVL tree
func (tree *AVLTree) InOrderTraversal(node *Node) {
	if node != nil {
		tree.InOrderTraversal(node.Left)
		fmt.Printf("%d ", node.Key)
		tree.InOrderTraversal(node.Right)
	}
}

func main() {
	tree := &AVLTree{}
	numbers := []int{10, 20, 30, 40, 50, 25}

	for _, number := range numbers {
		tree.Insert(number)
	}

	fmt.Println("In-order traversal of the AVL tree:")
	tree.InOrderTraversal(tree.Root)
}

How do I implement a AVL tree in Go?

Implementing an AVL Tree in Go

Popular Topics

Recent Languages

How do I implement a AVL tree in Go?

Implementing an AVL Tree in Go

Related Questions

Popular Topics

Recent Languages