Пальчиковые деревья (Часть 1. Представление)

[gasya]

жоский перевод

[Vitter]

Жду пожелания в личку, улучшу как смогу. Спасибо

[lemelisk]

Прорекламирую свою статью про персистентную очередь, выполняющую каждую операцию за фактическое (не амортизационное) O(1), может кому-то будет интересно. Есть ещё альтернативная реализация, использующая 5 или 6 персистентных стеков. Обе реализации обладают свойством иммутабельности, значит могут быть реализованы на функциональном языке программирования (хотя я, конечно, не знаток).

Последовательность (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов)

Это называется дек (deque).

[lemelisk]

К слову, если персистентность не нужна (вы всегда работаете только с последней версией структуры), то можно просто эмулировать очередь двумя стеками, это будет работать за амортизированное O(1).

[Vitter]

можно поподробней как добраться до конца очереди (или эмулировать это) за О(1). Можно в пальчиковых деревьях использовать не 2-3 деревья, а бинарные деревья, но как 2мя стеками сэмулировать — не знаю. Хочу заметить в иммутабельных переменных указателей как таковых нет.

[ilammy]

можно поподробней как добраться до конца очереди (или эмулировать это) за О(1)

Никак. У очереди нет операции «обойти все элементы», есть только «положить в начало» и «забрать из конца».

Очередь на двух стеках А и Б делается по следующим правилам:
1. Элементы кладутся в стек А.
2. Элементы забираются из стека Б.
3. Стек Б пустой тогда и только тогда, когда очередь пуста.
Из третьего правила легко догадаться, почему реализация за амортизированное O(1).

[Vitter]

Сори, а как положить что-то в конец за О(1)? Ведь всё равно надо дойти до конца.

[ilammy]

Я вот не хочу прямо спойлерить. Вместо этого я ещё раз поставлю ударение на словах амортизированная сложность и два стека. Думайте, как два стека могут делать вид, что они очередь, в большинстве случаев извлекая элементы за постоянное время, но иногда тратя больше времени на некоторое действие.

[Vitter]

Смотрите, есть списки:

data List a = Nil | Cons a (List a)

ну, или используя встроенный синтаксис:

data [a] = [] | a : [a]

Пусть у нас есть список:

stack  = 5 : 4 :3 : 2 : 1 : []
stack_ = Cons 5 (Cons 4 (Cons 3 (Cons 2 (Cons 1 Nil))))

Как мне за О(1) добраться до конца? напоминаю, у нас нет указателей.
Для того, чтобы добавить в начало, это О(1):

stack1  = 6 : stack
stack1_ = Cons 6 : stack_

А для того, чтобы получить всё, кроме последнего элемента, или просто получить последний элемент — О(н):

last []     = error "last"
last [x]    = x
last (x:xs) = last xs

init []      = error "inits"
init [x]     = []
init (x:xs) = x : inits xs

[ilammy]

Ок, сдаюсь

empty_queue = ([], [])

enqueue :: a -> ([a], [a]) -> ([a], [a])
dequeue :: ([a], [a]) -> (a, ([a], [a]))

-- O(1)
enqueue x (a, b) = (x:a, b)

-- O(n)
reversed list = reversed' list []
  where
    reversed' []     reversed = reversed
    reversed' (x:xs) reversed = reversed' xs (x:reversed)

dequeue ([], []) = error "Dequeuing an empty queue"

-- O(1)
dequeue (a, x:b) = (x, (a, b))

-- O(n)
dequeue (a, []) = dequeue ([], reversed a)

[Vitter]

Пиковое вытаскивание так и остаётся О(n). Хотя средняя сложность, конечно, падает, согласен.

Я бы добавил тип сюда:

type Queue a = ([a], [a])

enqueue :: a -> Queue a -> Queue a
dequeue :: Queue a -> (a, Queue a)

Кстати, в следующей части статьи я опишу как добавлять к пальчиковому дереву. Пиковая сложность там будет O(lg n). Соединение 2х очередей — O(lg(min(m,n)))

[lemelisk]

Кстати, возможно не так очевидно, как для очереди, но дек также можно эмулировать двумя стеками, имея при этом амортизированное O(1) на каждую операцию. Основная идея, собственно, точно такая же: заводим два стека, один символизирует голову, второй — хвост, соответственно при вставке/удалении из головы/хвоста, добавляем или удаляем из нужного стека. Единственная разница, когда стек, из которого нам нужно удалить, оказывается пустым, то мы перемещаем в него из другого стека не все элементы сразу, а только нижнюю половину (можно взять и другую пропорцию).

[Vitter]

дубль

[utyv]

Однако, для уменьшения информативности, требование ослаблено для пальчиковых деревьев, и, вместо этого, каждый префикс и суффикс содержат от 1 до 4 элементов.

Кто-нибудь понял, что это значит? Почему не до 3-х элементов?

[Vitter]

Я так понял, что это означает, что каждое 2-3 дерево является пальчиковым, но не каждое пальчиковое является 2-3 деревом (если существуют аффиксы размера 4).
При этом, каждое пальчиковое дерево является 2-3-4 деревом, но не каждое 2-3-4 дерево является пальчиковым (если существуют ветки размера 4).