A stupid AVL solution O(nlog(n)) . too much coding~


  • 1
    A

    The basic idea is do a insert from right most element in nums to the left most element.

    At each insert(nums[i]), when we go right of the AVL tree, we add the count at root and size of left subtree. the sum is the val at res[i];

    Three different point to a vanilla AVL tree.

    1. No delete need. So I make the node destructer delete its left and right.
    2. Add a subtree size field at each node, when we do rotate, we need to consider that.
    3. Add a count file at each node as there may be element in nums has same value.

    This is not a smart solution. And R-B tree should be batter for this use case. Just a practice for coding.

    BTW. I tired regular BST, the run time is the same as this one. Should more test case be added to make regular BST to be TLE?

    Should OJ add the window size, So I can prictice the AVL or R-B tree delete?

    struct node {
        int val;    // value
        int height; // height of this node
        int count;  // number of num at this node
        int size;   // number of num at this subtree 
        node* left, *right;
        node(int v): val(v), height(1), size(1), left(NULL), right(NULL), count(1) {}
        ~node() {
            if (left) delete left;
            if (right) delete right;
        }
    };
    
    class tree {
        node *root;
        int count;
        int height(node *cur) {
            if (cur) {
                return cur->height;
            }
            return 0;
        }
        int balance(node *cur) {
            if (cur)
                return height(cur->left) - height(cur->right);
            return 0;
        }
        int size(node *cur) {
            if (cur) {
                return cur->size;
            }
            return 0;
        }
        node *right_r (node *p) {
            node *c = p->left;
            p->left = c->right;
            c->right = p;
            // height balance;
            p->height = 1 + max(height(p->left), height(p->right));
            c->height = 1 + max(height(c->left), height(c->right));
            // size recal;
            int all = p->size;
            p->size -= c->count + size(c->left);
            c->size = all;
            return c;
        }
        node *left_r(node *p) {
            node *c = p->right;
            p->right = c->left;
            c->left = p;
            
            p->height = 1 + max(height(p->left), height(p->right));
            c->height = 1 + max(height(c->left), height(c->right));
            // size recal;
            int all = p->size;
            p->size -= c->count + size(c->right);
            c->size = all;
            return c;
        }
        node *insert_rec(node* cur, int val) {
            if (cur==NULL) {
                return new node(val);
            }
            cur->size++;
            if (val < cur->val) {
                cur->left = insert_rec(cur->left, val);
            } else if (cur->val < val) {
                cur->right = insert_rec(cur->right,val);
                count+=cur->count + size(cur->left);
            } else {
                cur->count++;
                count += size(cur->left);
                return cur;
            }
            cur->height = 1 + max(height(cur->left), height(cur->right));
            int b = balance(cur);
            if (b>1) {
                if (val < cur->val) {
                    return right_r(cur);
                } else {
                    cur->left = left_r(cur->left);
                    return right_r(cur);
                }
            } else if (b<-1) {
                if (cur->val < val) {
                    return left_r(cur);
                } else {
                    cur->right = right_r(cur->right);
                    return left_r(cur);
                }
            }
            return cur;
        }
    public:
        tree(): root(NULL) {}
        ~tree() {
            delete root;
        }
        int insert(int val) {
            count = 0;
            root = insert_rec(root, val);
            return count;
        }
    };
    
    class Solution {
        tree avl_tree;
    public:
        vector<int> countSmaller(vector<int>& nums) {
            int n = nums.size();
            vector<int> res(n);
            if (n==0) return res;
            for (int i = n-1; i>=0; --i) {
                res[i] = avl_tree.insert(nums[i]);
            }
            return res;
        }
    };

  • 0
    S

    Decent code, and should the condition for rotation be modified?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.