В компьютерной науке , палец дерево является чисто функциональной структурой данных , которые могут быть использованы для эффективной реализации других функциональных структур данных. Дерево пальцев дает амортизированный доступ с постоянным временем к «пальцам» (листьям) дерева, в котором хранятся данные, а также объединение и разделение логарифмического времени в размере меньшего фрагмента. Он также хранит в каждом внутреннем узле результат применения некоторой ассоциативной операции к его потомкам. Эти «сводные» данные, хранящиеся во внутренних узлах, могут использоваться для обеспечения функциональности структур данных, отличных от деревьев.
Обзор
Ральф Хинце и Росс Патерсон утверждают, что дерево пальцев - это функциональное представление постоянных последовательностей, которые могут обращаться к концам за амортизированное постоянное время. Объединение и разделение можно выполнить за логарифмическое время по размеру меньшего фрагмента. Структура также может быть преобразована в структуру данных общего назначения путем определения операции разделения в общей форме, позволяя ей действовать как последовательность, очередь приоритета, дерево поиска или очередь поиска приоритета, среди других разновидностей абстрактных типов данных. [1]
Палец является точкой , в которой можно получить доступ к части структуры данных; в императивных языках это называется указателем. [2] В дереве пальцев пальцы - это структуры, указывающие на концы последовательности или листовые узлы. Пальцы добавляются к исходному дереву, чтобы обеспечить постоянный доступ к пальцам во времени. На изображениях, показанных ниже, пальцы - это линии, идущие от позвоночника к узлам.
Дерево пальцев состоит из разных слоев, которые можно определить по узлам вдоль его позвоночника . Хребет дерева можно рассматривать как ствол точно так же, как у деревьев есть листья и корень. Хотя пальчиковые деревья часто показаны с позвоночником и ветвями, отходящими от боковых сторон, на самом деле на каждом уровне есть два узла, которые были спарены, чтобы образовать центральный позвоночник. Приставка находится на левой стороне позвоночника, в то время как суффикс находится справа. Каждый из этих узлов связан со следующим уровнем позвоночника, пока не достигнет корня. [2]
Первый уровень дерева содержит только значения, листовые узлы дерева, и имеет глубину 0. Второй уровень - глубину 1. Третий - глубину 2 и так далее. Чем ближе к корню, тем глубже поддеревья исходного дерева (до того, как оно было деревом пальцев), на которые указывают узлы. Таким образом, работа по дереву идет от листьев к корню дерева, что является противоположностью типичной древовидной структуры данных. Чтобы получить эту красивую и необычную структуру, мы должны убедиться, что исходное дерево имеет одинаковую глубину. Чтобы обеспечить равномерность глубины, при объявлении объекта узла он должен быть параметризован типом дочернего элемента. Узлы на корешке глубины 1 и выше указывают на деревья, и с этой параметризацией они могут быть представлены вложенными узлами. [3]
Превращение дерева в пальчиковое дерево
Мы начнем этот процесс со сбалансированного 2-3 дерева . Чтобы дерево пальцев работало, все листовые узлы также должны быть выровнены.
Палец - это «структура, обеспечивающая эффективный доступ к узлам дерева рядом с выделенным местом». [1] Чтобы сделать пальчиковое дерево, нам нужно приложить пальцы к правому и левому концам дерева и трансформировать его как молнию . Это дает нам постоянный доступ по амортизированному времени к концам последовательности.
Чтобы трансформировать, начните со сбалансированного 2-3 дерева.
Возьмите крайний левый и крайний правый внутренние узлы дерева и потяните их вверх, чтобы остальная часть дерева болталась между ними, как показано на изображении справа.
Соединяет колючки, чтобы получилось стандартное дерево на 2-3 пальца.
Это можно описать так: [1]
data FingerTree a = Empty | Одноместный | Deep ( Digit а ) ( FingerTree ( Node а )) ( Digit ) данных узла в = Node2 в | Узел 3 а а а
Цифры в показанных примерах - это узлы с буквами. Каждый список разделен префиксом или суффиксом каждого узла на корешке. В преобразованном дереве 2-3 кажется, что списки цифр на верхнем уровне могут иметь длину два или три, а нижние уровни имеют длину только один или два. Чтобы некоторые приложения деревьев пальцев работали так эффективно, деревья пальцев допускают от одного до четырех поддеревьев на каждом уровне. Цифры дерева пальцев можно преобразовать в список следующим образом: [1]
введите цифру a = один a | Два а а | Три а а а | Четыре а а а а
Итак, на изображении верхний уровень имеет элементы типа a , следующий имеет элементы типа Node a, потому что узел между позвоночником и листьями, и это будет означать, в общем, что n- й уровень дерева имеет элементы типа a , или 2-3 дерева глубиной n. Это означает, что последовательность из n элементов представлена деревом глубины Θ (log n ). Более того, элемент, расположенный на d от ближайшего конца, хранится в дереве на глубине Θ (log d). [1]
Скидки
Deque операции
Пальцевые деревья также образуют эффективные декы . Независимо от того, является ли структура постоянной или нет, все операции занимают Θ (1) амортизированного времени. Анализ можно сравнить с неявными deques Окасаки, с той лишь разницей, что тип FingerTree хранит узлы вместо пар. [1]
Заявление
Деревья из пальцев можно использовать для постройки других деревьев. [4] Например, приоритетная очередь может быть реализована путем маркировки внутренних узлов по минимальному приоритету их дочерних элементов в дереве, или индексированный список / массив может быть реализован с маркировкой узлов по количеству листьев в их дети. Другие приложения - это последовательности с произвольным доступом, описанные ниже, упорядоченные последовательности и интервальные деревья . [1]
Деревья пальцев могут обеспечивать амортизированное O (1) нажатие, реверсирование, выталкивание, добавление и разделение O (log n); и могут быть адаптированы для индексирования или упорядочивания последовательностей. И, как и все функциональные структуры данных, он по своей природе постоянен ; то есть всегда сохраняются более старые версии дерева.
Последовательности произвольного доступа
Деревья пальцев могут эффективно реализовывать последовательности с произвольным доступом. Это должно поддерживать быстрые позиционные операции, включая доступ к n- му элементу и разделение последовательности в определенной позиции. Для этого аннотируем дерево пальцев с размерами. [1]
Newtype Размер = размер { GETSIZE :: Н } вывода ( уравнение , Ord )Экземпляр Monoid Size где ∅ = Размер 0 Размер m ⊕ Размер n = Размер ( m + n )
N для натуральных чисел. Новый тип необходим, потому что тип является носителем различных моноидов. Еще один новый тип все еще необходим для элементов в последовательности, показанной ниже.
Newtype Эль = Эль { getElem :: } Newtype СтартПослед = Seq ( FingerTree Размер ( Эль )) экземпляр Измеренный ( Элемент a ) Размер где || Элем || = Размер 1
Эти строки кода показывают, что экземпляр работает как базовый вариант для измерения размеров, а элементы имеют размер один. Использование newtype s не вызывает штрафов во время выполнения в Haskell, потому что в библиотеке типы Size и Elem будут скрыты от пользователя с помощью функций-оберток.
С этими изменениями длина последовательности теперь может быть вычислена за постоянное время.
Первая публикация
Finger деревья впервые были опубликованы в 1977 году Леонидас J Гибас , [5] и периодически рафинированное , так как (например, версия , используя AVL деревья , [6] , не ленивым пальцев деревьев, более простые 2-3 пальца деревья , показанные здесь, [1] B -Деревья и тд)
Реализации
Finger дерева с тех пор были использованы в Haskell основных библиотек (в реализации Data.Sequence ), а реализация в OCaml существует [7] , которая была получена из проверенной-правильно Кока реализации. [8] Деревья пальцев могут быть реализованы с ленивым вычислением или без него , [9] но лень допускает более простые реализации.
Смотрите также
Рекомендации
- ^ Б с д е е г ч я Гинец, Ralf; Патерсон, Росс (2006), "Finger деревья: Простой общего назначения структуры данных" (PDF) , журнал функционального программирования , 16 (2): 197-217, DOI : 10,1017 / S0956796805005769.
- ^ а б Гибянский, Андрей. «Пальчиковые деревья - Андрей Гибянский» . andrew.gibiansky.com . Проверено 26 октября 2017 .
- ^ «Пальцы сделаны правильно (я надеюсь)» . Хорошая математика, плохая математика . Проверено 26 октября 2017 .
- ^ Саркар, Абхируп. "Finger Tree - окончательная структура данных?" . abhiroop.github.io . Проверено 26 октября 2017 .
- ^ Guibas, LJ ; McCreight, EM; Plass, MF; Робертс, Дж. Р. (1977), «Новое представление линейных списков», Отчет о конференции девятого ежегодного симпозиума ACM по теории вычислений , стр. 49–60..
- ^ Цакалидис, AK (1985), "АВЛ-деревья для локализованного поиска", информации и управления , 67 (1-3): 173-194, DOI : 10.1016 / S0019-9958 (85) 80034-6.
- ^ Еженедельные новости Caml
- ^ Матье Созо :: Зависимые деревья пальцев в Coq
- ^ Kaplan, H .; Tarjan, RE (1995), «Постоянные списки с цепочкой через рекурсивное замедление», Труды двадцать седьмого ежегодного симпозиума ACM по теории вычислений , стр. 93–102.
Внешние ссылки
- http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
- http://hackage.haskell.org/packages/archive/EdisonCore/1.2.1.1/doc/html/Data-Edison-Concrete-FingerTree.html
- Пример 2-3 деревьев на C #
- Пример дерева пальцев Хинце / Патерсона в Java
- Пример дерева пальцев Хинце / Патерсона в C #
- "Моноиды и деревья пальцев в Haskell"
- "Библиотека дерева пальцев для Clojure"
- «Пальцевое дерево в Скалазе»
- "Проверенные пальчики в Изабель / ХОЛ"