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

Original author: Andrew Gibiansky
  • Translation
  • Tutorial
Вышла недавно статья на Хабре о том, как можно самому создать на функциональном языке такие структуры как Очередь (первый зашёл, первый вышел) и Дек (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов). Посмотрел я на этот код и понял, что он жутко неэффективен — сложность порядка O(n). Быстро сообразить, как создать структуры с O(1) у меня не вышло, поэтому я открыл код библиотечной реализации. Но там была не лёгкая и понятная реализация, а <много кода>. Это было описание пальчиковых деревьев, необходимость и элегантность которых для этой структуры данных хорошо раскрывается текущей статьёй.

Пальчиковые деревья


В этой статье мы рассмотрим пальчиковые деревья. Это функциональные неизменяемые структуры данных общего назначения, разработанные в работе Гинце и Паттерсона. Пальчиковые деревья обеспечивают функциональную структуру данных Последовательность (sequence), которая обеспечивает амортизированной доступ постоянный во времени для добавления как в начало, так и в конец последовательности, а также логарифмическое время для конкатенации и для произвольного доступа. В дополнение к хорошему времени асимптотических исполнения, структура данных оказывается невероятно гибкой: в сочетании с моноидальными тегами на элементах, пальчиковые деревья могут быть использованы для реализации эффективных последовательностей с произвольным доступом, упорядоченных последовательностей, интервальных деревьев и очередей приоритетов.

Статья будет состоять из 3-х частей:

Пальчиковые деревья (Часть 1. Представление)
Пальчиковые деревья (часть 2. Операции)
Пальчиковые деревья (Часть 3. Применение)

Разрабатывая структуру данных


Основа и мотивация пальчиковых деревьев пришла от 2-3 деревьев. 2-3 деревья — это деревья, которые могут иметь две или три ветви в каждой внутренней вершине и которые имеют все свои листья на одном и том же уровне. В то время, как бинарное дерево одинаковой глубины d должны быть 2d листьев, 2-3 деревья гораздо более гибкие, и могут быть использованы для хранения любого числа элементов (количество не должно быть степенью двойки).
Рассмотрим следующее 2-3 дерево:



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

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



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



Каждый слой пальчикового дерева имеет префикс (слева) и суффикс (справа), а также и ссылку на дальнейший поход вглубь. Префикс и суффикс содержат значения пальчикового дерева: на первом слое содержат значения 2-3 деревьев глубины 0, на втором слое — 2-3 деревья глубины 1, на третьем слое они содержат 2-3 деревья глубины 2 и так далее. Главным элементом этого 2-3 дерева сейчас является элемент в самом низу.

Что ж, имея описание, давайте опишем структуру данных. Для начала мы должны определить структуру 2-3 дерева, которую необходимо будет использовать для сохранения вещей, нанизанных на ось.

data Node a = Branch3 a a a    -- Ветка (node) может содержать 3х детей.
            | Branch2 a a      -- ... или только 2х детей.
            deriving Show

Заметим, что ветка параметризована по своим детям. Это позволяет иметь вложенные ветки для репрезентации 2-3 деревьев и гарантировать одинаковость глубины. Например, 2-3 дерево глубиной 1 может быть Node Char:
> -- 2-3 деревья со 2го суффиксного слоя экземпляра пальчикового дерева.
> Branch3 'n' 'o' 't'
Branch3 'n' 'o' 't'
> Branch2 'a' 't'
Branch2 'a' 't'

Однако, мы можем также создать более глубокие 2-3 деревья. Например, 2-3 дерево, глубиной 2 может быть Node (Node Char):

> Branch2 (Branch3 'n' 'o' 't') (Branch2 'a' 't')
Branch2 (Branch3 'n' 'o' 't') (Branch2 'a' 't')

Замечаем, что отображение гарантирует, что 2-3 дерево будет одинаковой глубины, потому что глубина присутствует в типе дерева. Это так же имеет свои недостатки, так как сложнее писать функции, которые параметрические по параметру глубины дерева. Но это не так плохо для нашего случая.
Для дальнейшего нашего удобства, добавим немного методов, которые позволят нам преобразовывать значения веток из списков длиной 2 или 3. Для этого будем использовать расширение OverloadedLists для GHC, которое позволит нам написать функции fromList и toList для различных типов данных, и далее использовать их для сравнений с образцом, если мы используем списки:

