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