How do I implement a generic AVL tree in Go?

In this tutorial, we'll explore how to implement a generic AVL tree in Go. An AVL tree is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes. This ensures that basic operations such as insertion, deletion, and lookup can be performed in O(log n) time. By making our AVL tree generic, we can allow it to hold values of any data type.

AVL Tree Implementation

Below is an example of a simple generic AVL tree implementation in Go:


        package main

        import (
            "fmt"
            "math"
            "sync"
        )

        type AVLNode[T any] struct {
            Key    T
            Height int
            Left   *AVLNode[T]
            Right  *AVLNode[T]
        }

        type AVLTree[T any] struct {
            root *AVLNode[T]
            mu   sync.RWMutex
        }

        func (n *AVLNode[T]) getHeight() int {
            if n == nil {
                return 0
            }
            return n.Height
        }

        func (tree *AVLTree[T]) insert(key T) {
            tree.mu.Lock()
            defer tree.mu.Unlock()
            tree.root = insertNode(tree.root, key)
        }

        func insertNode[T any](node *AVLNode[T], key T) *AVLNode[T] {
            if node == nil {
                return &AVLNode[T]{Key: key, Height: 1}
            }

            if key < node.Key {
                node.Left = insertNode(node.Left, key)
            } else if key > node.Key {
                node.Right = insertNode(node.Right, key)
            } else {
                return node // Duplicate keys are not allowed
            }

            node.Height = 1 + int(math.Max(float64(node.Left.getHeight()), float64(node.Right.getHeight())))

            balance := getBalance(node)

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

            return node
        }

        func getBalance[T any](node *AVLNode[T]) int {
            if node == nil {
                return 0
            }
            return node.Left.getHeight() - node.Right.getHeight()
        }

        func rightRotate[T any](y *AVLNode[T]) *AVLNode[T] {
            x := y.Left
            T2 := x.Right

            x.Right = y
            y.Left = T2

            y.Height = 1 + int(math.Max(float64(y.Left.getHeight()), float64(y.Right.getHeight())))
            x.Height = 1 + int(math.Max(float64(x.Left.getHeight()), float64(x.Right.getHeight())))

            return x
        }

        func leftRotate[T any](x *AVLNode[T]) *AVLNode[T] {
            y := x.Right
            T2 := y.Left

            y.Left = x
            x.Right = T2

            x.Height = 1 + int(math.Max(float64(x.Left.getHeight()), float64(x.Right.getHeight())))
            y.Height = 1 + int(math.Max(float64(y.Left.getHeight()), float64(y.Right.getHeight())))

            return y
        }
        
        func main() {
            tree := AVLTree[int]{}
            tree.insert(10)
            tree.insert(20)
            tree.insert(30)
            fmt.Println("AVL tree created and nodes inserted.")
        }

How do I implement a generic AVL tree in Go?

AVL Tree Implementation

Popular Topics

Recent Languages

How do I implement a generic AVL tree in Go?

AVL Tree Implementation

Related Questions

Popular Topics

Recent Languages