C++ implement RBTree(LLRBT version)


  • 0
    X
    class Solution {
        static const bool BLACK = false, RED = true;
        struct Node {
            long long key;
            Node *left, *right;
            size_t N;
            bool color;
            Node(long long k) : key(k), left(0), right(0), N(1), color(RED) { }
            ~Node() { delete left; delete right; }
        };
        void insert(long long key) {
            if (root) root->color = BLACK;
            root = insert(root, key);
        }
        size_t rank(long long key) const { return rank(root, key); }
        Node* insert(Node *x, long long key) {
            if (!x) return new Node(key);
            if (key < x->key) x->left = insert(x->left, key);
            else if (key > x->key) x->right = insert(x->right, key);
            ++x->N;
            if (is_red(x->right) && !is_red(x->left)) x = rotate_left(x);
            if (is_red(x->left) && is_red(x->left->left)) x = rotate_right(x);
            if (is_red(x->left) && is_red(x->right)) flip_color(x);
            return x;
        }
        size_t rank(const Node *x, long long key) const {
            if (!x) return 0;
            if (key >= x->key) return rank(x->right, key);
            return rank(x->left, key) + size(x) - size(x->left);
        }
        Node* rotate_left(Node *x) {
            auto y = x->right;
            size_t x_lt = size(x) - size(x->right);
            x->N = x->N - size(y) + size(y->left);
            y->N += x_lt;
            y->color = x->color;
            x->color = RED;
            x->right = y->left;
            y->left = x;
            return y;
        }
        Node* rotate_right(Node *x) {
            auto y = x->left;
            size_t x_rt = size(x) - size(x->left);
            x->N = x->N - size(y) + size(y->right);
            y->N += x_rt;
            y->color = x->color;
            x->color = RED;
            x->left = y->right;
            y->right = x;
            return y;
        }
        void flip_color(Node *x) {
            x->color = RED;
            x->left->color = x->right->color = BLACK;
        }
        size_t size(const Node *x) const {
            return x ? x->N : 0;
        }
        bool is_red(const Node *x) const {
            return x ? x->color : false;
        }
        Node *root = nullptr;
    public:
        int reversePairs(vector<int>& nums) {
            int ret = 0;
            for (long long num : nums) {
                ret += rank(2 * num);
                insert(num);
            }
            return ret;
        }
    };
    

Log in to reply
 

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