[s1 | 2023] Алгоритмы и структуры данных, М. В. Первеев, лекция 6

• Видео начинается с объяснения связанных списков, которые являются одним из способов хранения данных без использования массивов.  

• В этой модели памяти данные хранятся в виде объектов, которые ссылаются друг на друга.  

• Односвязный список - это простой способ хранения данных в связанных списках.  

• В каждой ячейке списка хранятся данные и ссылка на следующий элемент.  

• Односвязный список позволяет легко добавлять элементы в конец списка и вставлять элементы в произвольное место.  

• Вставки в начало и конец списка также не вызывают проблем.  

• В видео представлен псевдокод для добавления элементов в односвязный список и вставки элементов в произвольное место.  

• Односвязные списки позволяют вставлять элементы в произвольное место и удалять их из произвольного места, но не поддерживают индексацию.  

• Эффективная вершина используется для создания зацикленного списка.  

• Двусвязные списки имеют ссылки на предыдущую и следующую вершины, что позволяет удалять элементы из произвольного места и поддерживать консистентное состояние.  

• Стек и очередь могут быть реализованы с использованием односвязных списков без амортизации и без необходимости оценки.  

• Деревья и кучи могут быть реализованы с использованием списков, что позволяет управлять элементами в произвольных местах и удалять их из произвольных мест.  

• В видео обсуждается идея использования деревьев для реализации связанных списков.  

• Деревья позволяют хранить ссылки на элементы и легко добавлять и удалять элементы.  

• Создается структура, которая позволяет быстро индексироваться в связанном списке.  

• Каждый уровень структуры отвечает за доступ к определенному количеству элементов списка.  

• Описывается алгоритм индексации в дереве, основанный на переходе между вершинами и использовании дополнительной памяти.  

• В результате получается структура, которая позволяет осуществлять индексацию в связанном списке за логарифмическое время.  

• Обсуждается возможность сделать индексирование в массиве быстрее, чем за логарифм.  

• Оказывается, что это невозможно, так как в массиве нет возможности перемещаться по ссылкам.  

• Дерево отрезков и бинпо похожи на структуру, обсуждаемую в видео.  

• Вставка в конец дерева отрезков и бинпо работает за логарифм действий.  

• Вставка и удаление в конец дерева отрезков и бинпо работают нормально.  

• Вставка и удаление в произвольное место в дереве отрезков и бинпо могут быть сложными.  

• В заключение обсуждается возможность добавления и удаления элементов в конец дерева отрезков и бинпо.  

• В целом, добавление и удаление в конец работает нормально, но удаление из произвольного места может быть сложным.  

• Видео обсуждает понятие персистентности, которое позволяет хранить копии структуры данных перед каждым изменением.  

• Пример персистентного стека показывает, как можно откатиться к любой версии структуры данных и выполнить с ней любую операцию.  

• Персистентность используется в различных областях, включая хранение истории изменений в социальных сетях и чат-системах.  

• В примере с персистентным стеком можно прочитать стек в любой версии, просто идя по ссылкам от вершины к вершине.  

• В видео обсуждается персистентность - свойство структур данных, позволяющее откатиться к любой версии и выполнить операцию над ней.  

• Для стека это реализуется легко, так как можно запомнить ссылки на голову и хвост для каждой версии.  

• В очереди возникают проблемы с откатом к старым версиям, так как ссылки идут слева направо от головы к хвосту.  

• Если сделать ссылки только в одном направлении, от хвоста к голове, очередь превратится в стек, так как можно будет только добавлять в конец и удалять с конца.  

• Полная персистентность - это когда можно откатиться до любой версии и выполнить любую операцию над ней.  

• С очередью это не получается реализовать, так как не получается создать древовидную структуру версий.  

• Можно сделать такую персистентность, чтобы каждая следующая версия зависела от предыдущей.  

• В видео обсуждается понятие частичной персистентности, когда каждая следующая версия получается из предыдущей, но не может быть сделана из произвольной версии.  

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

• В видео приводятся примеры использования частичной персистентности в структурах данных, таких как персистентные массивы и деревья.  

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

• В видео отмечается, что пользователи должны запомнить, куда им нужно вставить, чтобы сохранить ссылку на предыдущую версию.  

• Это может вызывать диссонанс, но по-другому сделать нельзя.