288
правок
Изменения
Нет описания правки
|definition=Мы называем ADT '''полностью персистентными'''(англ. fully persistent), если, помимо интерфейса, все операции сохраняют операнды неизменными, таким образом, что операнды и результаты таких операций могут быть свободно используемы повторно во время дальнейшего хода вычислений.
Мы называем структуру данных (как реализацию абстрактного типа данных англ.ATD) полностью персистентной, если она эффективно реализует все операции предполагаемого, полностью персистентного ADT.}}
* '''[X] ''' статический конструктор, который принимает элемент X и возвращает массив, который содержит X в качестве его единственного элемента.
* '''LENGTH''' [A] возвращает длину массива A.
* ε является пустым массивом, иногда также обозначается []
* '''REVERSE'''[''A''] принимает на вход массив A = [''a''0,...,''a''<sub>n-1</sub>] и возвращает [''a''<sub>n-1</sub>,...,a0].
* '''REPLACE'''[A,i, x] принимает на вход массив A = [''a''0,...,''a''<sub>n-1</sub>], индекс ''i'' = 0..''n'' − 1, и новый элемент ''x'', выводит [''a''<sub>0</sub>,...,''a''<sub>i-1</sub>, ''x'',''a''<sub>i+1</sub>,...,''a''<sub>n-1</sub>].
* ''''''A'''[i] ← ''x '''''является сокращенным обозначением A ← REPLACE(A,''i'', ''x'').
* '''INSERT'''[A,i, x] получает массив A = [''a''0,...,''a''<sub>n-1</sub>], индекс ''i'' = 0..n−1, и новый элемент x и возвращает массив [''a''0,...,''a''<sub>i-1</sub>, x,''a''i ,...,''a''n−1] = '''HEAD'''(A,''i'') · [''x''] · '''TAIL'''(A,''i)'', длина которого ''n''-1.
* '''LEFTPART'''(A): возвращает (non-deterministically) массив, представляющий последовательность префикса A.
* ''' RIGHTPART'''(A): возвращает (non-deterministically) массив, представляющий последовательность суффикса A.
Будем использовать сбалансированные деревья в качестве нашей стандартной реализации постоянных массивов. (Реализации сбалансированных деревьев, таких как AVL-деревья и B-деревья, можно найти в соответствующих разделах сайта)
Решающим моментом является то, что мы допускаем множественные ссылки на одно и то же поддерево: хотя концептуальное представление постоянных массивов - ориентированные деревья, их представление в памяти различно. Мы допускаем, что узел может быть преемником многих разных узлов.
