Left-leaning Red-Black Trees

いろいろなところで引用されています．実装が楽な赤黒木で，以下のスライドを見れば（むしろ，ほとんどコピーする感じで），簡単に実装できます．

以下は，少し普通じゃない感じで，とりあえず追加のみを実装してみたものです．64 ビット環境だとポインタに割り当てられる領域も無視できないことがあったりなかったり，という思いが反映されています．ただし，試作品なので少しだけ…．

template <typename ValueType, typename IndexType = unsigned,
	typename LessThanType = less<ValueType>,
	typename Allocator = allocator<ValueType> >
class BSTree
{
public:
	typedef ValueType value_type;

private:
	typedef IndexType index_type;

	class Node
	{
	public:
		Node() : left_(0), right_(0), value_() {}
		Node(const value_type &value) : left_(1), right_(0), value_(value) {}

		void color_flip() { set_is_red(!is_red()); }

		void set_is_red(bool is_red)
		{ if (is_red) left_ |= 1; else left_ &= ~static_cast<index_type>(1); }
		void set_left(index_type left) { left_ = (left << 1) | (left_ & 1); }
		void set_right(index_type right) { right_ = right; }

		bool is_red() const { return (left_ & 1) != 0; }
		index_type left() const { return left_ >> 1; }
		index_type right() const { return right_; }
		const value_type &value() const { return value_; }

	private:
		index_type left_;
		index_type right_;
		value_type value_;
	};

	typedef LessThanType less_than_type;
	typedef typename Allocator::template rebind<Node>::other allocator_type;

public:
	BSTree() : root_(0), nodes_(1) {}

	void insert(const value_type &value) { root_ = insert(root_, value); }

	bool has(const value_type &value) const
	{
		index_type index = root_;
		while (index)
		{
			const Node &node = nodes_[index];
			if (less_than_type()(value, node.value()))
				index = node.left();
			else if (less_than_type()(node.value(), value))
				index = node.right();
			else
				return true;
		}
		return false;
	}

private:
	index_type root_;
	vector<Node, allocator_type> nodes_;

	index_type insert(index_type index, const value_type &value)
	{
		if (!index)
		{
			nodes_.push_back(value);
			return static_cast<index_type>(nodes_.size() - 1);
		}

		if (nodes_[nodes_[index].left()].is_red()
			&& nodes_[nodes_[index].right()].is_red())
			color_flip(index);

		if (less_than_type()(value, nodes_[index].value()))
		{
			index_type left = insert(nodes_[index].left(), value);
			nodes_[index].set_left(left);
		}
		else if (less_than_type()(nodes_[index].value(), value))
		{
			index_type right = insert(nodes_[index].right(), value);
			nodes_[index].set_right(right);
		}

		if (nodes_[nodes_[index].right()].is_red())
			index = rotate_left(index);
		if (nodes_[nodes_[index].left()].is_red()
			&& nodes_[nodes_[nodes_[index].left()].left()].is_red())
			index = rotate_right(index);

		return index;
	}

	index_type rotate_left(index_type index)
	{
		index_type x_index = nodes_[index].right();
		nodes_[index].set_right(nodes_[x_index].left());
		nodes_[x_index].set_left(index);
		nodes_[x_index].set_is_red(nodes_[index].is_red());
		nodes_[index].set_is_red(true);
		return x_index;
	}

	index_type rotate_right(index_type index)
	{
		index_type x_index = nodes_[index].left();
		nodes_[index].set_left(nodes_[x_index].right());
		nodes_[x_index].set_right(index);
		nodes_[x_index].set_is_red(nodes_[index].is_red());
		nodes_[index].set_is_red(true);
		return x_index;
	}

	void color_flip(index_type index)
	{
		nodes_[index].color_flip();
		nodes_[nodes_[index].left()].color_flip();
		nodes_[nodes_[index].right()].color_flip();
	}
};