完全永続赤黒木 (平衡二分木)
(DataStructure/PersistentRedBlackTree.hpp)

View this file on GitHub
Last update: 2021-03-09 15:27:18+09:00
Include: #include "DataStructure/PersistentRedBlackTree.hpp"
Link: https://tkmst201.github.io/Library/DataStructure/PersistentRedBlackTree.hpp

概要

完全永続赤黒木です。可変配列を扱います。大きさ $N$ の配列の過去の任意の状態に対し、split、 merge、データの挿入、削除が $\mathcal{O}(\log{N})$ で行うことができます。各操作 $\mathcal{O}(\log{N})$ の空間を消費します。

PersistentRedBlackTree()
- $\Theta(1)$ 要素数 $0$ の可変配列で初期化
PersistentRedBlackTree(std::vector<T> v)
- 時間/空間 $\Theta($v$)$ $v$ で初期化
PersistentRedBlackTree(size_t n, const T & x)
- 時間/空間 $\Theta(n)$ すべての値が $x$ の要素数 $n$ の可変配列で初期化
bool empty()
- $\Theta(1)$ 可変配列が空なら $true$ を返す
size_t size()
- $\Theta(1)$ 可変配列の要素数 $N$ を返す
void clear()
- $\mathcal{O}(N)$ 可変配列のすべての要素を削除
std::vector<T> enumerate()
- $\Theta(N)$ 現在の可変配列を返す
PersistentRedBlackTree merge(const PersistentRedBlackTree & a)
- 時間/空間 $\Theta(|$rank $-$ a.rank$|)$ 可変配列の末尾に a を追加した可変配列を返す
pair<PersistentRedBlackTree, PersistentRedBlackTree> split(size_t k)
- 時間/空間 $\mathcal{O}(\log{N})$ 可変配列の先頭 $k$ 個の要素と $k + 1$ 個目の要素以降の $2$ つの可変配列に分けてこの順で返す
PersistentRedBlackTree insert(size_t k, const T & x)
- 時間/空間 $\mathcal{O}(\log{N})$ 前に $k$ 個の要素がある位置に $x$ を挿入した可変配列を返す
PersistentRedBlackTree erase(size_t k)
- 時間/空間 $\mathcal{O}(\log{N})$ 先頭から 0-indexed で $k$ 番目の要素を削除した可変配列を返す
const T & get(size_t k)
- $\mathcal{O}(\log{N})$ 先頭から 0-indexed で $k$ 番目の要素を返す

コンストラクタ

PersistentRedBlackTree()

要素数 $0$ の可変配列で初期化します。
$T$ には保持したい値の型を指定します。

計算量

$\Theta(1)$

PersistentRedBlackTree(std::vector<T> v)

$v$ で初期化します。

制約

InputIterator は Random Access Iterator

計算量

$\Theta($v$)$

PersistentRedBlackTree(size_t n, const T & x)

すべての値が $x$ の要素数 $n$ の可変配列で初期化します。

制約

InputIterator は Random Access Iterator

計算量

$\Theta(n)$

メンバ関数

可変配列の要素数を $N$ とします。
根から葉までのパス上 (根含まない) にある黒ノードの個数を rank とします。

bool empty()

可変配列が空なら $true$ を返します。それ以外は $false$ を返します。

計算量

$\Theta(1)$

size_t size()

可変配列の要素数 $N$ を返します。

計算量

$\Theta(1)$

void clear()

可変配列のすべての要素を削除します。

計算量

$\mathcal{O}(N)$

std::vector enumerate()

現在の可変配列を返します。

計算量

$\Theta(N)$

PersistentRedBlackTree merge(const PersistentRedBlackTree & a)

可変配列の末尾に a を追加した可変配列を返します。

計算量

時間/空間 $\Theta(|$rank $-$ a.rank$|)$

pair<PersistentRedBlackTree, PersistentRedBlackTree> split(size_t k)

可変配列の先頭 $k$ 個の要素と $k + 1$ 個目の要素以降の $2$ つの可変配列に分けてこの順で返します。

制約

$0 \leq k \leq N$

計算量

