AVL Tree Rebalancing Algorithm Implementation in the Hello-Algo Repository

The hello-algo AVL tree detects imbalance using balance factors of +2 or -2, then restores balance through four specific rotation patterns: LL (single right), RR (single left), LR (double left-right), and RL (double right-left), maintaining O(log n) height after every insertion and deletion.

The krahets/hello-algo repository provides a comprehensive Go implementation of self-balancing binary search trees in its tree chapter. Located in codes/go/chapter_tree/avl_tree.go, this code demonstrates the classic AVL tree rebalancing algorithm with explicit height management and distinct rotation cases. The implementation relies on a generic TreeNode structure defined in codes/go/pkg/tree_node.go to store values, child pointers, and cached heights for O(1) balance factor calculation.

Height Management and Balance Factor Calculation

The foundation of AVL rebalancing rests on accurate height tracking and balance factor computation. The implementation provides three core helper methods in avl_tree.go to manage these properties efficiently.

The height() function returns -1 for nil nodes and 0 for leaf nodes, establishing a consistent base case for height calculations. Following any structural change, updateHeight() recomputes a node's cached height as the maximum of its children's heights plus one. Finally, balanceFactor() calculates the difference between left and right subtree heights using height(left) - height(right). When this factor reaches +2 or -2, the subtree requires rebalancing through rotation.

// From codes/go/chapter_tree/avl_tree.go
func (t *aVLTree) height(node *TreeNode) int {
    if node == nil {
        return -1
    }
    return node.Height
}

func (t *aVLTree) updateHeight(node *TreeNode) {
    leftHeight := t.height(node.Left)
    rightHeight := t.height(node.Right)
    if leftHeight > rightHeight {
        node.Height = leftHeight + 1
    } else {
        node.Height = rightHeight + 1
    }
}

func (t *aVLTree) balanceFactor(node *TreeNode) int {
    if node == nil {
        return 0
    }
    return t.height(node.Left) - t.height(node.Right)
}

The Four Rotation Patterns for AVL Rebalancing

The rotate() method (lines 78-107 in avl_tree.go) implements the core rebalancing logic by detecting which of the four imbalance cases has occurred and applying the corresponding rotation sequence. This function returns the new subtree root after balancing, ensuring that parent pointers can be updated during recursive traversal.

Single Rotations (LL and RR Cases)

Right rotation handles the LL case (Left-Left), where the balance factor is +2 and the left child's balance factor is non-negative. The rightRotate() function (lines 50-62) pivots on the left child, moving the current node down to become the right child, and promotes the left child to the subtree root.

Left rotation handles the RR case (Right-Right), where the balance factor is -2 and the right child's balance factor is non-positive. The leftRotate() function (lines 64-76) performs the mirror operation, pivoting on the right child and moving the current node down to become the left child.

Both rotation functions explicitly call updateHeight() on the rotated nodes to maintain correct height information before returning the new subtree root.

// Right rotation for LL case
func (t *aVLTree) rightRotate(node *TreeNode) *TreeNode {
    child := node.Left
    grandChild := child.Right
    child.Right = node
    node.Left = grandChild
    t.updateHeight(node)
    t.updateHeight(child)
    return child
}

// Left rotation for RR case  
func (t *aVLTree) leftRotate(node *TreeNode) *TreeNode {
    child := node.Right
    grandChild := child.Left
    child.Left = node
    node.Right = grandChild
    t.updateHeight(node)
    t.updateHeight(child)
    return child
}

Double Rotations (LR and RL Cases)

Left-Right (LR) rotation handles the case where the balance factor is +2 but the left child's balance factor is -1 (indicating the left subtree leans right). The implementation first applies a leftRotate() on node.Left, converting the structure into an LL case, then applies a rightRotate() on the original node.

Right-Left (RL) rotation handles the mirror case where the balance factor is -2 but the right child's balance factor is +1. The code applies a rightRotate() on node.Right followed by a leftRotate() on the original node. These double rotations restore balance while maintaining the binary search tree ordering invariant.

// Core rebalancing logic from rotate()
func (t *aVLTree) rotate(node *TreeNode) *TreeNode {
    bf := t.balanceFactor(node)
    
    // Left-heavy cases
    if bf > 1 {
        if t.balanceFactor(node.Left) >= 0 {
            // LL case: single right rotation
            return t.rightRotate(node)
        } else {
            // LR case: left rotation on child, then right on node
            node.Left = t.leftRotate(node.Left)
            return t.rightRotate(node)
        }
    }
    
    // Right-heavy cases  
    if bf < -1 {
        if t.balanceFactor(node.Right) <= 0 {
            // RR case: single left rotation
            return t.leftRotate(node)
        } else {
            // RL case: right rotation on child, then left on node
            node.Right = t.rightRotate(node.Right)
            return t.leftRotate(node)
        }
    }
    
    return node // Already balanced
}

