左偏红黑树

左偏红黑树的 cpp 简单实现

---

左偏红黑树实现的 multiset

支持：

• 插入 / 删除一个元素
• 查询元素数量
• 查找前驱 / 后继
• 查询第 k 大元素
• 查询元素排名

#ifndef __LLRE_TREE__
#define __LLRE_TREE__ 1

#include <functional>
#include <memory>
#include <cassert>

template <typename Key, typename Compare = std::less<Key>>
class LLRB_Tree {
private:
    enum class Node_Color {
        BLACK,
        RED
    }; // the color of the parent link

    Compare compare = Compare();

    struct Node {
        Node *left = nullptr;
        Node *right = nullptr;
        Node *father = nullptr;

        size_t size;
        Node_Color color;
        Key key;
        size_t cnt;

        Node(Key key, Node_Color color, Node *father) : key(key), color(color), size(1), cnt(1), father(father) {}
        Node() = default;
    };

    void Delete_Tree(Node *root) const {
        if (root != nullptr) {
            Delete_Tree(root->left);
            Delete_Tree(root->right);
            root->left = root->right = nullptr;
            delete root;
        }
    }

    size_t size(const Node *node) const {
        return (node == nullptr ? 0 : node->size);
    }

    bool is_red(const Node *node) const {
        return (node == nullptr ? 0 : (node->color == Node_Color::RED));
    }

    int add_node(Node *node) {
        node->cnt++;
        node->size++;
        return node->cnt;
    }

    int sub_node(Node *node) {
        node->cnt--;
        node->size--;
        return node->cnt;
    }

    Node *rotate_left(Node *node) const {
        // rotate left a red link
        //      <nd>                    <rc>
        //     /    \\                //    \
        //    *     <rc>     -->    <nd>     *
        //         /    \          /    \
        //        *      *        *      *
        assert(is_red(node->right));
        Node *res = node->right;
        node->right = res->left;
        res->left = node;
        if (node->right != nullptr) {
            node->right->father = node;
        }
        res->father = node->father;
        node->father = res;
        res->color = node->color;
        node->color = Node_Color::RED;
        res->size = node->size;
        node->size = size(node->left) + size(node->right) + node->cnt;
        return res;
    }

    Node *rotate_right(Node *node) const {
        // rotate right a red link
        //          <nd>               <lc>
        //        //    \             /    \\
        //      <lc>     *    -->    *     <nd>
        //     /    \                     /    \
        //    *      *                   *      *
        assert(is_red(node->left));
        Node *res = node->left;
        node->left = res->right;
        res->right = node;
        if (node->left != nullptr) {
            node->left->father = node;
        }
        res->father = node->father;
        node->father = res;
        res->color = node->color;
        node->color = Node_Color::RED;
        res->size = node->size;
        node->size = size(node->left) + size(node->right) + node->cnt;
        return res;
    }
    // get the fliped color
    Node_Color fliped_color(Node_Color color) const {
        return (color == Node_Color::RED ? Node_Color::BLACK : Node_Color::RED);
    }
    // flip the color of the three node
    void color_flip(Node *node) const {
        node->color = fliped_color(node->color);
        node->left->color = fliped_color(node->left->color);
        node->right->color = fliped_color(node->right->color);
    }

