288
правок
Изменения
Нет описания правки
{{Определение
|def=Мы называем ADT '''полностью персистентными'''(англ. fully persistent), если, помимо интерфейса, все операции сохраняют операнды неизменными, таким образом, что операнды и результаты таких операций могут быть свободно используемы повторно во время дальнейшего хода вычислений.
Мы называем структуру данных (как реализацию абстрактного типа данных англ.ATD) полностью персистентной, если она эффективно реализует все операции предполагаемого, полностью персистентного ADT.}}
===Интерфейс===
Решающим моментом является то, что мы допускаем множественные ссылки на одно и то же поддерево: хотя концептуальное представление постоянных массивов - ориентированные деревья, их представление в памяти различно. Мы допускаем, что узел может быть преемником многих разных узлов.
Дано двоичное дерево с несколькими ссылками B = (N,L,R) и узел ''p'' ∈ N. Пишут LEFT(''p'') = ''q'', если ''q'' является единственным приемником ''p'' в(N,L) и, если такого ''q'' не существует, пишем LEFT(''p'')= ⊥, предполагая, что ⊥ не содержит N. Аналогично, пишут RIGHT(p) = ''q'', если q является единственным приемником p в(N,R) и, если такого q не существует, пишем RIGHT(''p'')= ⊥. Мы будем называть LEFT (''p'') левым дочерним элементом p и RIGHT (''p'') правым дочерним элементом.
В B = (N, L∪R) узел ''p'' ∈ N может иметь много прямых предшественников ''q''. Тогда ребра (''q'', ''p'') ∈ E называют ссылками от q до p.
