Question

AVL tree; Insert and Range Minimum operation in Java code.

Answer 1

1.) INSERTION

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 
            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); 
    } 
} 

2.) Range minimum

class SegmentTreeRMQ 
{ 
    int st[]; 
  
   
    int minVal(int x, int y) { 
        return (x < y) ? x : y; 
    } 
  
  
    int getMid(int s, int e) { 
        return s + (e - s) / 2; 
    } 
  
   
      
    int RMQUtil(int ss, int se, int qs, int qe, int index) 
    { 
       
        if (qs <= ss && qe >= se) 
            return st[index]; 
  
       
        if (se < qs || ss > qe) 
            return Integer.MAX_VALUE; 
  
         
        int mid = getMid(ss, se); 
        return minVal(RMQUtil(ss, mid, qs, qe, 2 * index + 1), 
                RMQUtil(mid + 1, se, qs, qe, 2 * index + 2)); 
    } 
  
  
    int RMQ(int n, int qs, int qe) 
    { 
        
        if (qs < 0 || qe > n - 1 || qs > qe) { 
            System.out.println("Invalid Input"); 
            return -1; 
        } 
  
        return RMQUtil(0, n - 1, qs, qe, 0); 
    } 
  
    
    int constructSTUtil(int arr[], int ss, int se, int si) 
    { 
       
        if (ss == se) { 
            st[si] = arr[ss]; 
            return arr[ss]; 
        } 
  
        int mid = getMid(ss, se); 
        st[si] = minVal(constructSTUtil(arr, ss, mid, si * 2 + 1), 
                constructSTUtil(arr, mid + 1, se, si * 2 + 2)); 
        return st[si]; 
    } 
  
   
    void constructST(int arr[], int n) 
    { 
        int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 
  
      
        int max_size = 2 * (int) Math.pow(2, x) - 1; 
        st = new int[max_size]; 
  
       
        constructSTUtil(arr, 0, n - 1, 0); 
    } 
  
   
    public static void main(String args[])  
    { 
        int arr[] = {1, 3, 2, 7, 9, 11}; 
        int n = arr.length; 
        SegmentTreeRMQ tree = new SegmentTreeRMQ(); 
  
       
        tree.constructST(arr, n); 
  
        int qs = 1;  
        int qe = 5; 
  
        
        System.out.println("Minimum of values in range [" + qs + ", "
                           + qe + "] is = " + tree.RMQ(n, qs, qe)); 
    } 
}