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_reader :data, :height, :left, :right
	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_reader :root
	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
	def addNode(node, data) 
		if (node == nil) 
			#  Return a new node
			return TreeNode.new(data)
		end

		if (data < node.data) 
			node.left = self.addNode(node.left, data)
		elsif (data > node.data) 
			node.right = self.addNode(node.right, 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()
	#  Add tree node
	tree.root = tree.addNode(tree.root, 4)
	tree.root = tree.addNode(tree.root, 7)
	tree.root = tree.addNode(tree.root, 5)
	tree.root = tree.addNode(tree.root, 19)
	tree.root = tree.addNode(tree.root, 17)
	tree.root = tree.addNode(tree.root, 13)
	tree.root = tree.addNode(tree.root, 11)
	tree.root = tree.addNode(tree.root, 3)
	tree.root = tree.addNode(tree.root, 2)
	tree.root = tree.addNode(tree.root, -3)
	#  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.

New Comment







© 2021, kalkicode.com, All rights reserved