Avl tree node insertion in golang

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

package main
import "fmt"
// Go program
// AVL Tree insertion

// Avl Tree Node
type TreeNode struct {
	data int
	height int
	left * TreeNode
	right * TreeNode
}
func getTreeNode(data int) * TreeNode {
	// Set node value of avl tree
	return &TreeNode {data,1,nil,nil}
}
type AvlTree struct {
	// Tree root node
	root * TreeNode
}
func getAvlTree() * AvlTree {
	
	// Set value of root
	return  &AvlTree {nil}
}
// Get the height of given node
func(this AvlTree) getHeight(node * TreeNode) int {
	if node == nil {
		return 0
	}
	return node.height
}
// Get the max value of given two numbers
func(this AvlTree) maxHeight(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}
// Perform the Right rotate operation
func(this *AvlTree) rightRotate(node * TreeNode) * TreeNode {
	// Get left child node
	var leftNode * TreeNode = node.left
	// Get left node right subtree
	var rightSubtree * TreeNode = leftNode.right
	// Update the left and right subtree
	leftNode.right = node
	node.left = rightSubtree
	// Change the height of modified node
	node.height = this.maxHeight(this.getHeight(node.left), this.getHeight(node.right)) + 1
	leftNode.height = this.maxHeight(this.getHeight(leftNode.left), this.getHeight(leftNode.right)) + 1
	return leftNode
}
// Perform the Left Rotate operation
func(this *AvlTree) leftRotate(node * TreeNode) * TreeNode {
	// Get right child node
	var rightNode * TreeNode = node.right
	// Get right node left subtree
	var leftSubtree * TreeNode = rightNode.left
	// Update the left and right subtree
	rightNode.left = node
	node.right = leftSubtree
	// Change the height of modified node
	node.height = this.maxHeight(this.getHeight(node.left), this.getHeight(node.right)) + 1
	rightNode.height = this.maxHeight(this.getHeight(rightNode.left), this.getHeight(rightNode.right)) + 1
	return rightNode
}
// Get the balance factor
func(this AvlTree) getBalanceFactor(node * TreeNode) int {
	if node == nil {
		return 0
	}
	return this.getHeight(node.left) - this.getHeight(node.right)
}
// Recursively, add a node in AVL tree
// Duplicate keys (data) are not allowed
func(this *AvlTree) addNode(node * TreeNode, data int) * TreeNode {
	if node == nil {
		// Return a new node
		return getTreeNode(data)
	}
	if data < node.data {
		node.left = this.addNode(node.left, data)
	} else if data > node.data {
		node.right = this.addNode(node.right, data)
	} else {
		// When given key data already exists
		return node
	}
	// Change the height of current node
	node.height = 1 + this.maxHeight(this.getHeight(node.left), this.getHeight(node.right))
	// Get balance factor of a node
	var factor int = this.getBalanceFactor(node)
	// LL Case
	if factor > 1 && data < node.left.data {
		return this.rightRotate(node)
	}
	// RR Case
	if factor < -1 && data > node.right.data {
		return this.leftRotate(node)
	}
	// LL Case
	if factor > 1 && data > node.left.data {
		node.left = this.leftRotate(node.left)
		return this.rightRotate(node)
	}
	// RR Case
	if factor < -1 && data < node.right.data {
		node.right = this.rightRotate(node.right)
		return this.leftRotate(node)
	}
	return node
}
// Print the tree in preorder form
func(this AvlTree) preorder(node * TreeNode) {
	if node != nil {
		fmt.Print("  ", node.data)
		this.preorder(node.left)
		this.preorder(node.right)
	}
}
// Print the tree in inorder form
func(this AvlTree) inorder(node * TreeNode) {
	if node != nil {
		this.inorder(node.left)
		fmt.Print("  ", node.data)
		this.inorder(node.right)
	}
}
// Print the tree in postorder form
func(this AvlTree) postorder(node * TreeNode) {
	if node != nil {
		this.postorder(node.left)
		this.postorder(node.right)
		fmt.Print("  ", node.data)
	}
}
func main() {
	var tree * AvlTree = getAvlTree()
	// 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
	*/
	fmt.Print("Resultant AVL Tree")
	fmt.Print("\nPreorder  :")
	tree.preorder(tree.root)
	fmt.Print("\nInorder   :")
	tree.inorder(tree.root)
	fmt.Print("\nPostorder :")
	tree.postorder(tree.root)
}

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