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

Нужна помощь с декартовым деревом!
Автор upd, 13 лет назад, перевод, По-русски

Здравствуйте уважаемые codeforcerы! Я читал много информации про декартовые деревья, но так и не могу реализовать декартово дерево по не явному ключу. Если у кого-нибудь имеется код прошу помогите!

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

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

Тут, похоже, не читали?

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

    Я читал и даже реализовывал обычное декартово дерево и знаю как там все работает.) Но просто не могу понять как работает split в неявном декартовом дереве...) И как оно используется. На e-maxxе не очень было понятно.

    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

      Представь, что мы просто выкинули ключ x.
      Возникает вопрос — как теперь понимать, какая вершина левее какой? Ответ простой — по ссылкам l и r это однозначно восстанавливается. А именно, из следующего логичного соотношения: все элементы поддерева v->l находятся левее элемента v, который находится левее всех элементов поддерева v->r. С помощью этого однозначно определяется порядок на всех вершинах, лежащих в декартовом дереве.
      Теперь поймём, что нам это даёт. Это нам, например, даёт возможность обращаться с деревом, как с последовательностью его вершин, упорядоченной слева направо. Теперь положим в каждую вершину дерева какую-нибудь чиселку, например значение w. Декартово дерево теперь будет работать как последовательность этих значений w. Поясню: пусть у нас есть два дерева A и B, соответствующие последовательностям a и b, если мы рассмотрим дерево merge(A, B), то получим дерево, соответствующее последовательности ab, если рассмотрим дерево merge(B, A) — то последовательности ba. Раньше мы имели право мёрджить только деревья, расположенные строго одно левее другого — теперь такого ограничения нет, мы оторвали деревья от абсолютного позиционирования на плоскости.
      Теперь осталось понять, что есть операция split. Split должен просто разбивать дерево T на две части — до элемента с номером k и после. Как её реализовывать — тут уже почитай на емаксе, там вполне доходчиво это объяснено.

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

Просто само название "неявный ключ", имхо не особо удачное. Я тоже не понимал что имеется в виду. По факту у нас есть последовательность, которую можно распечатать рекурсивно процедурой

void print(tree t)
{
    if (!t) return
    print(t->L);
    cout << t->element << endl;
    print(t->R);
}

пронумеруем элементы дерева в этом порядке, и эти номера и будут теми самыми "неявными ключами". просто если "явно" нумеровать, т.е. в каждую вершину это число записывать, то их придётся перезаписывать каждый раз при разрывании/склеивании деревьев, поэтому мы вычисляем эти числа, по ходу операций с деревом, используя поле cnt, означающее размер поддерева.

→ Ответить