struct ListNode
{
	bool isString;
	std::string string;
	int value;

	ListNode()
	{
		isString = true;
		string = "No name";
		value = NULL;
	}

	ListNode(std::string str)
	{
		isString = true;
		string = str;
		value = NULL;
	}

	ListNode(int val)
	{
		isString = false;
		value = val;
	}
};

struct TableName
{
	std::string name;
	std::string value;
	int size;

	TableName(std::string name, std::string value)
	{
		this->name = name;
		this->value = value;
	}

	TableName(std::string name, std::string value, int s)
	{
		this->name = name;
		this->value = value;
		size = 0;
	}
};


struct Pair
{
	std::string name;
	std::vector<TableName> nameRow;
	std::list<std::vector<ListNode>> list;

	Pair()
	{
		name = "No name";
		TableName firstRow("Id", "Int");
		TableName secondRow("Name", "String");
		TableName thirdRow("Value", "Int");
		std::vector<TableName> newTable;
		newTable.push_back(firstRow);
		newTable.push_back(secondRow);
		newTable.push_back(thirdRow);
		nameRow = newTable;
	}

	Pair(std::string strName, std::list<std::vector<ListNode>> array, std::vector<TableName> tableNameRow)
	{
		name = strName;
		list = array;
		nameRow = tableNameRow;
	}
};

struct TreeNode
{
	Pair value;
	TreeNode* left, * right;

	bool operator<(const TreeNode& other)
	{
		return value.name < other.value.name; // leksicographical compair
	}
	bool operator==(const TreeNode& other)
	{
		return value.name == other.value.name; // leksicographical compair
	}

	TreeNode()
	{
		value.name = "NoName";
		left = right = nullptr;
	}

	TreeNode(int s)
	{
		value.name = "NoName";
		left = right = nullptr;
	}

	TreeNode(const Pair& value)
	{
		this->value = value;
		left = right = nullptr;
	}
};

class Tree
{
private:
	TreeNode* root;

	TreeNode* find(TreeNode* r, const std::string& key) const
	{
		if (!r)  return nullptr;

		if (r->value.name == key) return r;

		return r->value.name < key ? find(r->left, key) : find(r->right, key);

	}

	TreeNode* insert(TreeNode*& r, const Pair& val)
	{
		if (!r)
		{
			r = new TreeNode(val);
			return r;
		}
		if (val.name < r->value.name) r->left = insert(r->left, val);
		else r->right = insert(r->right, val);
		if (val.name == r->value.name) return r;

	}

	TreeNode* findParent(TreeNode* r, const std::string& key)
	{
		if (!r) return nullptr;
		if (r->left->value.name == key || r->right->value.name == key)
		{
			return r;
		}
		findParent(r->left, key);
		findParent(r->right, key);
	}

	void remove(TreeNode*& r, const std::string& name)
	{
		TreeNode* toDelete = find(name);
		TreeNode* parent = findParent(r, name);

		int children = !toDelete->left + !toDelete->right;
		if (children == 0)
		{
			if (parent->left->value.name == name) parent->left = nullptr;
			else parent->right = nullptr;

			delete toDelete;
			return;
		}

		else if (children == 1)
		{
			TreeNode* pos = parent->left->value.name == name ? parent->left : parent->right;
			TreeNode* par = findParent(r, name);

			toDelete->left ? pos = toDelete->left : pos = toDelete->right;
			delete toDelete;
			return;
		}

		TreeNode* del;
		TreeNode* maxLeft = toDelete->left;
		while (maxLeft->right)
		{
			del = maxLeft;
			maxLeft = maxLeft->right;
		}

		maxLeft->right = nullptr;
		toDelete->value = maxLeft->value;
		delete maxLeft;
	}

	TreeNode* copy(TreeNode* r, TreeNode* other)
	{
		if (!r) return nullptr;

		TreeNode* c = new TreeNode();

		c->left = copy(r->left, other);
		c->right = copy(r->right, other);

		return c;
	}

	void clear(TreeNode* r)
	{
		if (!r) return;

		clear(r->left);
		clear(r->right);

		delete r;
	}

public:
	Tree() : root(nullptr) {}
	Tree(const Tree& other)
	{
		copy(root, other.root);
	}
	~Tree()
	{
		clear(root);
	}

	TreeNode* find(const std::string& key) const
	{
		return find(root, key);
	}

	TreeNode* insert(const Pair& addedNode)
	{
		insert(root, addedNode);
		return root;
	}

	bool remove(const std::string& removedName)
	{
		remove(root, removedName);
	}

};