AVL with duplicate keys | Java program of AVL tree that handles duplicates ; An AVL tree node ; A utility function to get height of the tree ; A utility function to get maximum of two integers ; Helper function that allocates a new node with the given key and null left and right pointers . ; new node is initially added at leaf ; A utility function to right rotate subtree rooted with y See the diagram given above . ; Perform rotation ; Update heights ; Return new root ; A utility function to left rotate subtree rooted with x See the diagram given above . ; Perform rotation ; Update heights ; Return new root ; Get Balance factor of node N ; 1. Perform the normal BST rotation ; If key already exists in BST , increment count and return ; Otherwise , recur down the tree ; 2. Update height of this ancestor node ; 3. Get the balance factor of this ancestor node to check whether this node became unbalanced ; If this node becomes unbalanced , then there are 4 cases Left Left Case ; Right Right Case ; Left Right Case ; Right Left Case ; return the ( unchanged ) node pointer ; Given a non - empty binary search tree , return the node with minimum key value found in that tree . Note that the entire tree does not need to be searched . ; loop down to find the leftmost leaf ; STEP 1 : PERFORM STANDARD BST DELETE ; If the key to be deleted is smaller than the root 's key,  then it lies in left subtree ; If the key to be deleted is greater than the root 's key,  then it lies in right subtree ; if key is same as root 's key, then This is the node  to be deleted ; If key is present more than once , simply decrement count and return ; ElSE , delete the node node with only one child or no child ; No child case ; One child case ; Copy the contents of the non - empty child ; node with two children : Get the inorder successor ( smallest in the right subtree ) ; Copy the inorder successor 's data to this node and update the count ; Delete the inorder successor ; If the tree had only one node then return ; STEP 2 : UPDATE HEIGHT OF THE CURRENT NODE ; STEP 3 : GET THE BALANCE FACTOR OF THIS NODE ( to check whether this node became unbalanced ) ; If this node becomes unbalanced , then there are 4 cases Left Left Case ; Left Right Case ; Right Right Case ; Right Left Case ; A utility function to print preorder traversal of the tree . The function also prints height of every node ; Driver program to test above function ; Coning tree given in the above figure
import java . util . * ; class solution { static class node { int key ; node left ; node right ; int height ; int count ; } static int height ( node N ) { if ( N == null ) return 0 ; return N . height ; } static int max ( int a , int b ) { return ( a > b ) ? a : b ; } static node newNode ( int key ) { node node = new node ( ) ; node . key = key ; node . left = null ; node . right = null ; node . height = 1 ; node . count = 1 ; return ( node ) ; } static 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 ; } static 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 ; } static int getBalance ( node N ) { if ( N == null ) return 0 ; return height ( N . left ) - height ( N . right ) ; } static node insert ( node node , int key ) { if ( node == null ) return ( newNode ( key ) ) ; if ( key == node . key ) { ( node . count ) ++ ; return node ; } if ( key < node . key ) node . left = insert ( node . left , key ) ; else node . right = insert ( node . right , key ) ; node . height = max ( height ( node . left ) , height ( node . right ) ) + 1 ; 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 ; } static node minValueNode ( node node ) { node current = node ; while ( current . left != null ) current = current . left ; return current ; } static node deleteNode ( node root , int key ) { if ( root == null ) return root ; if ( key < root . key ) root . left = deleteNode ( root . left , key ) ; else if ( key > root . key ) root . right = deleteNode ( root . right , key ) ; else { if ( root . count > 1 ) { ( root . count ) -- ; return null ; } if ( ( root . left == null ) || ( root . right == null ) ) { node temp = root . left != null ? root . left : root . right ; if ( temp == null ) { temp = root ; root = null ; } else root = temp ; } else { node temp = minValueNode ( root . right ) ; root . key = temp . key ; root . count = temp . count ; temp . count = 1 ; root . right = deleteNode ( root . right , temp . key ) ; } } if ( root == null ) return root ; root . height = max ( height ( root . left ) , height ( root . right ) ) + 1 ; int balance = getBalance ( root ) ; if ( balance > 1 && getBalance ( root . left ) >= 0 ) return rightRotate ( root ) ; if ( balance > 1 && getBalance ( root . left ) < 0 ) { root . left = leftRotate ( root . left ) ; return rightRotate ( root ) ; } if ( balance < - 1 && getBalance ( root . right ) <= 0 ) return leftRotate ( root ) ; if ( balance < - 1 && getBalance ( root . right ) > 0 ) { root . right = rightRotate ( root . right ) ; return leftRotate ( root ) ; } return root ; } static void preOrder ( node root ) { if ( root != null ) { System . out . printf ( " % d ( % d ) ▁ " , root . key , root . count ) ; preOrder ( root . left ) ; preOrder ( root . right ) ; } } public static void main ( String args [ ] ) { node root = null ; root = insert ( root , 9 ) ; root = insert ( root , 5 ) ; root = insert ( root , 10 ) ; root = insert ( root , 5 ) ; root = insert ( root , 9 ) ; root = insert ( root , 7 ) ; root = insert ( root , 17 ) ; System . out . printf ( "Pre order traversal of the constructed AVL tree is NEW_LINE"); preOrder ( root ) ; deleteNode ( root , 9 ) ; System . out . printf ( " Pre order traversal after deletion of 9 "); preOrder ( root ) ; } }