Всем привет. Совсем недавно я, наконец, познакомился с такой замечательной структурой, как дерамида. В теории я понял ее практически отлично. Но вот когда дело дошло до реализации, я понял, что не все так хорошо. Долгое время я думал, что знаю все нужные аспекты Java для ОП, но, как оказалось, не все.

Вот то, что я смог написать сам — http://pastie.org/5084738 Это, вроде, самая "нубская" реализация Декартова Дерева. В теории я знаю о том, как можно избавится от приоритетов, о переходе от явного ключу к неявному, но я хочу пройти через все этапы усовершенствований, дабы понимать, что к чему.

Так, много слов, а сути нет. На данном этапе я хочу модифицировать функции add() и remove(), чтобы они использовали по одной операции split()/**merge()**, а не по три. Ясно, как это делается:

Add(x) — спускаемся по дереву поиска, пока не найдем вершину с приоритетом меньшим, чем у добавляемый вершины, посплитим ее по x, и поставим получившиеся l и r как l и r добавляемой вершины, ее же поставим на место найденной

Remove(x) — спускаемся по дереву, находим искомую вершину, мерджим ее l и r, ставим результат на место этой вершины, вуаля

На примере remove() покажу, в чем, собственно, моя проблема. Вот как, по сути, она должна выглядеть:

void remove(int x) {
	Node t = root;
	while (t.x != x)
		t = x < t.x ? t.l : t.r;
	t = merge(t.l, t.r);
}

Но это не работает в силу того, что в данном случае t — лишь одна из ссылок на вершину дерева и, меняя ее, я не меняю само дерево, я лишь меняю эту ссылку. И вот, я не знаю, как правильно это реализовать. То же самое с add().

Возможно, я очень опозорился этим постом, но что ж, ладно, я только учусь, так что ничего. Если кто может помочь советом по реализации или каким-нибудь еще советом — буду очень благодарен. Также буду благодарен за ссылки на готовые реализации, как такого дерева, так и по неявному ключу, чтобы было с чем сравнивать. На емакс и хабр ссылок не надо, читал уже :)