# Avl tree node insertion in ruby

Ruby program for Avl tree node insertion. Here problem description and other solutions.

``````#  Ruby program
#  AVL Tree insertion

#  Avl Tree Node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :height, :left, :right
def initialize(data)
#  Set node value of avl tree
self.data = data
self.height = 1
self.left = nil
self.right = nil
end

end

class AvlTree
# Define the accessor and reader of class AvlTree
attr_accessor :root
#  Tree root node
def initialize()
self.root = nil
end

#  Get the height of given node
def getHeight(node)
if (node == nil)
return 0
end
return node.height
end

#  Get the max value of given two numbers
def maxHeight(a, b)
if (a > b)
return a
else

return b
end

end

#  Perform the Right rotate operation
def rightRotate(node)
#  Get left child node
leftNode = node.left
#  Get left node right subtree
rightSubtree = leftNode.right
#  Update the left and right subtree
leftNode.right = node
node.left = rightSubtree
#  Change the height of modified node
node.height = self.maxHeight(
self.getHeight(node.left), self.getHeight(node.right)) + 1
leftNode.height = self.maxHeight(
self.getHeight(leftNode.left), self.getHeight(leftNode.right)) + 1
return leftNode
end

#  Perform the Left Rotate operation
def leftRotate(node)
#  Get right child node
rightNode = node.right
#  Get right node left subtree
leftSubtree = rightNode.left
#  Update the left and right subtree
rightNode.left = node
node.right = leftSubtree
#  Change the height of modified node
node.height = self.maxHeight(
self.getHeight(node.left), self.getHeight(node.right)) + 1
rightNode.height = self.maxHeight(
self.getHeight(rightNode.left),
self.getHeight(rightNode.right)) + 1
return rightNode
end

#  Get the balance factor
def getBalanceFactor(node)
if (node == nil)
return 0
end

return self.getHeight(node.left) - self.getHeight(node.right)
end

#  Recursively, add a node in AVL tree
#  Duplicate keys (data) are not allowed
if (node == nil)
#  Return a new node
return TreeNode.new(data)
end

if (data < node.data)
elsif (data > node.data)
else

#  When given key data already exists
return node
end

#  Change the height of current node
node.height = 1 + self.maxHeight(
self.getHeight(node.left), self.getHeight(node.right))
#  Get balance factor of a node
factor = self.getBalanceFactor(node)
#  LL Case
if (factor > 1 && data < node.left.data)
return self.rightRotate(node)
end

#  RR Case
if (factor < -1 && data > node.right.data)
return self.leftRotate(node)
end

#  LL Case
if (factor > 1 && data > node.left.data)
node.left = self.leftRotate(node.left)
return self.rightRotate(node)
end

#  RR Case
if (factor < -1 && data < node.right.data)
node.right = self.rightRotate(node.right)
return self.leftRotate(node)
end

return node
end

#  Print the tree in preorder form
def preorder(node)
if (node != nil)
print("  ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end

end

#  Print the tree in inorder form
def inorder(node)
if (node != nil)
self.inorder(node.left)
print("  ", node.data)
self.inorder(node.right)
end

end

#  Print the tree in postorder form
def postorder(node)
if (node != nil)
self.postorder(node.left)
self.postorder(node.right)
print("  ", node.data)
end

end

end

def main()
tree = AvlTree.new()
#  Resultant  AVL Tree
#  -----------------
#         7
#        /  \
#       /    \
#      4      17
#     / \     / \
#    2   5  13  19
#   / \     /
# -3   3   11
print("Resultant AVL Tree")
print("\nPreorder  :")
tree.preorder(tree.root)
print("\nInorder   :")
tree.inorder(tree.root)
print("\nPostorder :")
tree.postorder(tree.root)
end

main()``````

Output

``````Resultant AVL Tree
Preorder  :  7  4  2  -3  3  5  17  13  11  19
Inorder   :  -3  2  3  4  5  7  11  13  17  19
Postorder :  -3  3  2  5  4  11  13  19  17  7``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.