Войти
В информатике, a finger tree - это чисто функциональная структура данных, которая может использоваться для эффективной реализации других функциональных структур данных. Дерево пальцев дает амортизированное постоянное время доступ к «пальцам» (листьям) дерева, в котором хранятся данные, а также объединение и разделение логарифмического времени в размере меньшего фрагмента. Он также сохраняет в каждом внутреннем узле результат применения некоторой ассоциативной операции к его потомкам. Эти «сводные» данные, хранящиеся во внутренних узлах, могут использоваться для обеспечения функциональности структур данных, отличных от деревьев.
Дерево пальцев, используемое как простая очередь с амортизированными операциями O (1) put get. Целые числа от 1 до 21 вставляются справа и извлекаются слева. Квадратные блоки представляют значения, «Цифра» (небесно-голубой) может иметь 1-4 дочерних элемента, «Узел» (темно-синий) может иметь 2-3 дочерних элемента, белый кружок означает «Пустой», красный узел представляет «Единственное» значение и зеленый узлы представляют «глубокие» значения. Обратите внимание, что на каждом шаге мы удаляем корешок, отдельные значения и дочерние числа цифр вставляются с новым уровнем узлов. Ральф Хинце и Росс Патерсон заявляют, что дерево пальцев - это функциональное представление постоянных последовательностей, которые могут получить доступ к концам в амортизированное постоянное время. Объединение и разделение может быть выполнено за логарифмическое время по размеру меньшего фрагмента. Структуру также можно превратить в структуру данных общего назначения, определив операцию разделения в общей форме, позволяя ей действовать как последовательность, приоритетная очередь, дерево поиска или очередь приоритетного поиска, среди других разновидностей абстрактных типов данных.
Палец - это точка, где можно получить доступ к части структуры данных; в императивных языках это называется указателем. В дереве пальцев пальцы - это структуры, которые указывают на концы последовательности или листовые узлы. Пальцы добавляются к исходному дереву, чтобы обеспечить постоянный доступ к пальцам во времени. На изображениях, показанных ниже, пальцы - это линии, идущие от позвоночника к узлам.
Дерево пальцев состоит из разных слоев, которые можно идентифицировать по узлам вдоль его позвоночника. Хребет дерева можно представить себе как ствол, точно так же, как у деревьев есть листья и корень. Хотя пальчиковые деревья часто показаны с позвоночником и ветвями, отходящими от боковых сторон, на самом деле на каждом уровне позвоночника есть два узла, которые были спарены, чтобы образовать центральный стержень. Префикс находится слева от корешка, а суффикс - справа. Каждый из этих узлов связан со следующим уровнем позвоночника, пока не достигнет корня.
Показывает, что 2-3 дерева (вверху) можно вытянуть в дерево пальцев (внизу) Первый уровень дерево содержит только значения, листовые узлы дерева, и имеет глубину 0. Второй уровень - глубину 1. Третий - глубину 2 и так далее. Чем ближе к корню, тем глубже поддеревья исходного дерева (до того, как оно было деревом пальцев), на которые указывают узлы. Таким образом, движение вниз по дереву идет от листьев к корню дерева, что является противоположностью типичной древовидной структуры данных. Чтобы получить эту красивую и необычную структуру, мы должны убедиться, что исходное дерево имеет одинаковую глубину. Чтобы обеспечить равномерность глубины, при объявлении объекта узла он должен быть параметризован типом дочернего элемента. Узлы на корешке глубины 1 и выше указывают на деревья, и с этой параметризацией они могут быть представлены вложенными узлами.
Мы начнем с этого процесс со сбалансированным 2-3 деревом. Чтобы дерево пальцев работало, все листовые узлы также должны быть выровнены.
Палец - это «структура, обеспечивающая эффективный доступ к узлам дерева рядом с выделенным местом». Чтобы сделать дерево из пальцев, нам нужно приложить пальцы к правому и левому концам дерева и преобразовать его как молнию. Это дает нам постоянный доступ по амортизированному времени к концам последовательности.
Чтобы трансформировать, начните со сбалансированного дерева 2-3.
Возьмите крайний левый и крайний правый внутренние узлы дерева и потяните их вверх, чтобы остальная часть дерева болталась между ними, как показано на изображении справа.
Соединяет шипы, чтобы получилось стандартное дерево на 2-3 пальца.
Это можно описать как:
data FingerTree a = Empty | Одиночный | Глубокий (Цифра a) (FingerTree (Узел a)) (Цифра a) узел данных a = Node2 a a | Node3 a a a
Цифры в показанных примерах - это узлы с буквами. Каждый список разделен префиксом или суффиксом каждого узла на корешке. В преобразованном дереве 2-3 кажется, что списки цифр на верхнем уровне могут иметь длину два или три, а нижние уровни имеют длину только один или два. Чтобы некоторые приложения деревьев пальцев работали так эффективно, деревья пальцев допускают от одного до четырех поддеревьев на каждом уровне. Цифры дерева пальцев можно преобразовать в список следующим образом:
type Digit a = One a | Два а | Три а а а | Четыре aaaa
И так на изображении, верхний уровень имеет элементы типа a, следующий имеет элементы типа Node a, потому что узел между позвоночником и листьями, и это будет в целом означать, что n-й уровень дерева имеет элементы типа 
Деревья пальцев также делают эффективными вопросы. Независимо от того, является ли структура постоянной или нет, все операции занимают Θ (1) амортизированного времени. Анализ можно сравнить с неявными deques Окасаки, с той лишь разницей, что тип FingerTree хранит узлы вместо пар.
Деревья пальцев могут использоваться для построения других деревьев. Например, приоритетная очередь может быть реализована путем маркировки внутренних узлов по минимальному приоритету их дочерних элементов в дереве, или индексированный список / массив может быть реализован с маркировкой узлов по количеству уходит в их детей. Другие приложения - это последовательности с произвольным доступом, описанные ниже, упорядоченные последовательности и деревья интервалов.
Деревья пальцев могут обеспечивать амортизированное O (1) нажатие, реверсирование, выталкивание, добавление O (log n) и раскол; и может быть адаптирован для индексирования или упорядочивания последовательностей. И, как и все функциональные структуры данных, он по своей сути постоянный ; то есть всегда сохраняются более старые версии дерева.
Деревья пальцев могут эффективно реализовывать последовательности произвольного доступа. Это должно поддерживать быстрые позиционные операции, включая доступ к n-му элементу и разделение последовательности в определенной позиции. Для этого мы аннотируем дерево пальцев с помощью размеров.
newtype Size = Size {getSize :: N} вывод (Eq, Ord) instance Monoid Size, где ∅ = Size 0 Size m ⊕ Size n = Size (m + n)N - натуральные числа. Новый тип необходим, потому что тип является носителем различных моноидов. Еще один новый тип по-прежнему необходим для элементов в последовательности, показанной ниже.
newtype Elem a = Elem {getElem :: a} newtype Seq a = Seq (FingerTree Size (Elem a)) instance Measured (Elem a) Size где || Elem || = Размер 1Эти строки кода показывают, что экземпляр работает как базовый вариант для измерения размеров, а элементы имеют размер один. Использование newtype s не вызывает штрафов во время выполнения в Haskell, потому что в библиотеке типы Size и Elem будут скрыты от пользователя с помощью функций-оберток.
С этими изменениями теперь можно вычислить длину последовательности за постоянное время.
Деревья пальцев были впервые опубликованы в 1977 году Леонидасом Дж. Гибасом и с тех пор периодически уточнялись (например, версия, использующая деревья AVL, неленивые деревья пальцев, простые деревья на 2-3 пальца, показанные здесь, B-деревья и т. д.)
Деревья пальцев с тех пор используются в Haskell существуют базовые библиотеки (в реализации Data.Sequence) и реализация в OCaml, которая была получена из проверенной правильной реализации Coq. Деревья пальцев могут быть реализованы с ленивым вычислением или без него, но ленивость допускает более простые реализации.
