#include <iostream>
#include <vector>
using namespace std;

class Tree
{
public:
	Tree() : root(NONE) { }
	~Tree() { }

	void add(const string& data);
	void remove(const string& data);
	string dump();

private:
	typedef uint32_t index;
	static const index NONE = static_cast<index>(-1);

	class Node
	{
	public:
		Node(const string& data, index parent, index left, index right) :
			data(data), parent(parent), left(left), right(right)
		{
		}

		string data;
		index parent, left, right;
	};
	index find(const string& data, index& parent, bool& left);
	void remove_replace(index inode);
	index leftmost(index inode);
	string dump(index inode, const string& tab, const string& tabs);

	vector<Node> nodes;
	index root;
};

const Tree::index Tree::NONE;

void Tree::add(const string& data)
{
	index inode = nodes.size(), iparent;
	bool left;
	if (find(data, iparent, left) != NONE) throw runtime_error("дубликат: " + data);

	nodes.emplace_back(data, iparent, NONE, NONE);
	(iparent == NONE ? root : left ? nodes[iparent].left : nodes[iparent].right) = inode;
}

void Tree::remove(const string& data)
{
	index inode, iparent;
	bool left;
	if ((inode = find(data, iparent, left)) == NONE) throw runtime_error("не найдено: " + data);

	Node& node = nodes[inode];
	if (node.left != NONE && node.right != NONE)
	{
		// удаление элемента с 2 детьми
		index rlm = leftmost(node.right), rlmp = nodes[rlm].parent, rlmr = nodes[rlm].right;
		node.data = move(nodes[rlm].data);
		(rlm == nodes[rlmp].left ? nodes[rlmp].left : nodes[rlmp].right) = rlmr;
		if (rlmr != NONE) nodes[rlmr].parent = rlmp;
		remove_replace(rlm);
	} else
	{
		// удаление элемента с 0 или 1 детьми
		index maybe_child = node.left != NONE ? node.left : node.right;
		(iparent == NONE ? root : left ? nodes[iparent].left : nodes[iparent].right) = maybe_child;
		if (maybe_child != NONE) nodes[maybe_child].parent = iparent;
		remove_replace(inode);
	}
}

string Tree::dump()
{
	return root == NONE ? "<пусто>" : dump(root, "\t", "");
}

Tree::index Tree::find(const string& data, index& iparent, bool& left)
{
	iparent = NONE;
	index inode = root;
	while (inode != NONE)
	{
		Node& node = nodes[inode];
		int cmp = data.compare(node.data);
		if (cmp == 0) break;
		iparent = inode;
		inode = cmp < 0 ? node.left : node.right;
		left = cmp < 0;
	}
	return inode;
}

// Удаляет узел inode из хранилища узлов,
// заменяя его последним и исправляя индексы ссылавшихся на последний.
void Tree::remove_replace(index inode)
{
	index ilast = nodes.size() - 1;
	if (inode != ilast)
	{
		Node& node = nodes[inode];
		node = move(nodes[ilast]);

		if (node.parent == NONE)
			root = inode;
		else
		{
			Node& parent = nodes[node.parent];
			(ilast == parent.left ? parent.left : parent.right) = inode;
		}
		if (node.left != NONE) nodes[node.left].parent = inode;
		if (node.right != NONE) nodes[node.right].parent = inode;
	}
	nodes.pop_back();
}

Tree::index Tree::leftmost(index inode)
{
	for (index next; (next = nodes[inode].left) != NONE; inode = next) ;
	return inode;
}

string Tree::dump(index inode, const string& tab, const string& tabs)
{
	Node& node = nodes[inode];
	string r = node.data + " (#" + to_string(inode) + ", parent = " + (node.parent == NONE ? "NONE" : "#" + to_string(node.parent)) + ")";
	for (int ic = 0; ic < 2; ic++)
	{
		index child = ic == 0 ? node.left : node.right;
		if (child != NONE)
			r += "\n" + tabs + tab + (ic == 0 ? "L" : "R") + " = " + dump(child, tab, tabs + tab);
	}
	return r;
}

int main()
{
	string ops[] =
	{
		"+555",
		"+444",
		"+666",
		"+321",
		"+445",
		"+777",
		"+600",
		"-гетеросексуальность",
		"+600",
		"-555",
		"-777",
		"-444",
		"-445",
		"-600",
		"-321",
		"-666",
	};

	Tree tree;
	cout << tree.dump() << endl << endl;
	for (const auto& op : ops)
	{
		bool add = op[0] == '+';
		string arg = op.substr(1);
		cout << (add ? "Добавление" : "Удаление") << " " << arg << endl;

		try
		{
			if (add)
				tree.add(arg);
			else
				tree.remove(arg);
		} catch (const exception& err)
		{
			cout << err.what() << endl << endl;
			continue;
		}

		cout << tree.dump() << endl << endl;
	}
	return 0;
}