Декартово дерево: правила построения и базовые операции

Задача «Следующий»: informatics.msk.ru/mod/statem...

[@onlyc583]

Большое спасибо за урок! Очень просто и понятно объяснили как работает декартово дерево, как балансируется и как его писать

[@CR-tj6gk]

это самое лучшее что я видел в своей жизни

[@daniilevsienko4060]

Очень понятное объяснение! Спасибо!

[@user-jn4lk2ne9k]

Спасибо за хорошее описание! Декартово дерево стало более понятным :))

[@getawayunclejohn7107]

Легендарен, спасибо большое за видео!!!!❤

[@user-nw2eb6lx1k]

Отличное обучающее видео.

[@TheSemgold]

Кстати интересно поднять другую реализацию, где удаление без сплита, а инсперт без мерджа. То есть сначала спускаемся по ключу, а потом уже выполняем операции.

[@op_ulstu]

Insert без merge: Найдём место, куда нужно вставить новый элемент, обычным спуском по двоичному дереву поиска, как мы делали это в предыдущем видео. Правда, теперь новый элемент не всегда должен стать листом, потому что у него может быть слишком большой приоритет. Следовательно, нам нужно остановить поиск на первом элементе, приоритет которого меньше, чем приоритет нового элемента. Новый элемент должен будет занять место этого старого элемента. Старый элемент придётся разрезать (split) по ключу нового элемента и сделать получившиеся части детьми нового элемента. Erase без split: Опять же, найдём при помощи спуска по двоичному дереву поиска тот элемент, который нужно удалить. Заменим его на объединение (merge) его детей.

[@kpanat]

Только что написал реализацию шаблонного класса бинарного дерева с простейшим набором функций типа вставки удаления и т.п. Всё протестил как следует работает. Вот только блин деревья получаются фиговые... нифига несбалансированные. А какой тогда от них толк? И тут наткнулся на это. Ну что же это хорошо, подумал я. Вот как надо реализовывать деревья чтобы они были шустрыми... Интересно вобщем было. Надо сделать такое. Может где пригодится...

[@user-jv6ks7cd3i]

А почуме функции merge, split не сделать friend для class Node ?

[@op_ulstu]

Node в видео объявлен как struct, следовательно, все его поля уже публичны и доступны для функций merge и split. Если бы Node был объявлен как class, и поля были бы приватными, то, действительно, функции пришлось бы помечать как friend. Но код становится более громоздким, а выгода не ясна.

[@kpanat]

@@op_ulstu чтоб выяснить выгоду надо протестить... так сразу и не скажешь...

[@Kolbastero]

Зачем в классе Treap мы пишем static перед Node *merge(Node *a, Node *b).... . Зачем нам тут static?

[@op_ulstu]

Функции merge и split мы не вызываем от какого-то конкретного объекта Treap (a.merge(b), root.split(key, less, greater)), а передаём им дерамиды, которые нужно обработать, через аргументы (merge(a, b), split(root, key, less, greater)). Этим функциям нет необходимости знать о внутреннем состоянии какого-то экземпляра Treap, они работают одинаково для всех Treap. Следовательно, их можно сделать статическими. На самом деле, если убрать static, остальной код не изменится, так как функции merge и split приватные и вызываются только изнутри класса. Поэтому словом static мы, по сути, просто подчеркнули, что эти функции не относятся к какому-то конкретному объекту. Если вы изучите код реализаций дерамиды из интернета, вы увидите, что часто функции merge и split вообще делают внешними по отношению к классу Treap (правда, тогда приходится либо как-то предоставлять доступ к полям Treap, либо помечать merge и split как friend).

[@klausvreinherz7145]

у вас звезда амперсанд в аргументе сплита - это бан на полчаса

[@op_ulstu]

Что именно вас смутило? a и b в split() - это указатели на вершины результирующих деревьев, они имеют тип Node *. Это выходные параметры, мы хотим изменять их внутри split, поэтому передаём их по ссылке: Node *&. Если хотите, можете возвращать из split пару указателей: pair split(Node *n, int key).

[@klausvreinherz7145]

@@op_ulstu это некоторый мем с лабораторных работ по C в моём универе, если подойти с таким на сдачу лабы, то вас не будут принимать следующие полчаса, так как в си такая конструкция не имеет смысла. Если говорить о том что меня смутило в этом видеоролике, то мне и словами не описать ту боль которую мне пришлось пережить чтобы понять как дерево на самом деле работает, то как вы объяснили на визуализации конечно складно и понятно, но код так не работает, (я говорю о ф-ии split). Возможно этого поверхностного "понимания" достаточно чтобы использовать такой подход как инструмент в олимпиадных задачах и далеко не всем хочется знать как обстоят дела на самом деле

[@op_ulstu]

@@klausvreinherz7145 Код в видео написан на C++, а не на C. Здесь & - это не операция взятия адреса (в объявлении типа эта операция всё равно не имела бы смысла), а признак ссылки. В показанном коде *& - не две взаимообратные операции, а ссылка на указатель.

[@klausvreinherz7145]

@@op_ulstuпоэтому я и упомянул что лабораторные мы писали на си

[@klausvreinherz7145]

@@op_ulstu так как этот мем был несколько неуместен, но всё же достойным упоминания в обществе моих одногрупников, с коими я и пытался смотреть ваше видео