{- LANGUAGE OverloadedLists, TypeFamilies -}
import GHC.Exts (IsList(..))

instance IsList (Node a) where
  type Item (Node a) = a
  
  toList (Branch2 x y)   = [x, y]
  toList (Branch3 x y z) = [x, y, z]
  
  fromList [x, y]    = Branch2 x y
  fromList [x, y, z] = Branch3 x y z
  fromList _ = error "Node must contain two or three elements"

Теперь, когда мы имеем наш тип 2-3 дерева, необходим также тип для сохранения префикса и суффиксов, которые нанизаны на ось пальчикового дерева. Если наше пальчиковое дерева является полной аналогией 2-3 дерева, тогда каждые самые первые префиксы и суффиксы могут иметь 2 или 3 элемента, а средние могут иметь только 1 или 2 (потому что одна из ссылок идёт вверх на один уровень по оси). Однако, для уменьшения информативности, требование ослаблено для пальчиковых деревьев, и, вместо этого, каждый префикс и суффикс содержат от 1 до 4 элементов. Больше значений быть не может. Мы могли бы позволить сохранять префикс и суффикс в виде списков, но мы вместо этого будем использовать более селективные конструкторы, каждый из которых отвечает за своё правильное количество элементов:

-- Параметризуем аффикс типом данных, который он сохраняет
-- Тип эквивалентен спискам длиной от 1 до 4
data Affix a = One a
             | Two a a
             | Three a a a
             | Four a a a a
             deriving Show

Работать с таким типом данных не так уж и удобно, поэтому мы быстро допишем функции-помощники, которые позволяют работать с аффиксами как со списками.

-- Работам с аффиксами как со списками
instance IsList (Affix a) where
  type Item (Affix a) = a
  
  toList (One x)        = [x]
  toList (Two x y)      = [x, y]
  toList (Three x y z)  = [x, y, z]
  toList (Four x y z w) = [x, y, z, w]
  
  fromList [x]          = One x
  fromList [x, y]       = Two x y
  fromList [x, y, z]    = Three x y z
  fromList [x, y, z, w] = Four x y z w
  fromList _ = error "Affix must have one to four elements"
  
-- Следующая функция может быть куда более эффективной
-- Мы же будем использовать самую простую реализацию на сколько возможно
affixPrepend :: a -> Affix a -> Affix a
affixPrepend x = fromList . (x :) . toList

affixAppend :: a -> Affix a -> Affix a
affixAppend x = fromList . (++ [x]) . toList

Теперь, когда мы определили тип данных, необходимых для хранения значений (2-3 деревья, сохраняющие значения и аффиксы, прикрепленные к оси), мы можем создать осевую структуру данных. Эта осевая структура и есть то, что мы называем пальчиковым деревом, и определяется она так:

-- Как обычно, параметрезируется тип тем типом, который он сохраняет в пальчиковом дереве
data FingerTree a 
  = Empty      -- Дерево может быть пустым
  | Single a   -- Дерево может содержать единственное значение, удобно это записать в отдельный случай
  
  -- Общий случай с префиксом, суффиксом и ссылкой на вглубь дерева
  | Deep {
    prefix :: Affix a,             -- Значения слева
    deeper :: FingerTree (Node a), -- Более глубокая часть пальчикового дерева, хранящая 2-3 деревья
    suffix :: Affix a              -- Значения справа
  }
  deriving Show

В определении выше, глубокое поле FingerTree a имеет тип FingerTree (Node a). Это означает, что значения, хранимые на следующем слое являются 2-3 деревьями, которые находятся на уровень глубже. Так, аффиксы первого слоя FingerTree Char хранят всего лишь Char, второй слой хранит FingerTree (Node Char) и имеет аффиксы, которые хранят 2-3 деревья глубиной 1 (Node Char). Третий слой будет уже FingerTree (Node (Node Char)) и имеет аффиксы, которые хранят 2-3 деревья глубиной 2 (Node (Node Char)).

