Avl tree node insertion in python

Python program for Avl tree node insertion. Here problem description and explanation.

#  Python 3 program
#  AVL Tree insertion

#  Avl Tree Node
class TreeNode :
	def __init__(self, data) :
		#  Set node value of avl tree
		self.data = data
		self.height = 1
		self.left = None
		self.right = None
	

class AvlTree :
	#  Tree root node
	def __init__(self) :
		self.root = None
	
	#  Get the height of given node
	def getHeight(self, node) :
		if (node == None) :
			return 0
		
		return node.height
	
	#  Get the max value of given two numbers
	def maxHeight(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	#  Perform the Right rotate operation
	def rightRotate(self, 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
	
	#  Perform the Left Rotate operation
	def leftRotate(self, 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
	
	#  Get the balance factor
	def getBalanceFactor(self, node) :
		if (node == None) :
			return 0
		
		return self.getHeight(node.left) - self.getHeight(node.right)
	
	#  Recursively, add a node in AVL tree
	#  Duplicate keys (data) are not allowed
	def addNode(self, node, data) :
		if (node == None) :
			#  Return a new node
			return TreeNode(data)
		
		if (data < node.data) :
			node.left = self.addNode(node.left, data)
		elif (data > node.data) :
			node.right = self.addNode(node.right, data)
		else :
			#  When given key data already exists
			return node
		
		#  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 and data < node.left.data) :
			return self.rightRotate(node)
		
		#  RR Case
		if (factor < -1 and data > node.right.data) :
			return self.leftRotate(node)
		
		#  LL Case
		if (factor > 1 and data > node.left.data) :
			node.left = self.leftRotate(node.left)
			return self.rightRotate(node)
		
		#  RR Case
		if (factor < -1 and data < node.right.data) :
			node.right = self.rightRotate(node.right)
			return self.leftRotate(node)
		
		return node
	
	#  Print the tree in preorder form
	def preorder(self, node) :
		if (node != None) :
			print("  ", node.data, end = "")
			self.preorder(node.left)
			self.preorder(node.right)
		
	
	#  Print the tree in inorder form
	def inorder(self, node) :
		if (node != None) :
			self.inorder(node.left)
			print("  ", node.data, end = "")
			self.inorder(node.right)
		
	
	#  Print the tree in postorder form
	def postorder(self, node) :
		if (node != None) :
			self.postorder(node.left)
			self.postorder(node.right)
			print("  ", node.data, end = "")
		
	

def main() :
	tree = AvlTree()
	#  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("Preorder  :", end = "")
	tree.preorder(tree.root)
	print("\nInorder   :", end = "")
	tree.inorder(tree.root)
	print("\nPostorder :", end = "")
	tree.postorder(tree.root)

if __name__ == "__main__": 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