bbst/red_black_tree.hpp

• View this file on GitHub
• Last update: 2025-06-19 13:39:58+09:00
• Include: #include "bbst/red_black_tree.hpp"

Depends on

• 赤黒木の基本クラス (bbst/base/red_black_tree_base.hpp)
• others/vector_pool.hpp
• type_traits/io.hpp

Verified with

• verify/yosupo_ds/ds_ordered_set_max_right.test.cpp
• verify/yosupo_ds/ds_ordered_set_min_left.test.cpp
• verify/yosupo_ds/ds_point_set_range_composite_2.test.cpp

Code

#ifndef KK2_BBST_RED_BLACK_TREE_HPP
#define KK2_BBST_RED_BLACK_TREE_HPP 1

#include <cassert>
#include <memory>
#include <string>
#include <utility>
#include <vector>

#include "../type_traits/io.hpp"
#include "base/red_black_tree_base.hpp"

namespace kk2 {

namespace rbtree {

template <class M> struct RedBlackTreeNode {
    using NodePtr = typename RedBlackTreeBase<RedBlackTreeNode>::NodePtr;
    using action_type = void;
    using S = M;
    using A = int;
    static S s_op(S a, S b) { return S::op(a, b); }
    static S s_unit() { return S::unit(); }
    static S sa_act(A, S) { return S(); }
    static A a_op(A, A) { return 0; }
    static A a_unit() { return 0; }

    NodePtr left, right;
    int rank, count;
    bool is_red, is_rev;
    S val;

    RedBlackTreeNode(S val_ = s_unit())
        : left(nullptr),
          right(nullptr),
          rank(0),
          count(1),
          is_red(false),
          is_rev(false),
          val(val_) {}

    RedBlackTreeNode(NodePtr l, NodePtr r) : left(l), right(r), is_red(true), is_rev(false) {}

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    void debug_output(OStream &os) const {
        std::vector<std::string> a;
        a.push_back("[");
        auto dfs = [&](auto self, NodePtr t, int dep) -> void {
            if (!t) return;
            if ((int)a.size() <= dep + 1) a.resize(dep + 2);
            a[dep + 1] += (t->is_red ? "(R" : "(B");
            a[dep + 1] += " val:" + std::to_string(t->val);
            a[dep + 1] += " is_rev:" + std::to_string(t->is_rev);
            a[dep + 1] += " rank:" + std::to_string(t->rank);
            a[dep + 1] += " cnt:" + std::to_string(t->count);
            a[dep + 1] += ") ";
            self(self, t->left, dep + 1);
            self(self, t->right, dep + 1);
        };
        dfs(dfs, NodePtr(this), 0);
        for (auto &s : a) s.push_back('\n');
        a.push_back("]");
        for (auto &s : a) os << s;
    }
};

template <class M> struct RedBlackTree : RedBlackTreeBase<RedBlackTreeNode<M>> {
    using base = RedBlackTreeBase<RedBlackTreeNode<M>>;
    using base::RedBlackTreeBase;
    using base::s_op;
    using base::size;
    using typename base::NodePtr;
    using typename base::S;

  protected:
    NodePtr update(NodePtr t) override {
        t->count = size(t->left) + size(t->right) + (t->left == nullptr);
        t->rank = t->left ? t->left->rank + !t->left->is_red : 1;
        t->val = (t->left ? s_op(t->left->val, t->right->val) : t->val);
        return t;
    }

    NodePtr push(NodePtr t) override {
        if (t->is_rev) {
            std::swap(t->left, t->right);
            if (t->left) t->left->is_rev ^= 1;
            if (t->right) t->right->is_rev ^= 1;
            t->is_rev = false;
        }
        return t;
    }
};

} // namespace rbtree

using rbtree::RedBlackTree;

} // namespace kk2


#endif // KK2_BBST_RED_BLACK_TREE_HPP

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: type_traits/io.hpp: line 4: #pragma once found in a non-first line

Back to top page