Question

How do you implement an AVL tree for strings in Java?

Answer 1

//Java program for AVL Tree

class TreeNode {
String key;
int height;
TreeNode left, right;
  
TreeNode(String d) {
key = d;
height = 1;
}
}
  
class AVLTree {
  
TreeNode root;
  
int nodeHeight(TreeNode N) {
if (N == null)
return 0;
  
return N.height;
}
  
int maximum(int a, int b) {
return (a > b) ? a : b;
}
  
TreeNode rotateLeft(TreeNode x) {
   TreeNode y = x.right;
   TreeNode T2 = y.left;
y.left = x;
x.right = T2;
x.height = maximum(nodeHeight(x.left), nodeHeight(x.right)) + 1;
y.height = maximum(nodeHeight(y.left), nodeHeight(y.right)) + 1;
  
return y;
}
  
int getBalanceFactor(TreeNode N) {
if (N == null)
return 0;
  
return nodeHeight(N.left) - nodeHeight(N.right);
}
  
TreeNode rotateRight(TreeNode y) {
   TreeNode x = y.left;
   TreeNode T2 = x.right;
  
x.right = y;
y.left = T2;
  
y.height = maximum(nodeHeight(y.left), nodeHeight(y.right)) + 1;
x.height = maximum(nodeHeight(x.left), nodeHeight(x.right)) + 1;
  
return x;
}
  
  
  
TreeNode insertNode(TreeNode node, String key) {
  
if (node == null) return (new TreeNode(key));
  
if (key.compareTo(node.key) < 0)
node.left = insertNode(node.left, key);
else if (key.compareTo(node.key) > 0)
node.right = insertNode(node.right, key);
else
return node;
node.height = 1 + maximum(nodeHeight(node.left),nodeHeight(node.right));
  
int balance = getBalanceFactor(node);
if (balance > 1 && key.compareTo(node.left.key) < 0)
return rotateRight(node);
  
if (balance < -1 && key.compareTo(node.right.key) > 0)
return rotateLeft(node);
  
if (balance > 1 && key.compareTo(node.left.key) > 0) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
  
if (balance < -1 && key.compareTo(node.right.key) < 0) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
  
return node;
}
void inOrder(TreeNode node) {
if (node != null) {
   inOrder(node.left);
System.out.print(node.key + " ");
inOrder(node.right);
}
}
  
public static void main(String[] args) {
AVLTree AVLtree = new AVLTree();
  
AVLtree.root = AVLtree.insertNode(AVLtree.root, "Banana");
AVLtree.root = AVLtree.insertNode(AVLtree.root, "Orange");
AVLtree.root = AVLtree.insertNode(AVLtree.root, "Apple");
AVLtree.root = AVLtree.insertNode(AVLtree.root, "mango");
AVLtree.root = AVLtree.insertNode(AVLtree.root, "Grapes");
AVLtree.root = AVLtree.insertNode(AVLtree.root, "Guava");
  
System.out.println("INorder traversal : ");
AVLtree.inOrder(AVLtree.root);
}
}