Сейчас, когда мы определили наш тип пальчикового дерева, проведём немного больше времени и рассмотрим пример, который был показан выше, для того, чтобы понять как мы переводим его в структуру FingerTree Char:



Переведя это в дерево, получим:

layer3 :: FingerTree a
layer3 = Empty

layer2 :: FingerTree (Node Char)
layer2 = Deep prefix layer3 suffix
  where
    prefix = [Branch2 'i' 's', Branch2 'i' 's']
    suffix = [Branch3 'n' 'o' 't', Branch2 'a' 't']

layer1 :: FingerTree Char
layer1 = Deep prefix layer2 suffix
  where
    prefix = ['t', 'h']
    suffix = ['r', 'e', 'e']

exampleTree :: FingerTree Char
exampleTree = layer1

> exampleTree
Deep {prefix = Two 't' 'h', deeper = Deep {prefix = Two (Branch2 'i' 's') (Branch2 'i' 's'), deeper = Empty, 
suffix = Two (Branch3 'n' 'o' 't') (Branch2 'a' 't')}, suffix = Three 'r' 'e' 'e'}

В следующей части статьи мы научимся легко работать с пальчиковыми деревьями как с последовательностями.

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 15

    –5
    жоский перевод
      +1
      Жду пожелания в личку, улучшу как смогу. Спасибо
      +2
      Прорекламирую свою статью про персистентную очередь, выполняющую каждую операцию за фактическое (не амортизационное) O(1), может кому-то будет интересно. Есть ещё альтернативная реализация, использующая 5 или 6 персистентных стеков. Обе реализации обладают свойством иммутабельности, значит могут быть реализованы на функциональном языке программирования (хотя я, конечно, не знаток).
      Последовательность (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов)
      Это называется дек (deque).
        0
        К слову, если персистентность не нужна (вы всегда работаете только с последней версией структуры), то можно просто эмулировать очередь двумя стеками, это будет работать за амортизированное O(1).
          0
          можно поподробней как добраться до конца очереди (или эмулировать это) за О(1). Можно в пальчиковых деревьях использовать не 2-3 деревья, а бинарные деревья, но как 2мя стеками сэмулировать — не знаю. Хочу заметить в иммутабельных переменных указателей как таковых нет.
            +1
            можно поподробней как добраться до конца очереди (или эмулировать это) за О(1)
            Никак. У очереди нет операции «обойти все элементы», есть только «положить в начало» и «забрать из конца».

            Очередь на двух стеках А и Б делается по следующим правилам:
            1. Элементы кладутся в стек А.
            2. Элементы забираются из стека Б.
            3. Стек Б пустой тогда и только тогда, когда очередь пуста.
            Из третьего правила легко догадаться, почему реализация за амортизированное O(1).
              0
              Сори, а как положить что-то в конец за О(1)? Ведь всё равно надо дойти до конца.
                0
                Я вот не хочу прямо спойлерить. Вместо этого я ещё раз поставлю ударение на словах амортизированная сложность и два стека. Думайте, как два стека могут делать вид, что они очередь, в большинстве случаев извлекая элементы за постоянное время, но иногда тратя больше времени на некоторое действие.
                  0
                  Смотрите, есть списки:
                  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
                  
                    +1
                    Ок, сдаюсь
                    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)
                      +1
                      Пиковое вытаскивание так и остаётся О(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)))
            0
            Кстати, возможно не так очевидно, как для очереди, но дек также можно эмулировать двумя стеками, имея при этом амортизированное O(1) на каждую операцию. Основная идея, собственно, точно такая же: заводим два стека, один символизирует голову, второй — хвост, соответственно при вставке/удалении из головы/хвоста, добавляем или удаляем из нужного стека. Единственная разница, когда стек, из которого нам нужно удалить, оказывается пустым, то мы перемещаем в него из другого стека не все элементы сразу, а только нижнюю половину (можно взять и другую пропорцию).
            0
            дубль
              +1
              Однако, для уменьшения информативности, требование ослаблено для пальчиковых деревьев, и, вместо этого, каждый префикс и суффикс содержат от 1 до 4 элементов.

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

              Only users with full accounts can post comments. Log in, please.