Изменения

* <tex>[ X ]</tex> статический конструктор, который принимает элемент X и возвращает массив, который содержит X в качестве его единственного элемента.* <tex>LENGTH [A] </tex> возвращает длину массива A.* ε является пустым массивом, иногда также обозначается <tex> []</tex> * <tex>A [i] </tex> принимает массив </tex> A = [a_0, ..., a_na_{n-1 } ] </tex> и индекс <tex> i = 0..n - 1 </tex>, затем возвращает <tex> a_i </tex> a_i.* <tex>CONCATENATE(A,B) </tex> конкатентирует два массива: <tex> if A = [a_0,..., a_{n-1} ] </tex> and <tex> B = [b_0,..., b_{m-1} ], n, m \geq 0</tex>, результат будет <tex> [a_0 ,..., a_{n−1}, b_0,..., b_{m-1}] </tex>. Часто записывается как <tex> A • B</tex> вместо вместо <tex>CONCATENATE</tex>(A,B).* <tex>HEAD</tex>(A, i) принимает на вход массив <tex> A = [a_0,...,a_{n−1}] </tex> и производный <tex> int</tex>, возвращает массив <tex> [a_0,...,a_{min(i−1,n−1)} ] </tex>. Если <tex> i < 0</tex> результатом будет <tex> [ ]</tex>.* <tex>TAIL (A,i) </tex> принимает на вход массив <tex> A = [a_0,...,a_n−1] </tex> и производный <tex> int</tex>, возвращает массив <tex> [a_{max(i,0)} ,...,a_{n−1}]</tex>. Если <tex> i \geq n</tex>, результатом будет <tex> [ ]</tex>.* <tex>B</tex> - структура, то <tex> seq (B) </tex> обозначает строку, которая представлена <tex> B</tex>.

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

|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</tex> , ребрами L∪R <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> двоичных дерева. Стоимость одной конкатенации пропорциональна разнице высот.