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.
Отличная статья, спасибо.
Only those users with full accounts are able to leave comments. Log in, please.