AVL Trees (Adelson-Velsky and Landis Trees)
AVL trees are self-balancing binary search trees designed to maintain balance during insertions and deletions. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. This ensures that the tree remains balanced, which helps in maintaining efficient search, insertion, and deletion operations.
Balancing Operations
AVL trees employ rotation operations to maintain balance. There are four types of rotations:
- Left rotation
- Right rotation
- Left-right rotation (also known as double rotation)
- Right-left rotation (also known as double rotation)
Insertion
When inserting a new node into an AVL tree, the tree may become unbalanced. To restore balance, rotation operations are performed as necessary.
Deletion
Similarly, when deleting a node from an AVL tree, the tree may become unbalanced. Rotation operations are employed to restore balance in this scenario as well.
Below is the Ruby program to implement AVL Tree:
class AVLNode
attr_accessor :value, :left, :right, :height
def initialize(value)
@value = value
@left = nil
@right = nil
@height = 1
end
end
class AVLTree
attr_reader :root
def initialize
@root = nil
end
def insert(value)
@root = insert_node(@root, value)
end
def inorder_traversal(node = @root)
return unless node
inorder_traversal(node.left)
puts node.value
inorder_traversal(node.right)
end
private
def insert_node(node, value)
return AVLNode.new(value) unless node
if value < node.value
node.left = insert_node(node.left, value)
else
node.right = insert_node(node.right, value)
end
node.height = [height(node.left), height(node.right)].max + 1
balance = balance_factor(node)
# Perform rotations if the node becomes unbalanced
if balance > 1 && value < node.left.value
return right_rotate(node)
end
if balance < -1 && value > node.right.value
return left_rotate(node)
end
if balance > 1 && value > node.left.value
node.left = left_rotate(node.left)
return right_rotate(node)
end
if balance < -1 && value < node.right.value
node.right = right_rotate(node.right)
return left_rotate(node)
end
node
end
def height(node)
return 0 unless node
node.height
end
def balance_factor(node)
return 0 unless node
height(node.left) - height(node.right)
end
def right_rotate(y)
x = y.left
t2 = x.right
x.right = y
y.left = t2
y.height = [height(y.left), height(y.right)].max + 1
x.height = [height(x.left), height(x.right)].max + 1
x
end
def left_rotate(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
end
avl_tree = AVLTree.new
avl_tree.insert(10)
avl_tree.insert(20)
avl_tree.insert(30)
avl_tree.insert(40)
avl_tree.insert(50)
avl_tree.insert(25)
puts "In-order traversal of AVL tree:"
avl_tree.inorder_traversal
Output:
How to Implement Data Structures in Ruby?
Data structures are fundamental components of any programming language, allowing developers to organize and manipulate data efficiently. In Ruby, a versatile and expressive language, implementing various data structures is straightforward. In this article, we’ll explore how to implement common data structures such as arrays, linked lists, stacks, queues, trees, graphs, and hashmaps in Ruby. The article focuses on discussing data structures in Ruby.
Table of Content
- Singly-Linked Lists
- Doubly-Linked Lists
- Circular Linked Lists
- Queues
- Stack
- Hash Tables
- Sets
- Binary Trees
- AVL Trees (Adelson-Velsky and Landis Trees)
- Graphs
- Persistent Lists