時間/空間 $\mathcal{O}(\log{N})$

PersistentRedBlackTree insert(size_t k, const T & x)

前に $k$ 個の要素がある位置に $x$ を挿入した可変配列を返します。

制約

$0 \leq k \leq N$

計算量

時間/空間 $\mathcal{O}(\log{N})$

PersistentRedBlackTree erase(size_t k)

先頭から 0-indexed で $k$ 番目の要素を削除した可変配列を返します。

制約

時間/空間 $0 \leq k < N$

計算量

$\mathcal{O}(\log{N})$

const T & get(size_t k)

先頭から 0-indexed で $k$ 番目の要素を返します。

制約

$0 \leq k < N$

計算量

$\mathcal{O}(\log{N})$

使用例

#include <bits/stdc++.h>
#include "DataStructure/PersistentRedBlackTree.hpp"
using namespace std;

int main() {
	PersistentRedBlackTree<int> rbt({0, 1, 2, 3, 4, 5, 6});
	
	cout << "empty() = " << boolalpha << rbt.empty() << endl; // false
	cout << "size = " << rbt.size() << endl; // 7
	// 0 1 2 3 4 5 6
	for (int i : rbt.enumerate()) cout << i << " "; cout << '\n';
	
	auto rbt2 = rbt.insert(0, 100);
	auto rbt3 = rbt.insert(3, 100);
	auto rbt4 = rbt.insert(7, 100);
	// 0 1 2 3 4 5 6
	for (int i : rbt.enumerate()) cout << i << " "; cout << '\n';
	// 100 0 1 2 3 4 5 6
	for (int i : rbt2.enumerate()) cout << i << " "; cout << '\n';
	// 0 1 2 100 3 4 5 6
	for (int i : rbt3.enumerate()) cout << i << " "; cout << '\n';
	// 0 1 2 3 4 5 6 100
	for (int i : rbt4.enumerate()) cout << i << " "; cout << '\n';
	
	auto rbtm = rbt3.merge(rbt4);
	// 0 1 2 100 3 4 5 6 0 1 2 3 4 5 6 100
	for (int i : rbtm.enumerate()) cout << i << " "; cout << '\n';
	
	// 100 3 4 5 6 0 ( [3, 9) )
	auto rbts = rbtm.split(9).first.split(3).second;
	for (int i : rbts.enumerate()) cout << i << " "; cout << '\n';
	
	cout << "get(3) = " << rbts.get(3) << endl; // 5
	
	auto rbte = rbts.erase(3);
	// 100 3 4 6 0
	for (int i : rbte.enumerate()) cout << i << " "; cout << '\n';
	
	rbt = PersistentRedBlackTree<int>();
	cout << "empty() = " << boolalpha << rbt.empty() << endl; // true
	
	// 5 5 5
	for (int i : PersistentRedBlackTree<int>(3, 5).enumerate()) cout << i << " "; cout << '\n';
}

TODO

TODO: メモリプールを使って高速化

参考

2020/08/30: https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4-copypaste-slides.pdf
2020/08/30: http://blog.mitaki28.info/1447078746296/
2020/08/30: http://algoogle.hadrori.jp/algorithm/rbtree_merge.html

Verified with

Test/PersistentRedBlackTree.test.cpp

Code

#ifndef INCLUDE_GUARD_PERSISTENT_RED_BLACK_TREE_HPP
#define INCLUDE_GUARD_PERSISTENT_RED_BLACK_TREE_HPP

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

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/PersistentRedBlackTree.hpp
 */
template<typename T>
struct PersistentRedBlackTree {
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	
	static constexpr bool red = true;
	static constexpr bool black = false;
	struct Node;
	using node_ptr = std::shared_ptr<Node>;
	using node_ref = const node_ptr &;
	using raw_ptr = Node *;
	struct Node {
		value_type val;
		bool color;
		size_type size, rank;
		node_ptr l, r;
		Node(bool color, node_ref l, node_ref r)
			: color(color), size(l->size + r->size), rank(l->rank + (l->color == black)), l(l), r(r) {}
		Node(const_reference val) : val(val), color(black), size(1), rank(0), l(nullptr), r(nullptr) {}
	};
	
private:
	node_ptr root = nullptr;
	
