In this program, we are going to share a Java program for insertion in AVL Tree with the output. If you are a Java beginner and want to start learning the Java programming, then keep your close attention in this tutorial as I am going to share how to write a java program for insertion in AVL Tree.
Copy the below Java program and execute it with the help of Javac compiler.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
class Node { int key, height; Node left, right; Node(int d) { key = d; height = 1; } } class AVLTree { Node root; int height(Node N) { if (N == null) return 0; return N.height; } int max(int a, int b) { return (a > b) ? a : b; } Node rightRotate(Node y) { Node x = y.left; Node T2 = x.right; x.right = y; y.left = T2; y.height = max(height(y.left), height(y.right)) + 1; x.height = max(height(x.left), height(x.right)) + 1; return x; } Node leftRotate(Node x) { Node y = x.right; Node T2 = y.left; y.left = x; x.right = T2; x.height = max(height(x.left), height(x.right)) + 1; y.height = max(height(y.left), height(y.right)) + 1; return y; } int getBalance(Node N) { if (N == null) return 0; return height(N.left) - height(N.right); } Node insert(Node node, int key) { if (node == null) return (new Node(key)); if (key < node.key) node.left = insert(node.left, key); else if (key > node.key) node.right = insert(node.right, key); else // Duplicate keys not allowed return node; node.height = 1 + max(height(node.left), height(node.right)); int balance = getBalance(node); if (balance > 1 && key < node.left.key) return rightRotate(node); if (balance < -1 && key > node.right.key) return leftRotate(node); if (balance > 1 && key > node.left.key) { node.left = leftRotate(node.left); return rightRotate(node); } if (balance < -1 && key < node.right.key) { node.right = rightRotate(node.right); return leftRotate(node); } return node; } void preOrder(Node node) { if (node != null) { System.out.print(node.key + " "); preOrder(node.left); preOrder(node.right); } } public static void main(String[] args) { AVLTree tree = new AVLTree(); tree.root = tree.insert(tree.root, 10); tree.root = tree.insert(tree.root, 20); tree.root = tree.insert(tree.root, 30); tree.root = tree.insert(tree.root, 40); tree.root = tree.insert(tree.root, 50); tree.root = tree.insert(tree.root, 25); System.out.println("Preorder traversal" + " of constructed tree is : "); tree.preOrder(tree.root); } } |
Preorder traversal of the constructed AVL tree is
30 20 10 25 40 50
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
