Editorial Staff - - Java Programming
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
