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

Поділитися
Вставка
  • Опубліковано 24 гру 2024

КОМЕНТАРІ • 22

  • @onlyc583
    @onlyc583 9 місяців тому +2

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

  • @daniilevsienko4060
    @daniilevsienko4060 Рік тому +2

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

  • @CR-tj6gk
    @CR-tj6gk 2 роки тому +5

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

  • @getawayunclejohn7107
    @getawayunclejohn7107 Рік тому +2

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

  • @Юрий-к3й8д
    @Юрий-к3й8д 4 роки тому +5

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

  • @НатальяАлфёрова-и6т

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

  • @georgevonfloydmann1797
    @georgevonfloydmann1797 6 місяців тому

    О да, легендарное ПиВо, ака КуРево, ака ДеРамида. Было бы интересно услышать от Вас про Авл и красночерные деревья

  • @kpanat
    @kpanat Рік тому +1

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

  • @TheSemgold
    @TheSemgold 3 роки тому

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

    • @op_ulstu
      @op_ulstu  Рік тому +2

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

  • @MAKMED1337
    @MAKMED1337 3 роки тому

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

    • @op_ulstu
      @op_ulstu  Рік тому

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

    • @kpanat
      @kpanat Рік тому

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

  • @Kolbastero
    @Kolbastero 3 роки тому +1

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

    • @op_ulstu
      @op_ulstu  Рік тому +1

      Функции 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
    @klausvreinherz7145 8 місяців тому

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

    • @op_ulstu
      @op_ulstu  8 місяців тому

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

    • @klausvreinherz7145
      @klausvreinherz7145 8 місяців тому

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

    • @op_ulstu
      @op_ulstu  8 місяців тому

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

    • @klausvreinherz7145
      @klausvreinherz7145 8 місяців тому

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

    • @klausvreinherz7145
      @klausvreinherz7145 8 місяців тому

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