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

Декартово дерево
Автор agul, 13 лет назад, По-русски
Задача: http://informatics.mccme.ru/moodle/mod/statements/view.php?id=1974#1

В каких случаях дерево построить невозможно?
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Возможно в любом случае. И при этом при заданных b[i] дерево определяется однозначно.
В жизни мы обычно стараемся выбрать приоритеты случайно(b[i] в задаче), чтобы получить ожидаемую высоту O(logn)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Есть алгоритм, делающий это за O(N), если вершины отсортированы по ключу (ai). По-моему, придумать его - достаточно полезное упражнение.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Я когда-то себе сделал пометку для использования на своих занятиях одного классного материала по этой теме.
Во всяком случае лучшего подбора материала по этой теме, сконцентрированного в одном месте, я больше нигде не видел (на данный момент).
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Поддерживаю. Тоже недавно, когда читал про них лекцию, давал ссылку как раз туда.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +29 Проголосовать: не нравится
      Хех, спасибо. Всегда приятно, что хоть не зря писал все-таки :)
      → Ответить