Декартово дерево: Часть 1. Описание, операции, применения

[karlicos]

Да, хабр точно торт :) Спасибо, отличная статья)

[oYASo]

Обидно только, что такие крутые статьи читает 1/100 хабра. Зато вот напиши очередную статью «как правильно ложиться спать», и все, +300 голосов, 600 комментов.

[Joshua]

Не совсем понятно, чем это лучше, например Nested set? Порядок О — аналогичный, алгоритмы поиска — примерно такие-же, но алгоритмы создания, слияния, удаления и переноса — проще.
Можете сделать сравнительный анализ?

[no_smoking]

Задачи разные. И что все носятся с этими Nested set :)

[Joshua]

Поясните, плиз. Так понял, задача — ускорить операции поиска, вставки и удаления. Есть какие-то еще?

[Skiminok]

Еще огромнейшее количество применений, просто в первую часть они не влезли :)

[no_smoking]

Хотя бы тем что nested set не ускорит поиск по ключу как это. Nested set больше нужен для построения иерархических каталогов в базе данных чтобы можно было быстро выбрать нужную ветку а не для поиска например цены.

[happybyte]

Было бы интересно видеть сравнение перформанса с реализацией RBT без рекурсии.

[Skiminok]

Я видел одно полноценное сравнение (стр. 69-77). В нем дерамида выиграла по производительности (на рандомных тестах величины 10000/50000/100000) у RBT, Radix tree, списка с пропусками и AA-дерева.

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

[kotehok]

По моему опыту, на больших объёмах данных у декартова дерева скорость процентов на 20% ниже, чем у RBT, а ещё быстрее процентов на 5 будет работать 2-3 дерево, за счёт того, что в этих случаях производительность зависит от объёма используемой памяти на узел, а в 2-3 дереве можно в листьях не хранить указатели на детей (правда, кода получается жутко много). Естественно, рассматриваются нерекурсивные реализации. Отметим, правда, что при хранении дополнительных данных вроде количества/суммы по поддеревьям нерекурсивная реализация требует моделирования стека или хранения предка (ну второе вообще по памяти жесть, а вот первое реально используется).

Но мне пока так никто и не объяснил, как нормально без лишних данных в RBT делать merge, а без этого невозможно их адаптировать для использования по неявному ключу (а именно для этого и придумывалось декартово дерево в российском ACM-программировании).

А ещё нерекурсивная реализация декартова дерева выглядит красиво :) К сожалению, при попытке запостить код все отступы куда-то исчезают, несмотря на мои попытки использовать теги code и pre… (может, я чего-то не понимаю???)

[Skiminok]

В крайнем случае всегда можно выложить код на какой-нибудь pastie.org, и оставить здесь ссылку. Интересно увидеть ведь.

[kotehok]

Да, точно… что-то мне не пришло это в голову, хотел прямо сюда :)
Вот пример процедуры merge, написанной нерекурсивно.

[Skiminok]

Оставлю здесь код из ссылки kotehok, на случай если его удалят с acm.spbgu.ru:

static ltree_t *ltree_merge (ltree_t *L, ltree_t *R) {
  ltree_t *Root, **U = &Root;

  while (L && R) {
    if (L->y > R->y) {
      *U = L;
      U = &L->right;
      L = *U;
    } else {
      *U = R;
      U = &R->left;
      R = *U;
    }
  }

  *U = L ? L : R;

  return Root;
}

[StopKran]

О, есть шанс ещё раз попробовать понять эту структуру данных!

[Chvanikoff]

Статья на главной — иллюстраций нет :(
С ними было бы попонятнее…

[Skiminok]

Недопонял. В статье с десяток иллюстраций, все на habreffect`e.

[Chvanikoff]

Видимо я неудачно зашел — ни одной не было, перезагрузка не помогала.
Сейчас вижу, буду дочитывать материал…
Кстати, спасибо за топик — тема интересная.

[tyomitch]

Про терминологию: встречал название «курево» (куча+дерево), удачно созвучное с «treap».

[SegaZero]

жарево, парево, серево, варево, курево :)
извините, неудержался:)

[Skiminok]

Кстати, еще из забавных названий.
Пирамида + Дерево => ПиВо.

[hr0nix]

Круто. Кажется, где-то еще нужно написать, что эта структура данных meldable, но не mergeable.

[AlMag]

Введение в курево отличное.
Ждем второго поста. Дерамида по неявному ключу + множественные операции + инверсия на отрезке — это сила данной структуры.

[alexeyrom]

По-моему, было бы лучше в примерах на C# писать сразу Treap<T> без специализации на int.

[Skiminok]

Теоретически да, я говорил об этом в тексте. Но тогда, во-первых, T where T: IComparable<T>. Во-вторых, потеряется возможность сравнивать ключи операторами — теряется наглядность кода. Эта статья более учебная, чем обобщенная, поэтому я предпочитаю наглядность.

[Skiminok]

Microsoft Visio 2010.

[SemenMartynov]

Здесь есть видео по Декартову дереву.

[cptgav]

в статье битые ссылки, после реорганизации сатйа. Если можно — поправьте.