Изменения

def|definition=Мы называем ADT '''полностью персистентными'''(англ. fully persistent), если, помимо интерфейса, все операции сохраняют операнды неизменными, таким образом, что операнды и результаты таких операций могут быть свободно используемы повторно во время дальнейшего хода вычислений.

===Интерфейс=== * <tex> [X] </tex> статический конструктор, который принимает элемент <tex> X </tex> и возвращает массив, который содержит <tex> X </tex> в качестве его единственного элемента.* ''' <tex> LENGTH''' [A] </tex> возвращает длину массива <tex> A </tex>.* ε <tex> \varepsilon </tex> является пустым массивом, иногда также обозначается <tex> []</tex> * ''' <tex> A''' [i] </tex> принимает массив <tex> A = [''a''₀a_0, ..., ana_{n-1} ] </tex> и индекс '' <tex> i'' = 0..''n''-1</tex> , затем возвращает ''a'' <subtex>i a_i </subtex>.* ''' <tex> CONCATENATE'''(A,B) </tex> конкатентирует два массива: if '' если <tex> A'' = [''a''₀a_0,...,''a''<sub>a_{n-1} ] </subtex>] and '' и <tex> B'' = [''b''₀b_0,...,''b''_{b_{m-1}} ], ''; n'',''m'' ≥ \geq 0</tex> , результат будет [''a'' <sub>0</subtex> [a_0 ,...,''a''_{a_{n−1}},"b"₀b_0,...,''b''<sub>b_{m-1}] </subtex>]. Часто записывается как '' <tex> A'' · ''• B'' </tex> вместо ''' <tex> CONCATENATE'''(''A'',''B'')</tex> .* ''' <tex> HEAD'''(A,''i'') </tex> принимает на вход массив '' <tex> A'' = [''a''₀a_0,...,''a''a_{n−1}] </tex> и производный '' <tex> int''</tex> , возвращает массив <tex> [''a''0a_0,...,''amina_{min(i−1,n−1)'' } ]</tex> . Если '' <tex> i'' < 0 </tex> результатом будет <tex> [ ]</tex> .* ''' <tex> TAIL'''(''A'',''i'') </tex> принимает на вход массив <tex> ''A'' = ["a"₀a_0,...,an−1a_n−1] </tex> и производный <tex> int</tex> , возвращает массив <tex> [''amaxa_{max(''i'',0)'' } ,...,''a''a_{n−1}]</tex> . Если '' <tex> i'' ≥ ''\geq n''</tex> , результатом будет <tex> [ ]</tex> .* ''' Если <tex> B''' </tex> - структура, то '' <tex> seq (''B'')'' </tex> обозначает строку, которая представлена '' <tex> B''</tex> .  

 * <tex> [''x''0x0,..., ''x''x_{n−1}] </tex> является сокращением для ''' <tex> CONCATENATE'''([x0x_0],'''CONCATENATE'''([x1x_1],'''CONCATENATE'''(...,'''CONCATENATE'''([''x''x_{n−2}],[''x''x_{n−1}])))) </tex> . Обратите внимание, что в программе оценка этого выражения всегда включает '' <tex> n-2'' </tex> конкатенации.* ''' <tex> REVERSE'''[''A''] </tex> принимает на вход массив <tex> A = [''a''0a_0,...,''a''_{a_{n-1}] </subtex>] и возвращает [''a'' <subtex> [a_{n-1}},...,a0a_0]</tex> . * ''' <tex> REPLACE'''[A,i, x] </tex> принимает на вход массив <tex> A = [''a''0a_0,...,''a''<sub>a_{n-1}]</subtex>] , индекс '' <tex> i'' = 0..''n'' − - 1</tex> , и новый элемент '' <tex> x''</tex> , выводит [''a'' <sub>0</subtex>[a_0,...,''a''_{a_{i-1}}, ''x'',''a''_{a_{i+1}},...,''a''<sub>a_{n-1}]</subtex>]. * ''' <tex> A'''[i] ← ''\leftarrow x ''</tex> является сокращенным обозначением <tex> A ← \leftarrow REPLACE(A,''i'', ''x'')</tex> . * ''' <tex> INSERT'''[A,i, x] </tex> получает массив <tex> A = [''a''0a_0,...,''a''<sub>a_{n-1}]</subtex>] , индекс '' <tex> i'' = 0..n−1n - 1 </tex> , и новый элемент <tex> x </tex> и возвращает массив <tex> [''a''0a_0,...,''a''_{a_{i-1}}, x,''a''i a_i ,...,''a''a_{n−1}] = '''HEAD'''(A,''i'') · [''x''] · '''• TAIL'''(A,''i)''</tex> , длина которого '' <tex> n''-1</tex> .* ''' <tex> LEFTPART'''(A): </tex> возвращает (non-deterministically) массив, представляющий последовательность префикса <tex> A</tex> .* ''' <tex> RIGHTPART'''(A): </tex> возвращает (non-deterministically) массив, представляющий последовательность суффикса <tex> A</tex> . ===Реализация персистентных массивом массивов в виде сбалансированных деревьев===

