Count smaller elements on right side |  ; An AVL tree node ; size of the tree rooted with this node ; A utility function to get maximum of two integers ; A utility function to get height of the tree rooted with N ; A utility function to size of the tree of rooted with N ; 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 ; Perform rotation ; Update heights ; Update sizes ; Return new root ; A utility function to left rotate subtree rooted with x ; Perform rotation ; Update heights ; Update sizes ; Return new root ; Get Balance factor of node N ; Inserts a new key to the tree rotted with node . Also , updates * count to contain count of smaller elements for the new key ; 1. Perform the normal BST rotation ; UPDATE COUNT OF SMALLER ELEMENTS FOR KEY ; 2. Update height and size of this ancestor node ; 3. Get the balance factor of this ancestor node to check whether this node became unbalanced ; Left Left Case ; Right Right Case ; Left Right Case ; Right Left Case ; Return the ( unchanged ) node pointer ; The following function updates the countSmaller array to contain count of smaller elements on right side . ; Initialize all the counts in countSmaller array as 0 ; Starting from rightmost element , insert all elements one by one in an AVL tree and get the count of smaller elements ; Utility function that prints out an array on a line ; Driver code
#include <iostream> NEW_LINE using namespace std ; #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct node { int key ; struct node * left ; struct node * right ; int height ; int size ; } ; int max ( int a , int b ) ; int height ( struct node * N ) { if ( N == NULL ) return 0 ; return N -> height ; } int size ( struct node * N ) { if ( N == NULL ) return 0 ; return N -> size ; } int max ( int a , int b ) { return ( a > b ) ? a : b ; } struct node * newNode ( int key ) { struct node * node = ( struct node * ) malloc ( sizeof ( struct node ) ) ; node -> key = key ; node -> left = NULL ; node -> right = NULL ; node -> height = 1 ; node -> size = 1 ; return ( node ) ; } struct node * rightRotate ( struct node * y ) { struct node * x = y -> left ; struct 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 ; y -> size = size ( y -> left ) + size ( y -> right ) + 1 ; x -> size = size ( x -> left ) + size ( x -> right ) + 1 ; return x ; } struct node * leftRotate ( struct node * x ) { struct node * y = x -> right ; struct 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 ; x -> size = size ( x -> left ) + size ( x -> right ) + 1 ; y -> size = size ( y -> left ) + size ( y -> right ) + 1 ; return y ; } int getBalance ( struct node * N ) { if ( N == NULL ) return 0 ; return height ( N -> left ) - height ( N -> right ) ; } struct node * insert ( struct node * node , int key , int * count ) { if ( node == NULL ) return ( newNode ( key ) ) ; if ( key < node -> key ) node -> left = insert ( node -> left , key , count ) ; else { node -> right = insert ( node -> right , key , count ) ; * count = * count + size ( node -> left ) + 1 ; } node -> height = max ( height ( node -> left ) , height ( node -> right ) ) + 1 ; node -> size = size ( node -> left ) + size ( 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 ; } void constructLowerArray ( int arr [ ] , int countSmaller [ ] , int n ) { int i , j ; struct node * root = NULL ; for ( i = 0 ; i < n ; i ++ ) countSmaller [ i ] = 0 ; for ( i = n - 1 ; i >= 0 ; i -- ) { root = insert ( root , arr [ i ] , & countSmaller [ i ] ) ; } } void printArray ( int arr [ ] , int size ) { int i ; cout << " STRNEWLINE " ; for ( i = 0 ; i < size ; i ++ ) cout << arr [ i ] << " ▁ " ; } int main ( ) { int arr [ ] = { 10 , 6 , 15 , 20 , 30 , 5 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int * low = ( int * ) malloc ( sizeof ( int ) * n ) ; constructLowerArray ( arr , low , n ) ; cout << " Following ▁ is ▁ the ▁ constructed ▁ smaller ▁ count ▁ array " ; printArray ( low , n ) ; return 0 ; }