Pull to refresh

Comments 17

Александр, респектище вам за отличные статьи! Keep on!
Серия статей просто супер, тока что-то не особо много комментариев :)
А всё настолько круто, что по существу то и нечего комментировать. Мне вот не понятно, кто минусы таким статьям ставит. Чтобы это делать — нужно иметь веские аргументы, но что то их не видно. Неужели на хабре кому-то неугодны такие статьи? удивительное дело
ну минусуют те, кто видимо не понял в чем суть
Ну так есть же кнопочка — воздержаться (она же посмотреть результат). Ну мимо пройти на худой конец можно, раз ничего не понял. Может промахиваются мышкой? последняя надежда на адекватный вариант ;)
сам порой недоумеваю зачем так делать
Предпоследний абзац расстроил :)
А статьи просто супер. Кстати, чем картинки рисованы?
Microsoft Visio 2010.
Одна геометрическая иллюстрация в первой части создана с помощью GeoGebra.
Упоминанием Дурова? Или тем что за бугром ничего не знают по данной теме (возможно и знают но под другим именем)?
Да, есть ещё одна очень интересная и imho полезная, малоисследованная операция — обмен кусками между декартовыми деревьями, представляющими различные массивы. В принципе, это почти то же самое (массивы можно было бы склеить), но так удобнее понимать.

Пример задачи: реализовать операцию «обменять на отрезке все элементы на чётных позициях с элементами на нечётных».
Тогда будем хранить все чётные элементы в одном дереве, а нечётные — в другом.
Вырежем куски этого отрезка из каждого из деревьев:
A1 | A2 | A3 — нечётные элементы
B1 | B2 | B3 — чётные элементы

а теперь склеим по пути A1 — B2 — A3 и B1 — A2 — B3 — получим нужный обмен.
Очень забавная картинка :) Ну конкретно эта задача не очень осмысленна (просто олимпиадная задачка с чемпионата СПбГУ :), но, помнится, похожий приём применяли в какой-то гораздо более ценной задаче, у которой, правда, было более быстрое решение с помощью нескольких сдвинутых деревьев отрезков (мне кажется, это задача E с четвертьфинала ACM 2009, северный подрегион). Возможно, где-то ещё ему найдётся применение :)
PS. Да, буду очень благодарен, если кто-то всё-таки найдёт и выложит куда-нибудь/пришлёт мне/каким-либо иным способом доведёт до общественности информацию о всех известных в западной и вообще в научной литературе подобных структурах.

Я слышал, что есть структура данных Rope, которая позволяет делать склеивание за O(1), однако я ничего не знаю про разрезание и реальную эффективность использования на практике — если кто знает, поделитесь, plz. Если кто ещё что-то такое знает, тоже пишите :)
Сейчас реализовывая понял еще одно огромное преимущество дерева с неявным ключом: оно полностью immutable. Можно переделать все поля на final вычисляя size сразу (непонятно зачем рекалк нужен) и тогда сразу видно полная immutable этого дерева.

А если соответсвенно сделать лист — получится полностью immutable лист. И очень быстрый. Очень круто.
в западной литературе, статьях и Интернете ни одного упоминания о декартовом дереве по неявному ключу мне найти не удалось.


На английском оно называется implicit treap.
Отличная статья, спасибо.
Sign up to leave a comment.

Articles