Def {{Определение|definition= Пусть <tex> X </tex> - некоторое множество. Бинарное дерево с несколькими ссылками по на <tex> X </tex> является кортежем <tex> B = (N, L, R) с L∩R L \cap R = 0 /, L, R ⊆ \subseteq N × N</tex> , такойтаким, что * <tex> (N, L∪RL \cup R) </tex> является корневым ациклическим ориентированным графом с узлами <tex> N и ребра L∪R и в </tex> , ребрами <tex> L \cup R</tex> . * В каждом из двух подграфов <tex> (N, L) и (N, R) </tex> каждый узел имеет не более одного прямого преемника. Кроме того, узлы *Узлы без каких-либо преемников (листья B) должны быть все элементами <tex> X</tex> .}}Дано двоичное дерево с несколькими ссылками <tex> B = (N,L,R) </tex> и узел '' <tex> p'' ∈ \in N</tex> . Пишут <tex> LEFT(''p'') = ''q''</tex> , если '' <tex> q'' </tex> является единственным приемником <tex> ''p'' в(N,L) </tex> и, если такого '' <tex> q'' </tex> не существует, пишем <tex> LEFT(''p'')= ⊥\perp</tex> , предполагая, что ⊥ <tex> \perp </tex> не содержит <tex> N</tex> . Аналогично, пишут <tex> RIGHT(p) = ''q''</tex> , если <tex> q </tex> является единственным приемником <tex> p в(N,R) </tex> и, если такого <tex> q </tex> не существует, пишем <tex> RIGHT(''p'')= ⊥\perp</tex> . Мы будем называть <tex> LEFT (''p'') </tex> левым дочерним элементом <tex> p </tex> и <tex> RIGHT (''p'') </tex> правым дочерним элементом.В <tex> B = (N, L∪RL \cup R) </tex> узел '' <tex> p'' ∈ \in N </tex> может иметь много прямых предшественников '' <tex> q''</tex> . Тогда ребра <tex> (''q'', ''p'') ∈ \in E </tex> называют ссылками от <tex> q </tex> до <tex> p</tex> .

С каждым узлом '' <tex> p'' ∈ \in N </tex> мы можем идентифицировать строку <tex> seq (''p'') ∈ \in X *</tex> : Если ''p'' - лист, то согласно определению выше, ''<tex> p'' ∈ \in X</tex> . Мы можем установить <tex> seq (p) = x </tex> (строка, содержащая только'' x''). Поскольку <tex> (N, L∪R L \cup R ) </tex> ациклично, для всех внутренних узлов мы можем рекурсивно определить <tex> p ∈ \in N seq (''p'') = seq (LEFT (''p'')) seq (RIGHT (''p''))</tex> , задав <tex> seq (⊥\perp) = ε<tex> . Наконец, пусть r - корень B. Тогда определим''seq ''определимseq (B): = ''seq ''(''r''). В качестве примера, см. рисунок 1.2.В нашей реализации мы поддерживаем с каждым узлом <tex> p ∈ \in N </tex> длину <tex> seq (LEFT (''p''))</tex> . Это позволяет получить '' <tex> i''-й </tex> символ строки <tex> seq (B)</tex> , пройдя путь от корня до соответствующего листа. Мы также поддерживаем значение HEIGHT (''p'') для каждого <tex> p ∈ \in N</tex> , которое определяется как максимальнаядлина пути от p до листа в '' <tex> q'' ∈ \in N</tex> . Согласно этому определению все листья имеют высоту <tex> 0 </tex> и если мы устанавливаем <tex> HEIGHT (⊥\perp) = -1</tex> , то <tex> HEIGHT(''p'') = max(HEIGHT(LEFT(''p'')), HEIGHT(RIGHT(''p'')))+1 </tex> . для всех '' <tex> .p'' ∈ \in N</tex> ..

Def3 Бинарное дерево <tex> B = (N, L, R) </tex> является AVL-деревом, если оно удовлетворяет условию AVL, то есть для каждого <tex> p ∈ \in N |HEIGHT(LEFT(''p''))− HEIGHT(RIGHT(''p''))| ≤ \le 1</tex> .

Для полноты мы покажем операции для конкатенации · • и расщепления <tex> (HEAD и TAIL)</tex> , которые особенно просты в реализации, запускаются во времени <tex> O (HEIGHT (''r'')) </tex> и позволяют нам реализовать полный интерфейс персистентного массива ADT. Для конкатенации см. Алгоритм 1.2. <tex> NODE (''l'', ''r'') </tex> является конструктором, который выдает созданный узел '' <tex> p'' с LEFT (''p'') = l и RIGHT (''p'') = ''r''</tex> . Конструктор также определяет правильные значения <tex> p </tex> для <tex> HEIGHT (''p'') и LENGTH (''p'')</tex> .Обратите внимание, что время его работы равно <tex> O (| HEIGHT (''r'') -HEIGHT (''l'') |)</tex> . Далее мы покажем алгоритм <tex> HEAD</tex> , алгоритм для <tex> TAIL </tex> является симметричным.

Учитывая корневой узел r высоты ''h'' и целое число ''i'', алгоритм 1.3 свяжет не более чем '' <tex> h + 1'' </tex> двоичных дерева. Стоимость одной конкатенации пропорциональна разнице высот.