    Node *root = nullptr;
    // fix to maintain the tree
    Node *fix_up(Node *root) {
        if (is_red(root->right) && !is_red(root->left)) {
            root = rotate_left(root);
        }
        if (is_red(root->left) && is_red(root->left->left)) {
            root = rotate_right(root);
        }
        if (is_red(root->left) && is_red(root->right)) {
            color_flip(root);
        }
        root->size = size(root->left) + size(root->right) + root->cnt;
        return root;
    }
    // move a red edge to left
    Node *move_red_left(Node *root) {
        // fix the following case
        //          //             //
        //        <rt>           <rt>
        //       /    \         /    \
        //      *      *       *      *
        //     /      / \     /     // \
        //    *              *
        color_flip(root);
        if (is_red(root->right->left)) {
            // fix the following case
            //           /                     /                       /                      //
            //        <rt>                  <rt>                 <newrt>                 <newrt>
            //      //    \\              //    \\              //     \\                /     \
            //      *      *     -->      *      *     -->    <rt>      *    -->      <rt>      *
            //     /     // \            /      / \\          //                      //
            //    *                     *                     *                       *
            //                                               /                       /
            //                                              *                       *
            root->right = rotate_right(root->right);
            root = rotate_left(root);
            color_flip(root);
        }
        return root;
    }
    // move a red edge to right
    Node *move_red_right(Node *root) {
        // fix the following case
        //          //              //
        //        <rt>            <rt>
        //       /    \          /    \
        //      *      *        *      *
        //     /      / \     //      / \
        //    *      *   *    *      *   *
        color_flip(root);
        if (is_red(root->left->left)) {
            // fix the following case
            //           /                      /                       //
            //        <rt>                <newrt>                  <newrt>
            //      //    \\             //     \\                 /     \
            //      *      *      -->    *       <rt>      -->    *       <rt>
            //    //      / \                       \\                       \\
            //    *      *   *                       *                        *
            //                                      / \                      / \
            //                                     *   *                    *   *
            root = rotate_right(root);
            color_flip(root);
        }
        return root;
    }
    // get the min value of the subtree
    Node *get_min(Node *root) {
        Node *node = root;
        assert(node != nullptr);
        for (; node->left != nullptr; node = node->left);
        return node;
    }
    // erase the min node of the subtree
    Node *erase_min(Node *root) {
        if (root->left == nullptr) {
            delete root;
            return nullptr;
        }
        if (!is_red(root->left) && !is_red(root->left->left)) {
            root = move_red_left(root);
        }
        root->left = erase_min(root->left);
        return fix_up(root);
    }
    // insert from root as leaf
    Node *insert(Node *root, const Key &key, Node *father) {
        if (root == nullptr) {
            return new Node(key, Node_Color::RED, father);
        }
        if (root->key == key) {
            add_node(root);
            return fix_up(root);
        } else if (compare(key, root->key)) {
            root->left = insert(root->left, key, root);
        } else {
            root->right = insert(root->right, key, root);
        }
        return fix_up(root);
    }
    // erase an element
    Node *erase(Node *root, const Key &key) {
        if (compare(key, root->key)) {
            if (!is_red(root->left) && !is_red(root->left->left)) {
                root = move_red_left(root);
            }
            root->left = erase(root->left, key);
        } else {
            if (is_red(root->left)) {
                root = rotate_right(root);
            }
            if (key == root->key & root->right == nullptr) {
                if (sub_node(root) == 0) {
                    delete root;
                    return nullptr;
                } else {
                    return fix_up(root);
                }
            }
            if (!is_red(root->right) && !is_red(root->right->left)) {
                root = move_red_right(root);
            }
            if (key == root->key) {
                if (sub_node(root) == 0) {
                    Node *node_min = get_min(root->right);
                    root->key = node_min->key;
                    root->cnt = node_min->cnt;
                    root->right = erase_min(root->right);
                } else {
                    return fix_up(root);
                }
            } else {
                root->right = erase(root->right, key);
            }
        }
        return fix_up(root);
    }
    // get the prev node of the node
    Node *get_prev_node(Node *node) const {
        assert(node != nullptr);
        if (node->left == nullptr) {
            while (node->father != nullptr && node->father->left == node) {
                node = node->father;
            }
            node = node->father;
        } else {
            node = node->left;
            while (node->right != nullptr) {
                node = node->right;
            }
        }
        return node;
    }
    // get the next node of the node
    Node *get_next_node(Node *node) const {
        assert(node != nullptr);
        if (node->right == nullptr) {
            while (node->father != nullptr && node->father->right == node) {
                node = node->father;
            }
            node = node->father;
        } else {
            node = node->right;
            while (node->left != nullptr) {
                node = node->left;
            }
        }
        return node;
    }
    // print all (value: cnt)
    void print_tree(Node *root) const {
        if (root == nullptr) {
            return;
        }
        print_tree(root->left);
        std::cout << "(" << root->key << ": " << root->cnt << ") ";
        print_tree(root->right);
    }

public:
    LLRB_Tree() = default;
    LLRB_Tree(LLRB_Tree &) = default;
    LLRB_Tree(LLRB_Tree &&) noexcept = default;
    ~LLRB_Tree() {
        Delete_Tree(root);
    }
    // insert a node
    void insert(const Key &key) {
        root = insert(root, key, nullptr);
        root->color = Node_Color::BLACK;
    }
    // delete a node
    size_t erase(const Key &key) {
        if (count(key) > 0) {
            if (!is_red(root->left) && !is_red(root->right)) {
                root->color = Node_Color::RED;
            }
            root = erase(root, key);
            if (root != nullptr) {
                root->color = Node_Color::BLACK;
            }
            return 1;
        } else {
            return 0;
        }
    }
    // clear all node
    void clear() {
        Delete_Tree(root);
        root = nullptr;
    }
    // get the size of the tree
    size_t size() const {
        return size(root);
    }
    // count the key
    size_t count(const Key &key) const {
        Node *node = root;
        while (node != nullptr) {
            if (key == node->key) {
                return node->cnt;
            }
            if (compare(key, node->key)) {
                node = node->left;
            } else {
                node = node->right;
            }
        }
        return 0;
    }
    // get the rk of the value
    int get_rk(const Key &key) const {
        int rank = 1;
        Node *node = root;
        while (node != nullptr) {
            if (compare(key, node->key)) {
                node = node->left;
            } else {
                rank += size(node->left);
                if (key == node->key) {
                    return rank;
                }
                rank += node->cnt;
                node = node->right;
            }
        }
        return rank;
    }
    // get the kth value
    Key get_kth(int k) const {
        Node *node = root;
        if (size(root) < k) {
            return -1;
        }
        while (true) {
            if (k > size(node->left) + node->cnt) {
                k -= size(node->left) + node->cnt;
                node = node->right;
            } else if (size(node->left) >= k) {
                node = node->left;
            } else {
                return node->key;
            }
        }
    }
    // get the prev of key
    Node *get_prev(const Key &key) const {
        Node *node = root, *res_node = nullptr;
        while (node != nullptr) {
            res_node = node;
            if (compare(node->key, key)) {
                node = node->right;
            } else {
                node = node->left;
            }
        }
        if (compare(res_node->key, key)) {
            return res_node;
        } else {
            return get_prev_node(res_node);
        }
    }
    // get the next of key
    Node *get_next(const Key &key) const {
        Node *node = root, *res_node = nullptr;
        while (node != nullptr) {
            res_node = node;
            if (compare(key, node->key)) {
                node = node->left;
            } else {
                node = node->right;
            }
        }
        if (compare(key, res_node->key)) {
            return res_node;
        } else {
            return get_next_node(res_node);
        }
    }
    // check if is empty
    bool empty() const {
        return (size(root) == 0);
    }
    // print the value
    void print() const {
        print_tree(root);
        std::cout << "\n";
    }
};

