Что такое молния и как она связана с древовидной структурой?

15

Я читал главу в LYAH, которая не имела для меня никакого смысла. Я понимаю, что молнии могут произвольно пересекать древовидную структуру, но мне нужно кое-что прояснить. Кроме того, могут ли молнии быть обобщены на любую структуру данных?

n_ary_crazy
источник
3
Это, вероятно, больше подходит для информатики , хотя работа по обобщению застежек-молний включает довольно много технических механизмов.
Дейв Кларк,
6
Молния - это то, что вы всегда должны держать закрытым, особенно при обходе дерева.
Андрей Бауэр

Ответы:

14

В целом, молния - это структура данных с дырой в ней. Молнии используются для обхода / манипулирования структурами данных, а отверстие соответствует текущему фокусу обхода. Обычно имеется также элемент рассматриваемой структуры данных, так что у него есть (список) молния и список или (дерево) молния и дерево. Молния позволяет программисту эффективно перемещаться по структуре данных, даже заменяя элемент в фокусе. Пара молнии и элемент в фокусе удовлетворяют ограничению, согласно которому размещение элемента в фокусе в отверстии дает исходную структуру данных.

Молния может быть обобщена на произвольные индуктивные типы данных. Эта концепция может быть определена с помощью индексации по типу (см. Типы с индексацией по типу ). Они также связаны с идеей производной структуры данных и были изучены с точки зрения теории категорий .

Дэйв Кларк
источник
2

Застежка-молния - это, как правило, пара вещей: это структура с отверстием, фокус , показывающий , где в структуре вы находитесь, вместе с дорожкой , записывающая, как вы попали в этот фокус. (Этот путь - след Хлебных крошек ЛЯХА.)

Путь - это то, как вы на самом деле применяете изменения к структуре: «идти вниз, идти налево, увеличивать значение». Многократно применяя «идти вверх» ( go_upв статье Хуэта ) на этом этапе, вы можете пересмотреть свои шаги и в итоге получить новую, мутированную копию оригинальной структуры.

Они действительно могут быть обобщены на другие структуры:

Фрэнк Шиарар
источник