AVL tree | C++
Approach\n Describe your approach to solving the problem. \n\nMaintain two balanced binary tree. \n\n# Code\n\nstruct Node {\n\n    int key;\n    int size; \n  
# Approach\n<!-- Describe your approach to solving the problem. -->\n\nMaintain two balanced binary tree. \n\n# Code\n```\nstruct Node {\n\n    int key;\n    int size; \n    Node* left;\n    Node* right;\n\n    Node(int k, int s = 1, Node* l = nullptr, Node* r = nullptr)\n        : key(k), size(s), left(l), right(r) {}\n};\n\nclass BalancedTree {\nprivate:\n    Node* root;\n\n    void updateSize(Node* node) {\n        if (node != nullptr) {\n            node->size = getSize(node->left) + getSize(node->right) + 1;\n        }\n    }\n\n    Node* leftRotate(Node* x) {\n        Node* y = x->right;\n        x->right = y->left;\n        y->left = x;\n        updateSize(x);\n        updateSize(y);\n        return y;\n    }\n\n    Node* rightRotate(Node* y) {\n        Node* x = y->left;\n        y->left = x->right;\n        x->right = y;\n        updateSize(y);\n        updateSize(x);\n        return x;\n    }\n    \n    Node* insert(Node* node, int key) {\n        if (node == nullptr) {\n            return new Node(key);\n        }\n\n        if (key < node->key) {\n            node->left = insert(node->left, key);\n        } else {\n            node->right = insert(node->right, key);\n        }\n\n        updateSize(node);\n\n        int balance = getSize(node->left) - getSize(node->right);\n        if (balance > 1) {\n            return rightRotate(node);\n        } else if (balance < -1) {\n            return leftRotate(node);\n        }\n\n        return node;\n    }\n    \n\n    int greaterCount(Node* node, int key) {\n        if (node == nullptr) {\n            return 0;\n        }\n\n        if (key < node->key) {\n            return getSize(node->right) + 1 + greaterCount(node->left, key);\n        } else {\n            return greaterCount(node->right, key);\n        }\n    }   \n    \n    int getSize(Node* node) {\n        return (node != nullptr) ? node->size : 0;\n    }\n\npublic:\n    BalancedTree() : root(nullptr) {}\n    \n    void insert(int key) {\n        root = insert(root, key);\n    }\n\n    int greatorCount(int key) {\n        return greaterCount(root, key);\n    }\n    \n    int getSize() {\n        return getSize(root);\n    }\n\n};\n\nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        int n = nums.size();\n        if(n == 1) return nums;\n        vector<int> arr1, arr2;\n        BalancedTree tree1, tree2;\n        \n        arr1.push_back(nums[0]);\n        arr2.push_back(nums[1]);\n        tree1.insert(nums[0]);\n        tree2.insert(nums[1]);\n        for(int i = 2; i < n; i ++) {\n            int cnt1 = tree1.greatorCount(nums[i]);\n            int cnt2 = tree2.greatorCount(nums[i]);\n            // cout << cnt1 << " " << cnt2 << endl;\n            if(cnt1 > cnt2) {\n                arr1.push_back(nums[i]);\n                tree1.insert(nums[i]);\n            } else if(cnt1 < cnt2) {\n                arr2.push_back(nums[i]);\n                tree2.insert(nums[i]);\n            } else {\n                int size1 = tree1.getSize(), size2 = tree2.getSize();\n                // cout << " " << size1 << " " << size2 << endl;\n                if(size1 > size2) {\n                    arr2.push_back(nums[i]);\n                    tree2.insert(nums[i]);\n                } else {\n                    arr1.push_back(nums[i]);\n                    tree1.insert(nums[i]);\n                }\n            }\n        }\n        arr1.insert(arr1.end(), arr2.begin(), arr2.end());\n        return arr1;\n    }\n};\n```
['C++']