288
правок
Изменения
→Интерфейс
Мы называем структуру данных (как реализацию абстрактного типа данных англ.ATD) полностью персистентной, если она эффективно реализует все операции предполагаемого, полностью персистентного ADT.}}
===Интерфейс===
{{Рамка}}…
* [X] статический конструктор, который принимает элемент X и возвращает массив, который содержит X в качестве его единственного элемента.
* '''LENGTH''' [A] возвращает длину массива A.
* '''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-деревья, можно найти в соответствующих разделах сайта)