Rebalancing During Insertion and Deletion

The AVL tree maintains its balance invariant through post-operation rebalancing. Both insertion and deletion use recursive helper functions that retrace the path back to the root, updating heights and applying rotations at each level.

The insertHelper() method performs standard BST insertion, then calls updateHeight() and rotate() on the return path. This ensures that any imbalance caused by the new node is corrected before the recursive stack unwinds, guaranteeing that every ancestor node remains balanced. Similarly, removeHelper() handles the three standard BST deletion cases (leaf, single child, two children), then applies the same height-update and rotation sequence to restore AVL properties throughout the affected path.

func (t *aVLTree) insertHelper(node *TreeNode, val int) *TreeNode {
    if node == nil {
        return NewTreeNode(val)
    }
    
    if val < node.Val.(int) {
        node.Left = t.insertHelper(node.Left, val)
    } else if val > node.Val.(int) {
        node.Right = t.insertHelper(node.Right, val)
    }
    
    t.updateHeight(node)
    return t.rotate(node) // Rebalance if necessary
}

Practical Implementation Example

The following example demonstrates the complete workflow: building an AVL tree through insertions, performing a deletion that triggers rebalancing, and searching for specific values. The PrintTree utility from codes/go/pkg/print_utils.go visualizes the tree structure after each operation.

package main

import (
	"fmt"
	. "github.com/krahets/hello-algo/pkg"
	. "github.com/krahets/hello-algo/codes/go/chapter_tree"
)

func main() {
	avl := newAVLTree()
	
	// Insert values that would unbalance a standard BST
	for _, v := range []int{1, 2, 3, 4, 5, 8, 7, 9, 10, 6} {
		avl.insert(v)
	}
	fmt.Println("Tree after inserts:")
	PrintTree(avl.root)

	// Delete node with two children (triggers rebalancing)
	avl.remove(5)
	fmt.Println("\nTree after deleting 5:")
	PrintTree(avl.root)

	// Search operation
	if n := avl.search(7); n != nil {
		fmt.Printf("\nFound node %d with height %d\n", n.Val.(int), n.Height)
	}
}

Summary

• The AVL implementation in codes/go/chapter_tree/avl_tree.go uses cached heights and balance factors to detect imbalance in O(1) time.
• Four rotation cases (LL, LR, RR, RL) restore balance while maintaining BST properties, implemented in the rotate() method.
• Single rotations (rightRotate, leftRotate) handle LL and RR cases by promoting the heavy child to root.
• Double rotations combine two single rotations to handle LR and RL cases where the heavy child leans in the opposite direction.
• Insertion and deletion automatically trigger rebalancing through post-order height updates and recursive rotation calls, ensuring the tree maintains O(log n) height.

Frequently Asked Questions

How does the implementation detect when an AVL tree needs rebalancing?

The code calculates the balance factor for every node during the recursive return path of insertion or deletion. If balanceFactor() returns +2 (left-heavy) or -2 (right-heavy), the rotate() method is invoked to restore balance. Factors of -1, 0, or 1 indicate the node is already balanced and requires no adjustment.

What is the difference between single and double rotations in this implementation?

Single rotations (right or left) handle LL and RR cases where the imbalance occurs along a straight line (grandchild is outer). Double rotations handle LR and RL cases where the imbalance forms a zigzag (grandchild is inner). The implementation executes double rotations as two sequential single rotations: first on the child to convert the case to LL/RR, then on the original node.

Where is the TreeNode structure defined, and what fields does it contain?

The TreeNode structure is defined in codes/go/pkg/tree_node.go. It contains four fields: Val (interface{} for the stored value), Left (*TreeNode pointer), Right (*TreeNode pointer), and Height (int). The height field is crucial for the AVL rebalancing algorithm, allowing O(1) balance factor calculation without recursing through subtrees.

Does the AVL tree implementation support duplicate values?

According to the source code in avl_tree.go, the insertHelper() method uses strict comparison operators (< and >) rather than <= or >=. This means duplicate values are ignored during insertion—the recursive path stops when val == node.Val.(int) and returns the existing node without modification. For applications requiring duplicate support, the comparison logic would need modification to use <= for left insertion.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}