1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Интерфейс==
* <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_0, ..., a_{n-1} ] </tex> и индекс <tex> i = 0..n - 1 </tex> , затем возвращает <tex> a_i </tex>.
* <tex> CONCATENATE(A,B) </tex> конкатентирует два массива: если <tex> 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 (A,B) </tex> .
* <tex> HEAD (A,i) </tex> принимает на вход массив <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> RIGHTPART(A) </tex> возвращает массив, представляющий последовательность суффикса <tex> A</tex> .
==Реализация персистентных массивом массивов в виде сбалансированных деревьев==
Будем использовать сбалансированные деревья в качестве нашей стандартной реализации постоянных массивов. (Реализации сбалансированных деревьев, таких как AVL-деревья и B-деревья, можно найти в соответствующих разделах сайта)
Решающим моментом является то, что мы допускаем множественные ссылки на одно и то же поддерево: хотя концептуальное представление постоянных массивов - ориентированные деревья, их представление в памяти различно. Мы допускаем, что узел может быть преемником многих разных узлов.