	PersistentRedBlackTree(node_ref root) : root(root) {}
	
	static node_ptr create(bool color, node_ref l, node_ref r) {
		return std::make_shared<Node>(color, l, r);
	}
	
	static node_ptr create(const_reference val) {
		return std::make_shared<Node>(val);
	}
	
public:
	PersistentRedBlackTree() = default;
	
	PersistentRedBlackTree(const std::vector<value_type> & v)
		: root(v.empty() ? nullptr : build(std::begin(v), std::end(v), 30)) {}
	
	PersistentRedBlackTree(size_type n, const_reference x)
		: root(n == 0 ? nullptr : buildn(n, x, 30)) {}
	
	bool empty() const noexcept {
		return size() == 0;
	}
	
	size_type size() const noexcept {
		return root ? root->size : 0;
	}
	
	void clear() {
		root = nullptr;
	}
	
	std::vector<value_type> enumerate() const {
		std::vector<value_type> elements;
		std::stack<raw_ptr> stk;
		stk.emplace(root.get());
		while (!stk.empty()) {
			raw_ptr q = stk.top();
			stk.pop();
			if (q->l) {
				stk.emplace(q->r.get());
				stk.emplace(q->l.get());
			}
			else elements.emplace_back(q->val);
		}
		return elements;
	}
	
	PersistentRedBlackTree merge(const PersistentRedBlackTree & a) const {
		return merge(root, a.root);
	}
	
	std::pair<PersistentRedBlackTree, PersistentRedBlackTree> split(size_type k) const {
		assert(k <= size());
		const auto sp = split(root, k);
		return {sp.first, sp.second};
	}
	
	PersistentRedBlackTree insert(size_type k, const_reference x) const {
		assert(k <= size());
		return insert(root, k, x);
	}
	
	PersistentRedBlackTree erase(size_type k) const {
		assert(k < size());
		return erase(root, k);
	}
	
	const_reference get(size_type k) const noexcept {
		assert(k < size());
		raw_ptr q = root.get();
		while (q->l) {
			if (k < q->l->size) q = (q->l).get();
			else k -= q->l->size, q = (q->r).get();
		}
		return q->val;
	}
	
private:
	template<class InputIterator>
	node_ptr build(InputIterator first, InputIterator last, int k) const {
		if (first + 1 == last) return create(*first);
		const auto n = last - first;
		const unsigned int m = 1u << k;
		if (n > m) return merge(build(first, first + m, k - 1), build(first + m, last, k - 1));
		return build(first, last, k - 1);
	}
	
	node_ptr buildn(size_type n, const_reference x, int k) const {
		if (n == 1) return create(x);
		const unsigned int m = 1u << k;
		if (n > m) return merge(buildn(m, x, k - 1), buildn(n - m, x, k - 1));
		return buildn(n, x, k - 1);
	}
	
	node_ptr as_root(const node_ptr & q) const {
		if (!q) return nullptr;
		if (q->color == red) return create(black, q->l, q->r);
		return q;
	}
	
	node_ptr merge(const node_ptr & a, const node_ptr & b) const {
		if (!a) return b;
		if (!b) return a;
		node_ptr res = merge_sub(a, b);
		res->color = black;
		return res;
	}
	
	node_ptr merge_sub(const node_ptr & a, const node_ptr & b) const {
		if (a->rank < b->rank) {
			node_ptr c = merge_sub(a, b->l);
			if (b->color == black && c->color == red && c->l->color == red) {
				if (b->r->color == black) return create(black, c->l, create(red, c->r, b->r));
				c->color = black;
				return create(red, c, create(black, b->r->l, b->r->r));
			}
			return create(b->color, c, b->r);
		}
		else if (a->rank > b->rank) {
			const node_ptr c = merge_sub(a->r, b);
			if (a->color == black && c->color == red && c->r->color == red) {
				if (a->l->color == black) return create(black, create(red, a->l, c->l), c->r);
				c->color = black;
				return create(red, create(black, a->l->l, a->l->r), c);
			}
			return create(a->color, a->l, c);
		}
		return create(red, a, b);
	}
	