#endif

洛谷 P6136 AC 代码

#include <iostream>
#include <functional>
#include <memory>
#include <cassert>

template <typename Key, typename Compare = std::less<Key>>
class LLRB_Tree {
private:
    enum class Node_Color {
        BLACK,
        RED
    }; // the color of the parent link

    Compare compare = Compare();

    struct Node {
        Node *left = nullptr;
        Node *right = nullptr;
        Node *father = nullptr;

        size_t size;
        Node_Color color;
        Key key;
        size_t cnt;

        Node(Key key, Node_Color color, Node *father) : key(key), color(color), size(1), cnt(1), father(father) {}
        Node() = default;
    };

    void Delete_Tree(Node *root) const {
        if (root != nullptr) {
            Delete_Tree(root->left);
            Delete_Tree(root->right);
            root->left = root->right = nullptr;
            delete root;
        }
    }

    size_t size(const Node *node) const {
        return (node == nullptr ? 0 : node->size);
    }

    bool is_red(const Node *node) const {
        return (node == nullptr ? 0 : (node->color == Node_Color::RED));
    }

    int add_node(Node *node) {
        node->cnt++;
        node->size++;
        return node->cnt;
    }

    int sub_node(Node *node) {
        node->cnt--;
        node->size--;
        return node->cnt;
    }

    Node *rotate_left(Node *node) const {
        // rotate left a red link
        //      <nd>                    <rc>
        //     /    \\                //    \
        //    *     <rc>     -->    <nd>     *
        //         /    \          /    \
        //        *      *        *      *
        assert(is_red(node->right));
        Node *res = node->right;
        node->right = res->left;
        res->left = node;
        if (node->right != nullptr) {
            node->right->father = node;
        }
        res->father = node->father;
        node->father = res;
        res->color = node->color;
        node->color = Node_Color::RED;
        res->size = node->size;
        node->size = size(node->left) + size(node->right) + node->cnt;
        return res;
    }

    Node *rotate_right(Node *node) const {
        // rotate right a red link
        //          <nd>               <lc>
        //        //    \             /    \\
        //      <lc>     *    -->    *     <nd>
        //     /    \                     /    \
        //    *      *                   *      *
        assert(is_red(node->left));
        Node *res = node->left;
        node->left = res->right;
        res->right = node;
        if (node->left != nullptr) {
            node->left->father = node;
        }
        res->father = node->father;
        node->father = res;
        res->color = node->color;
        node->color = Node_Color::RED;
        res->size = node->size;
        node->size = size(node->left) + size(node->right) + node->cnt;
        return res;
    }
    // get the fliped color
    Node_Color fliped_color(Node_Color color) const {
        return (color == Node_Color::RED ? Node_Color::BLACK : Node_Color::RED);
    }
    // flip the color of the three node
    void color_flip(Node *node) const {
        node->color = fliped_color(node->color);
        node->left->color = fliped_color(node->left->color);
        node->right->color = fliped_color(node->right->color);
    }

