# 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.