	std::pair<node_ptr, node_ptr> split(const node_ptr & a, size_type k) const {
		if (!a) return {nullptr, nullptr};
		if (k == 0) return {nullptr, as_root(a)};
		if (k == a->size) return {as_root(a), nullptr};
		if (k < a->l->size) {
			const auto sp = split(a->l, k);
			return {as_root(sp.first), merge(sp.second, as_root(a->r))};
		}
		if (k > a->l->size) {
			const auto sp = split(a->r, k - a->l->size);
			return {merge(as_root(a->l), sp.first), as_root(sp.second)};
		}
		return {as_root(a->l), as_root(a->r)};
	}
	
	node_ptr insert(const node_ptr & a, size_type k, const_reference x) const {
		if (!a) return create(x);
		const auto sp = split(a, k);
		return merge(sp.first, merge(create(x), sp.second));
	}
	
	node_ptr erase(const node_ptr & a, size_type k) const {
		const auto sp = split(a, k + 1);
		return merge(split(sp.first, k).first, sp.second);
	}
};

#endif // INCLUDE_GUARD_PERSISTENT_RED_BLACK_TREE_HPP

#line 1 "DataStructure/PersistentRedBlackTree.hpp"



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

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/PersistentRedBlackTree.hpp
 */
template<typename T>
struct PersistentRedBlackTree {
	using value_type = T;
	using const_reference = const value_type &;
	using size_type = std::size_t;
	
	static constexpr bool red = true;
	static constexpr bool black = false;
	struct Node;
	using node_ptr = std::shared_ptr<Node>;
	using node_ref = const node_ptr &;
	using raw_ptr = Node *;
	struct Node {
		value_type val;
		bool color;
		size_type size, rank;
		node_ptr l, r;
		Node(bool color, node_ref l, node_ref r)
			: color(color), size(l->size + r->size), rank(l->rank + (l->color == black)), l(l), r(r) {}
		Node(const_reference val) : val(val), color(black), size(1), rank(0), l(nullptr), r(nullptr) {}
	};
	
private:
	node_ptr root = nullptr;
	
	PersistentRedBlackTree(node_ref root) : root(root) {}
	
	static node_ptr create(bool color, node_ref l, node_ref r) {
		return std::make_shared<Node>(color, l, r);
	}
	
	static node_ptr create(const_reference val) {
		return std::make_shared<Node>(val);
	}
	
public:
	PersistentRedBlackTree() = default;
	
	PersistentRedBlackTree(const std::vector<value_type> & v)
		: root(v.empty() ? nullptr : build(std::begin(v), std::end(v), 30)) {}
	
	PersistentRedBlackTree(size_type n, const_reference x)
		: root(n == 0 ? nullptr : buildn(n, x, 30)) {}
	
	bool empty() const noexcept {
		return size() == 0;
	}
	
	size_type size() const noexcept {
		return root ? root->size : 0;
	}
	
	void clear() {
		root = nullptr;
	}
	
	std::vector<value_type> enumerate() const {
		std::vector<value_type> elements;
		std::stack<raw_ptr> stk;
		stk.emplace(root.get());
		while (!stk.empty()) {
			raw_ptr q = stk.top();
			stk.pop();
			if (q->l) {
				stk.emplace(q->r.get());
				stk.emplace(q->l.get());
			}
			else elements.emplace_back(q->val);
		}
		return elements;
	}
	
	PersistentRedBlackTree merge(const PersistentRedBlackTree & a) const {
		return merge(root, a.root);
	}
	
	std::pair<PersistentRedBlackTree, PersistentRedBlackTree> split(size_type k) const {
		assert(k <= size());
		const auto sp = split(root, k);
		return {sp.first, sp.second};
	}
	
	PersistentRedBlackTree insert(size_type k, const_reference x) const {
		assert(k <= size());
		return insert(root, k, x);
	}
	
	PersistentRedBlackTree erase(size_type k) const {
		assert(k < size());
		return erase(root, k);
	}
	