    Node *root = nullptr;
    // fix to maintain the tree
    Node *fix_up(Node *root) {
        if (is_red(root->right) && !is_red(root->left)) {
            root = rotate_left(root);
        }
        if (is_red(root->left) && is_red(root->left->left)) {
            root = rotate_right(root);
        }
        if (is_red(root->left) && is_red(root->right)) {
            color_flip(root);
        }
        root->size = size(root->left) + size(root->right) + root->cnt;
        return root;
    }
    // move a red edge to left
    Node *move_red_left(Node *root) {
        // fix the following case
        //          //             //
        //        <rt>           <rt>
        //       /    \         /    \
        //      *      *       *      *
        //     /      / \     /     // \
        //    *              *
        color_flip(root);
        if (is_red(root->right->left)) {
            // fix the following case
            //           /                     /                       /                      //
            //        <rt>                  <rt>                 <newrt>                 <newrt>
            //      //    \\              //    \\              //     \\                /     \
            //      *      *     -->      *      *     -->    <rt>      *    -->      <rt>      *
            //     /     // \            /      / \\          //                      //
            //    *                     *                     *                       *
            //                                               /                       /
            //                                              *                       *
            root->right = rotate_right(root->right);
            root = rotate_left(root);
            color_flip(root);
        }
        return root;
    }
    // move a red edge to right
    Node *move_red_right(Node *root) {
        // fix the following case
        //          //              //
        //        <rt>            <rt>
        //       /    \          /    \
        //      *      *        *      *
        //     /      / \     //      / \
        //    *      *   *    *      *   *
        color_flip(root);
        if (is_red(root->left->left)) {
            // fix the following case
            //           /                      /                       //
            //        <rt>                <newrt>                  <newrt>
            //      //    \\             //     \\                 /     \
            //      *      *      -->    *       <rt>      -->    *       <rt>
            //    //      / \                       \\                       \\
            //    *      *   *                       *                        *
            //                                      / \                      / \
            //                                     *   *                    *   *
            root = rotate_right(root);
            color_flip(root);
        }
        return root;
    }
    // get the min value of the subtree
    Node *get_min(Node *root) {
        Node *node = root;
        assert(node != nullptr);
        for (; node->left != nullptr; node = node->left);
        return node;
    }
    // erase the min node of the subtree
    Node *erase_min(Node *root) {
        if (root->left == nullptr) {
            delete root;
            return nullptr;
        }
        if (!is_red(root->left) && !is_red(root->left->left)) {
            root = move_red_left(root);
        }
        root->left = erase_min(root->left);
        return fix_up(root);
    }
    // insert from root as leaf
    Node *insert(Node *root, const Key &key, Node *father) {
        if (root == nullptr) {
            return new Node(key, Node_Color::RED, father);
        }
        if (root->key == key) {
            add_node(root);
            return fix_up(root);
        } else if (compare(key, root->key)) {
            root->left = insert(root->left, key, root);
        } else {
            root->right = insert(root->right, key, root);
        }
        return fix_up(root);
    }
    // erase an element
    Node *erase(Node *root, const Key &key) {
        if (compare(key, root->key)) {
            if (!is_red(root->left) && !is_red(root->left->left)) {
                root = move_red_left(root);
            }
            root->left = erase(root->left, key);
        } else {
            if (is_red(root->left)) {
                root = rotate_right(root);
            }
            if (key == root->key & root->right == nullptr) {
                if (sub_node(root) == 0) {
                    delete root;
                    return nullptr;
                } else {
                    return fix_up(root);
                }
            }
            if (!is_red(root->right) && !is_red(root->right->left)) {
                root = move_red_right(root);
            }
            if (key == root->key) {
                if (sub_node(root) == 0) {
                    Node *node_min = get_min(root->right);
                    root->key = node_min->key;
                    root->cnt = node_min->cnt;
                    root->right = erase_min(root->right);
                } else {
                    return fix_up(root);
                }
            } else {
                root->right = erase(root->right, key);
            }
        }
        return fix_up(root);
    }
    // get the prev node of the node
    Node *get_prev_node(Node *node) const {
        assert(node != nullptr);
        if (node->left == nullptr) {
            while (node->father != nullptr && node->father->left == node) {
                node = node->father;
            }
            node = node->father;
        } else {
            node = node->left;
            while (node->right != nullptr) {
                node = node->right;
            }
        }
        return node;
    }
    // get the next node of the node
    Node *get_next_node(Node *node) const {
        assert(node != nullptr);
        if (node->right == nullptr) {
            while (node->father != nullptr && node->father->right == node) {
                node = node->father;
            }
            node = node->father;
        } else {
            node = node->right;
            while (node->left != nullptr) {
                node = node->left;
            }
        }
        return node;
    }
    // print all (value: cnt)
    void print_tree(Node *root) const {
        if (root == nullptr) {
            return;
        }
        print_tree(root->left);
        std::cout << "(" << root->key << ": " << root->cnt << ") ";
        print_tree(root->right);
    }

public:
    LLRB_Tree() = default;
    LLRB_Tree(LLRB_Tree &) = default;
    LLRB_Tree(LLRB_Tree &&) noexcept = default;
    ~LLRB_Tree() {
        Delete_Tree(root);
    }
    // insert a node
    void insert(const Key &key) {
        root = insert(root, key, nullptr);
        root->color = Node_Color::BLACK;
    }
    // delete a node
    size_t erase(const Key &key) {
        if (count(key) > 0) {
            if (!is_red(root->left) && !is_red(root->right)) {
                root->color = Node_Color::RED;
            }
            root = erase(root, key);
            if (root != nullptr) {
                root->color = Node_Color::BLACK;
            }
            return 1;
        } else {
            return 0;
        }
    }
    // clear all node
    void clear() {
        Delete_Tree(root);
        root = nullptr;
    }
    // get the size of the tree
    size_t size() const {
        return size(root);
    }
    // count the key
    size_t count(const Key &key) const {
        Node *node = root;
        while (node != nullptr) {
            if (key == node->key) {
                return node->cnt;
            }
            if (compare(key, node->key)) {
                node = node->left;
            } else {
                node = node->right;
            }
        }
        return 0;
    }
    // get the rk of the value
    int get_rk(const Key &key) const {
        int rank = 1;
        Node *node = root;
        while (node != nullptr) {
            if (compare(key, node->key)) {
                node = node->left;
            } else {
                rank += size(node->left);
                if (key == node->key) {
                    return rank;
                }
                rank += node->cnt;
                node = node->right;
            }
        }
        return rank;
    }
    // get the kth value
    Key get_kth(int k) const {
        Node *node = root;
        if (size(root) < k) {
            return -1;
        }
        while (true) {
            if (k > size(node->left) + node->cnt) {
                k -= size(node->left) + node->cnt;
                node = node->right;
            } else if (size(node->left) >= k) {
                node = node->left;
            } else {
                return node->key;
            }
        }
    }
    // get the prev of key
    Node *get_prev(const Key &key) const {
        Node *node = root, *res_node = nullptr;
        while (node != nullptr) {
            res_node = node;
            if (compare(node->key, key)) {
                node = node->right;
            } else {
                node = node->left;
            }
        }
        if (compare(res_node->key, key)) {
            return res_node;
        } else {
            return get_prev_node(res_node);
        }
    }
    // get the next of key
    Node *get_next(const Key &key) const {
        Node *node = root, *res_node = nullptr;
        while (node != nullptr) {
            res_node = node;
            if (compare(key, node->key)) {
                node = node->left;
            } else {
                node = node->right;
            }
        }
        if (compare(key, res_node->key)) {
            return res_node;
        } else {
            return get_next_node(res_node);
        }
    }
    // check if is empty
    bool empty() const {
        return (size(root) == 0);
    }
    // print the value
    void print() const {
        print_tree(root);
        std::cout << "\n";
    }
};

int ans = 0, lst = 0;

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);

    int n, m;
    std::cin >> n >> m;

    LLRB_Tree<int> st;

    for (int i = 1, x; i <= n; i++) {
        std::cin >> x;
        st.insert(x);
    }

    while (m--) {
        int op, x;
        std::cin >> op >> x;
        x ^= lst;

        if (op == 1) {
            st.insert(x);
        } else if (op == 2) {
            st.erase(x);
        } else if (op == 3) {
            lst = st.get_rk(x);
            ans ^= lst;
        } else if (op == 4) {
            lst = st.get_kth(x);
            ans ^= lst;
        } else if (op == 5) {
            lst = st.get_prev(x)->key;
            ans ^= lst;
        } else {
            lst = st.get_next(x)->key;
            ans ^= lst;
        }
    }

    std::cout << ans << "\n";

    return 0;
}