Всем привет!
Взялся тут выучить декартово дерево, встал вопрос реализации. Кто как пишет? Емакс читал, но реализация оттуда не понравилась -- не очень люблю на олимпиадах использовать указатели. Да и рекурсия это не очень круто, наверное.
В общем, обладателей хорошей быстрой простой красивой реализации всяких разных декартовых деревьев и операций на них -- прошу поделиться мастерством.
Большое спасибо.
на массивах со счетчиком, рекурсивно
Так и напрашивается фраза: "Ваши проблемы!". Код с указателями тупой, очевидный и короткий. Вы можете самостоятельно хорошенько подумать и избавиться от указателей, но то, что у Вас получится, вызывает у меня ассоциацию вот с этим.
e-maxx уже поделился. Я очень глубоко сомневаюсь в том, что его код можно ощутимо сократить или сделать проще.
Можете погуглить нерекурсивную реализацию (она существует). Можете даже попробовать додуматься до нее самостоятельно (в Кормене есть соответствующее упражнение).
Меня очень парила передача указателей по ссылке в функции, от этого можно избавиться, просто вернув
pair<node*, node*>в случае split иnode*в случае merge. А в остальном вроде указатели нормально совершенно смотрятся.У меня есть два упрощения для таких ситуаций:
Позволяет избавиться от кучи звёздочек, сказав, что node — это уже указатель (потому что не-указатели не нужны), а также не извращаться с возвратом пар, потому что удобные ссылки. Более того, не нужно никаких промежуточных переменных в split, потому что основной указатель передаются по значению и можно сразу вызывать дочерние split, модифицирующие поля вершины напрямую.