	const_reference get(size_type k) const noexcept {
		assert(k < size());
		raw_ptr q = root.get();
		while (q->l) {
			if (k < q->l->size) q = (q->l).get();
			else k -= q->l->size, q = (q->r).get();
		}
		return q->val;
	}
	
private:
	template<class InputIterator>
	node_ptr build(InputIterator first, InputIterator last, int k) const {
		if (first + 1 == last) return create(*first);
		const auto n = last - first;
		const unsigned int m = 1u << k;
		if (n > m) return merge(build(first, first + m, k - 1), build(first + m, last, k - 1));
		return build(first, last, k - 1);
	}
	
	node_ptr buildn(size_type n, const_reference x, int k) const {
		if (n == 1) return create(x);
		const unsigned int m = 1u << k;
		if (n > m) return merge(buildn(m, x, k - 1), buildn(n - m, x, k - 1));
		return buildn(n, x, k - 1);
	}
	
	node_ptr as_root(const node_ptr & q) const {
		if (!q) return nullptr;
		if (q->color == red) return create(black, q->l, q->r);
		return q;
	}
	
	node_ptr merge(const node_ptr & a, const node_ptr & b) const {
		if (!a) return b;
		if (!b) return a;
		node_ptr res = merge_sub(a, b);
		res->color = black;
		return res;
	}
	
	node_ptr merge_sub(const node_ptr & a, const node_ptr & b) const {
		if (a->rank < b->rank) {
			node_ptr c = merge_sub(a, b->l);
			if (b->color == black && c->color == red && c->l->color == red) {
				if (b->r->color == black) return create(black, c->l, create(red, c->r, b->r));
				c->color = black;
				return create(red, c, create(black, b->r->l, b->r->r));
			}
			return create(b->color, c, b->r);
		}
		else if (a->rank > b->rank) {
			const node_ptr c = merge_sub(a->r, b);
			if (a->color == black && c->color == red && c->r->color == red) {
				if (a->l->color == black) return create(black, create(red, a->l, c->l), c->r);
				c->color = black;
				return create(red, create(black, a->l->l, a->l->r), c);
			}
			return create(a->color, a->l, c);
		}
		return create(red, a, b);
	}
	
	std::pair<node_ptr, node_ptr> split(const node_ptr & a, size_type k) const {
		if (!a) return {nullptr, nullptr};
		if (k == 0) return {nullptr, as_root(a)};
		if (k == a->size) return {as_root(a), nullptr};
		if (k < a->l->size) {
			const auto sp = split(a->l, k);
			return {as_root(sp.first), merge(sp.second, as_root(a->r))};
		}
		if (k > a->l->size) {
			const auto sp = split(a->r, k - a->l->size);
			return {merge(as_root(a->l), sp.first), as_root(sp.second)};
		}
		return {as_root(a->l), as_root(a->r)};
	}
	
	node_ptr insert(const node_ptr & a, size_type k, const_reference x) const {
		if (!a) return create(x);
		const auto sp = split(a, k);
		return merge(sp.first, merge(create(x), sp.second));
	}
	
	node_ptr erase(const node_ptr & a, size_type k) const {
		const auto sp = split(a, k + 1);
		return merge(split(sp.first, k).first, sp.second);
	}
};

完全永続赤黒木 (平衡二分木) (DataStructure/PersistentRedBlackTree.hpp)

概要

コンストラクタ

PersistentRedBlackTree()

PersistentRedBlackTree(std::vector<T> v)

PersistentRedBlackTree(size_t n, const T & x)

メンバ関数

bool empty()

size_t size()

void clear()

std::vector enumerate()

PersistentRedBlackTree merge(const PersistentRedBlackTree & a)

pair<PersistentRedBlackTree, PersistentRedBlackTree> split(size_t k)

PersistentRedBlackTree insert(size_t k, const T & x)

PersistentRedBlackTree erase(size_t k)

const T & get(size_t k)

使用例

TODO

参考

Verified with

Code

完全永続赤黒木 (平衡二分木)
(DataStructure/PersistentRedBlackTree.hpp)