Блог пользователя 1k_trash

Автор 1k_trash, 10 лет назад, По-русски

Всем привет!

Взялся тут выучить декартово дерево, встал вопрос реализации. Кто как пишет? Емакс читал, но реализация оттуда не понравилась -- не очень люблю на олимпиадах использовать указатели. Да и рекурсия это не очень круто, наверное.

В общем, обладателей хорошей быстрой простой красивой реализации всяких разных декартовых деревьев и операций на них -- прошу поделиться мастерством.

Большое спасибо.

  • Проголосовать: нравится
  • -19
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

на массивах со счетчиком, рекурсивно

»
10 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

не очень люблю на олимпиадах использовать указатели

Так и напрашивается фраза: "Ваши проблемы!". Код с указателями тупой, очевидный и короткий. Вы можете самостоятельно хорошенько подумать и избавиться от указателей, но то, что у Вас получится, вызывает у меня ассоциацию вот с этим.

В общем, обладателей хорошей быстрой простой красивой реализации всяких разных декартовых деревьев и операций на них -- прошу поделиться мастерством.

e-maxx уже поделился. Я очень глубоко сомневаюсь в том, что его код можно ощутимо сократить или сделать проще.

Да и рекурсия это не очень круто, наверное.

Можете погуглить нерекурсивную реализацию (она существует). Можете даже попробовать додуматься до нее самостоятельно (в Кормене есть соответствующее упражнение).

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Меня очень парила передача указателей по ссылке в функции, от этого можно избавиться, просто вернув pair<node*, node*> в случае split и node* в случае merge. А в остальном вроде указатели нормально совершенно смотрятся.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    У меня есть два упрощения для таких ситуаций:

    struct _node {...};
    
    typedef _node *node;
    
    node merge(node l, node r) { ... }
    void split(node v, int key, node &l, node &r);
    

    Позволяет избавиться от кучи звёздочек, сказав, что node — это уже указатель (потому что не-указатели не нужны), а также не извращаться с возвратом пар, потому что удобные ссылки. Более того, не нужно никаких промежуточных переменных в split, потому что основной указатель передаются по значению и можно сразу вызывать дочерние split, модифицирующие поля вершины напрямую.