AVL Tree Implementation in Ruby

1. Introduction

An AVL Tree (named after its inventors Adelson-Velsky and Landis) 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 the tree remains approximately balanced, leading to O(log n) search times.

2. Implementation Steps

1. Define a Node class with attributes value, left, right, and height.

2. Initialize an AVLTree class with a root node.

3. Implement the insert method to add nodes and ensure the tree remains balanced.

4. Implement rotation methods (rightRotate, leftRotate, leftRightRotate, rightLeftRotate) to balance the tree when required.

5. Implement a display method to print the tree in an in-order traversal.

3. Implementation in Ruby Programming

class Node
    attr_accessor :value, :left, :right, :height
    def initialize(value)
        @value = value
        @left = nil
        @right = nil
        @height = 1
    end
end
class AVLTree
    def initialize
        @root = nil
    end
    # Insert value into the AVL tree
    def insert(value)
        @root = insert_recursive(@root, value)
    end
    # Display AVL tree in in-order traversal
    def display
        display_recursive(@root)
    end
    private
    def height(node)
        return 0 if node.nil?
        node.height
    end
    def balance_factor(node)
        return 0 if node.nil?
        height(node.left) - height(node.right)
    end
    def rightRotate(y)
        x = y.left
        T3 = x.right
        x.right = y
        y.left = T3
        y.height = [height(y.left), height(y.right)].max + 1
        x.height = [height(x.left), height(x.right)].max + 1
        x
    end
    def leftRotate(x)
        y = x.right
        T2 = y.left
        y.left = x
        x.right = T2
        x.height = [height(x.left), height(x.right)].max + 1
        y.height = [height(y.left), height(y.right)].max + 1
        y
    end
    def insert_recursive(node, value)
        return Node.new(value) if node.nil?
        if value < node.value
            node.left = insert_recursive(node.left, value)
        elsif value > node.value
            node.right = insert_recursive(node.right, value)
        else
            return node
        end
        node.height = 1 + [height(node.left), height(node.right)].max
        balance = balance_factor(node)
        if balance > 1
            if value < node.left.value
                return rightRotate(node)
            else
                node.left = leftRotate(node.left)
                return rightRotate(node)
            end
        end
        if balance < -1
            if value > node.right.value
                return leftRotate(node)
            else
                node.right = rightRotate(node.right)
                return leftRotate(node)
            end
        end
        node
    end
    def display_recursive(node)
        return if node.nil?
        display_recursive(node.left)
        puts node.value
        display_recursive(node.right)
    end
end
# Client code
avl_tree = AVLTree.new
[10, 20, 30, 40, 50, 25].each { |i| avl_tree.insert(i) }
puts "In-order traversal of AVL tree:"
avl_tree.display

Output:

In-order traversal of AVL tree:
10
20
25
30
40
50

Explanation:

1. The Node class represents each element in the AVL tree. Each node has a value, left and right child, and a height.

2. The AVLTree class initializes with a root node set to nil.

3. The insert method adds a value to the tree, ensuring that the tree remains balanced.

4. Rotation methods (rightRotate, leftRotate, leftRightRotate, rightLeftRotate) are used to balance the tree during insertion when the balance factor deviates from the range [-1,1].

5. The private helper functions, including height, balance_factor, and display_recursive, facilitate AVL tree operations.

6. The client code demonstrates the insertion and display operations on the AVL tree.