AVL Tree Implementation in Go

An AVL Tree is a self-balancing binary search tree where the difference in heights between the left and right subtrees (known as the balance factor) of any node is at most one. This balancing ensures that operations like insertion, deletion, and searching can be performed in O(log n) time.

Program Structure

The Go program implementing the AVL Tree is structured into the following components:

  1. Node Struct: This struct represents a node in the AVL Tree, containing fields for the key, height, left child, and right child.
  2. AVLTree Struct: This struct represents the AVL Tree itself, containing the root node.
  3. Insert Method: This method inserts a new key into the AVL Tree while maintaining the AVL property by balancing the tree as needed.
  4. LeftRotate and RightRotate Methods: These methods perform rotations to restore balance when the tree becomes unbalanced.
  5. Balance Method: This helper method checks the balance factor of nodes and performs the necessary rotations to keep the tree balanced.
  6. Height and GetBalance Methods: These methods help calculate the height of nodes and the balance factor, which are critical in maintaining the AVL property.
  7. InOrderTraversal Method: This method performs an in-order traversal of the tree to print the nodes in sorted order.

Go Code Implementation


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
}

// Insert inserts a new key into the AVL Tree and balances the tree
func (t *AVLTree) Insert(key int) {
    t.root = insert(t.root, key)
}

// insert recursively inserts a new key into the subtree rooted at node
func insert(node *Node, key int) *Node {
    if node == nil {
        return &Node{key: key, height: 1}
    }
    if key < node.key { node.left = insert(node.left, key) } else if key > node.key {
        node.right = insert(node.right, key)
    } else {
        return node // Duplicate keys are not allowed in the AVL Tree
    }

    node.height = 1 + max(height(node.left), height(node.right))
    return balance(node)
}

// LeftRotate performs a left rotation on the given node
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
}

// RightRotate performs a right rotation on the given node
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
}

// balance checks the balance factor of the node and performs rotations if needed
func balance(node *Node) *Node {
    balanceFactor := getBalance(node)

    // Left Left Case
    if balanceFactor > 1 && getBalance(node.left) >= 0 {
        return rightRotate(node)
    }

    // Left Right Case
    if balanceFactor > 1 && getBalance(node.left) < 0 {
        node.left = leftRotate(node.left)
        return rightRotate(node)
    }

    // Right Right Case
    if balanceFactor < -1 && getBalance(node.right) <= 0 {
        return leftRotate(node)
    }

    // Right Left Case
    if balanceFactor < -1 && getBalance(node.right) > 0 {
        node.right = rightRotate(node.right)
        return leftRotate(node)
    }

    return node
}

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

// getBalance returns the balance factor of the node
func getBalance(node *Node) int {
    if node == nil {
        return 0
    }
    return height(node.left) - height(node.right)
}

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

// InOrderTraversal performs in-order traversal of the tree
func (t *AVLTree) InOrderTraversal(node *Node) {
    if node != nil {
        t.InOrderTraversal(node.left)
        fmt.Printf("%d ", node.key)
        t.InOrderTraversal(node.right)
    }
}

func main() {
    avl := &AVLTree{}

    // Insert nodes into the AVL Tree
    for _, key := range []int{10, 20, 30, 40, 50, 25} {
        avl.Insert(key)
    }

    // Perform in-order traversal of the tree
    fmt.Println("In-order traversal of the AVL Tree:")
    avl.InOrderTraversal(avl.root)
    fmt.Println()
}
    

Explanation of the Code

Here’s a breakdown of the code:

  • Node Struct: The Node struct represents each node in the AVL Tree, including the key, height, and pointers to the left and right children.
  • AVLTree Struct: The AVLTree struct represents the AVL Tree itself, containing the root node.
  • Insert Method: This method inserts a new key into the AVL Tree. It calls the insert function, which recursively finds the correct position for the new key and then balances the tree.
  • LeftRotate and RightRotate Methods: These methods perform rotations on the tree to restore balance when the tree becomes unbalanced. Left rotation is performed when the right subtree is too tall, and right rotation is performed when the left subtree is too tall.
  • Balance Method: This method checks the balance factor of a node and performs the necessary rotations to keep the tree balanced. The balance factor is the difference in heights between the left and right subtrees.
  • Height and GetBalance Methods: These methods calculate the height of nodes and the balance factor, which are crucial for maintaining the AVL property.
  • InOrderTraversal Method: This method performs an in-order traversal of the tree, printing the nodes in sorted order.

Usage Example

Here’s an example of how you might use this AVL Tree implementation in a Go program:


func main() {
    avl := &AVLTree{}

    // Insert nodes into the AVL Tree
    for _, key := range []int{10, 20, 30, 40, 50, 25} {
        avl.Insert(key)
    }

    // Perform in-order traversal of the tree
    fmt.Println("In-order traversal of the AVL Tree:")
    avl.InOrderTraversal(avl.root)
    fmt.Println()
}
    

Conclusion

This Go program demonstrates a basic implementation of an AVL Tree, a self-balancing binary search tree that ensures O(log n) time complexity for insertion, deletion, and search operations. The AVL Tree is particularly useful in applications where balanced search trees are critical for maintaining efficient data retrieval and update operations.

 

By Aditya Bhuyan

I work as a cloud specialist. In addition to being an architect and SRE specialist, I work as a cloud engineer and developer. I have assisted my clients in converting their antiquated programmes into contemporary microservices that operate on various cloud computing platforms such as AWS, GCP, Azure, or VMware Tanzu, as well as orchestration systems such as Docker Swarm or Kubernetes. For over twenty years, I have been employed in the IT sector as a Java developer, J2EE architect, scrum master, and instructor. I write about Cloud Native and Cloud often. Bangalore, India is where my family and I call home. I maintain my physical and mental fitness by doing a lot of yoga and meditation.

Leave a Reply

Your email address will not be published. Required fields are marked *

error

Enjoy this blog? Please spread the word :)