二分木

bitree.h

#pragma once

#include <vector>
#include <list>

// 2分木
// 再配置もきっと怖くない

template<class T=int> class bitree {
public:
	struct node;

	// 頂点数ははじめに決めておく. 辺はあとで追加する.
	bitree(int V = 1024*1024) : _vs(V) {}

	// 頂点はg.v(1)のような感じで参照. 辺は見ちゃダメ.
	node &v(int i) { splay(i); return _vs[i]; };
	node &parent(int i) { return _vs[_vs[i].parent_idx]; }
	node &left(int i) { return _vs[_vs[i].l_idx]; }
	node &right(int i) { return _vs[_vs[i].r_idx]; }
	bool is_root(int i) { return _vs[i].parent_idx < 0; }
	bool is_leaf(int i) { return _vs[i].l_idx<0 && _vs[i].r_idx<0; }
	
	// 点を追加する
	int add(T data, int parent=-1) { _vs.push_back(node{data,parent}); return _vs.size()-1; }
	// vcをvpの右要素にする.
	void addr(int vp, int vc) { _vs[vp].r_idx = vc; _vs[vc].parent_idx = vp; }
	// vcをvpの左要素にする.
	void addl(int vp, int vc) { _vs[vp].l_idx = vc; _vs[vc].parent_idx = vp; }
	
private:
	std::vector<node> _vs;
};

template<class T>
struct bitree<T>::node {
	T data;
	int parent_idx=-1;
	int l_idx=-1, r_idx=-1;
};