288
правок
Изменения
→Интерфейс
# '''B''' - структура, то ''seq (''B'')'' обозначает строку, которая представлена ''B''.
Основываясь на вышеприведенных операциях, ADT может быть расширен следующими операциями:
# 1. [''x''0,..., ''x''n−1] является сокращением для '''CONCATENATE'''([x0],'''CONCATENATE'''([x1],'''CONCATENATE'''(...,'''CONCATENATE'''([''x''n−2],[''x''n−1])))) . Обратите внимание, что в программе оценка этого выражения всегда включает ''n-2'' конкатенации.# 2. '''REVERSE'''[''A''] принимает на вход массив A = [''a''0,...,''a''<sub>n-1</sub>] и возвращает [''a''<sub>n-1</sub>,...,a0]. # 3. '''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>]. # 4. '''A'''[i] ← ''x ''является сокращенным обозначением A ← REPLACE(A,''i'', ''x''). # 5. '''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.# 6. '''LEFTPART'''(A): возвращает (non-deterministically) массив, представляющий последовательность префикса A.# 7. * ''' RIGHTPART'''(A): возвращает (non-deterministically) массив, представляющий последовательность суффикса A.
Реализация персистентных массивом в виде сбалансированных деревьев
Будем использовать сбалансированные деревья в качестве нашей стандартной реализации постоянных массивов. (Реализации сбалансированных деревьев, таких как AVL-деревья и B-деревья, можно найти в соответствующих разделах сайта)
При использовании RAW с ограниченным размером арифметических операций, ADT для персистентных массивов могут быть реализованы таким образом, чтобы каждая из его операций выполнялась во времени O (logn).Если длины массивов представляются внутри границ слова. В противном случае временная граница O (min ((log n)2, k2)). Здесь n - максимальная длина задействованных массивов, а k – число, которые были использованы для создания массивов операндов.
==Литература==
