Пальцевое дерево

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

Обзор [ править ]

Дерево пальцев используется как простая очередь с амортизированными операциями ввода и получения O(1). Целые числа от 1 до 21 вставляются справа и извлекаются слева. Квадратные блоки представляют значения, «Цифра» (небесно-голубой) может иметь 1–4 дочерних элемента, «Узел» (темно-синий) может иметь 2–3 дочерних элемента, белый кружок означает «Пустой», красный узел представляет «Единственное» значение и зеленый узлы представляют «глубокие» значения. Обратите внимание, что на каждом шаге мы удаляем позвоночник, однозначные и дочерние элементы из цифр вкладываются в новый уровень узлов.

Ральф Хинце и Росс Патерсон утверждают, что пальцевое дерево — это функциональное представление постоянных последовательностей, которые могут получить доступ к концам за амортизированное постоянное время. Конкатенация и разделение могут выполняться за логарифмическое время в размере меньшего куска. Структуру также можно превратить в структуру данных общего назначения, определив операцию разделения в общей форме, позволяя ей действовать как последовательность, очередь приоритетов, дерево поиска или очередь приоритетного поиска, среди других разновидностей абстрактных типов данных. ^[1]

Палец — это точка, через которую можно получить доступ к части структуры данных; в императивных языках это называется указателем. ^[2] В дереве пальцев пальцы представляют собой структуры, указывающие на концы последовательности или листовые узлы. Пальцы добавляются к исходному дереву, чтобы обеспечить постоянный доступ к пальцам. На изображениях, показанных ниже, пальцы представляют собой линии, идущие от позвоночника к узлам.

Пальцевое дерево состоит из различных слоев , которые можно идентифицировать по узлам вдоль его позвоночника . Позвоночник дерева можно рассматривать как ствол, точно так же, как у дерева есть листья и корень. Хотя пальчатые деревья часто изображаются с позвоночником и ветвями, отходящими по бокам, на самом деле на позвоночнике на каждом уровне есть два узла, которые были спарены, чтобы образовать центральный позвоночник. Префикс суффикс находится слева от позвоночника, а — справа. Каждый из этих узлов имеет связь со следующим уровнем позвоночника, пока не достигнет корня. ^[2]

Первый уровень дерева содержит только значения, конечные узлы дерева, и имеет глубину 0. Второй уровень имеет глубину 1. Третий уровень имеет глубину 2 и так далее. Чем ближе к корню, тем глубже поддеревья исходного дерева (дерева до того, как оно было пальцевым деревом), на которые указывают узлы. Таким образом, работа по дереву идет от листьев к корню дерева, что противоположно типичной древовидной структуре данных. Чтобы получить эту красивую и необычную структуру, мы должны убедиться, что исходное дерево имеет одинаковую глубину. Чтобы гарантировать единообразие глубины, при объявлении объекта узла его необходимо параметризовать типом дочернего узла. Узлы на позвоночнике глубины 1 и выше указывают на деревья, и с помощью этой параметризации они могут быть представлены вложенными узлами. ^[3]

Превращение дерева в пальчиковое дерево [ править ]

Мы начнем этот процесс со сбалансированного дерева 2–3 . Чтобы дерево пальцев работало, все конечные узлы также должны быть ровными.

Палец — это «структура, обеспечивающая эффективный доступ к узлам дерева вблизи определенного места». ^[1] Чтобы сделать дерево из пальцев, нам нужно приложить пальцы к правому и левому концам дерева и трансформировать его, как молнию . Это дает нам постоянный доступ к концам последовательности с амортизированным временем.

Чтобы трансформироваться, начните со сбалансированного дерева 2–3.

Возьмите самый левый и самый правый внутренние узлы дерева и потяните их вверх так, чтобы остальная часть дерева болталась между ними, как показано на изображении справа.

Объедините колючки, чтобы получить стандартное деревце в 2–3 пальца.

Это можно описать как: ^[1]

данные   FingerTree   a     =   Пусто     |   Один       |   Deep   (  Цифра   a  )   (  FingerTree   (  Узел   a  ))   (  Цифра   a  )  данных   Узел   a     =   Node2   a   a     |   Node3   а   а   а

Цифры в показанных примерах — это узлы с буквами. Каждый список разделен префиксом или суффиксом каждого узла позвоночника. В преобразованном дереве 2–3 кажется, что списки цифр на верхнем уровне могут иметь длину две или три, а нижние уровни имеют длину только одну или две. Чтобы некоторые приложения пальцевых деревьев работали так эффективно, пальцевые деревья допускают от одного до четырех поддеревьев на каждом уровне.

Цифры дерева пальцев можно преобразовать в список следующим образом: ^[1]

введите   Цифра   a   =   Один   a   |   Два   а   |     Три   а   а   |     Четыре   а   а   а   а

Итак, на изображении верхний уровень имеет элементы типа a , следующий имеет элементы типа Node a , потому что узел между позвоночником и листьями, и это в целом означает, что n -й уровень дерева имеет элементы типа $Node^{n}$ a , или 2–3 дерева глубины n. Это означает, что последовательность из n элементов представлена деревом глубины Θ(log n ). Более того, элемент d , расположенный с ближайшего конца, хранится на глубине Θ(log d) в дереве. ^[1]

Сокращения [ править ]

${\begin{aligned}\mathrm {instance} &\ Reduce\ Node\ \mathrm {where} &&\\&reducer\ (\prec )\ (Node2\ a\ b)\ z&=&\ a\ \prec (b\ \prec \ z)\\&reducer\ (\prec )\ (Node3\ a\ b\ c)\ z&=&\ a\ \prec (\ b\prec (c\ \prec \ z))\\\\&reducel\ (\succ )\ z\ (Node2\ b\ a)\ &=&\ (z\ \succ \ b)\ \succ \ a\\&reducel\ (\succ )\ z\ (Node3\ c\ b\ a)\ &=&\ ((z\ \succ \ c)\succ \ b)\succ \ a\\\end{aligned}}$

${\begin{aligned}\mathrm {instance} &\ Reduce\ FingerTree\ \mathrm {where} &&\\&reducer\ (\prec )\ (Empty)\ z\ &=&\ z\\&reducer\ (\prec )\ (Single\ x)\ z&=&\ x\ \prec \ z\\&reducer\ (\prec )\ (Deep\ pr\ m\ sf)\ z&=&\ pr\ \prec '\ (m\ \prec ''\ (sf\ \prec '\ z))\\&\ \ \ \ where\\&\ \ \ \ \ \ \ \ (\prec ')\ =reducer\ (\prec )\\&\ \ \ \ \ \ \ \ (\prec '')\ =reducer\ (reducer\ (\prec ))\\\\&reducel\ (\succ )\ z\ (Empty)\ &=&\ z\\&reducel\ (\succ )\ z\ (Single\ \ x)\ &=&\ z\ \succ \ x\\&reducel\ (\succ )\ z\ (Deep\ \ pr\ m\ sf)\ &=&\ ((z\ \succ '\ pr)\ \succ ''\ m)\ \succ '\ sf)\\&\ \ \ \ where\\&\ \ \ \ \ \ \ \ (\succ ')\ =reducel\ (\succ )\\&\ \ \ \ \ \ \ \ (\succ '')\ =reducel\ (reducel\ (\succ ))\\\end{aligned}}$

Поэтому операции [ править ]

Деревья пальцев также позволяют создавать эффективные деки . Независимо от того, является ли структура постоянной или нет, все операции занимают амортизированное время Θ(1). Анализ можно сравнить с неявными деками Окасаки, с той лишь разницей, что тип FingerTree хранит узлы вместо пар. ^[1]

Приложение [ править ]

Пальцевые деревья можно использовать для построения других деревьев. ^[4] Например, очередь с приоритетами может быть реализована путем маркировки внутренних узлов по минимальному приоритету ее дочерних элементов в дереве, или индексированный список/массив может быть реализован с маркировкой узлов по количеству листьев в их дочерних элементах. Другими приложениями являются последовательности произвольного доступа, описанные ниже, упорядоченные последовательности и деревья интервалов . ^[1]

Деревья пальцев могут обеспечивать амортизированное перемещение O(1), реверсирование, извлечение, добавление и разделение O(log n); и может быть адаптирован для индексации или упорядочения последовательностей. И, как и все функциональные структуры данных, она по своей сути постоянна ; то есть всегда сохраняются более старые версии дерева.

Последовательности с произвольным доступом [ править ]

Деревья пальцев могут эффективно реализовывать последовательности произвольного доступа. Это должно поддерживать быстрые позиционные операции, включая доступ к n -му элементу и разделение последовательности в определенной позиции. Для этого мы аннотируем дерево пальцев размерами. ^[1]

newtype   Size   =   Size  {   getSize   ::   N   }    получение   (  Eq  ,   Ord  )  экземпляра   моноида   размера   где    ∅   =   Размер   0    Размер   m   ⊕   Размер   n   =   Размер   (  m   +   n  )

N означает натуральные числа. Новый тип необходим, поскольку тип является носителем разных моноидов. Для элементов в последовательности, показанной ниже, по-прежнему необходим еще один новый тип.

newtype   Elem   a   =   Elem  {   getElem   ::   a   }  newtype   Seq   a   =   Seq   (  FingerTree   Размер   (  Elem   a  ))  экземпляр   Измеренный   (  Elem   a  )   Размер   где    ||  Элем  ||   =   Размер   1

Эти строки кода показывают, что экземпляр работает в базовом случае для измерения размеров, а элементы имеют размер один. Использование newtype не вызывает штрафов во время выполнения в Haskell, поскольку в библиотеке типы Size и Elem будут скрыты от пользователя с помощью функций-оболочек.

Благодаря этим изменениям длину последовательности теперь можно вычислять за постоянное время.

Первая публикация [ править ]

Пальцевые деревья были впервые опубликованы в 1977 году Леонидасом Дж. Гибасом . ^[5] и периодически уточняется с тех пор (например, версия, использующая деревья AVL , ^[6] неленивые деревья пальцев, здесь показаны более простые деревья из 2–3 пальцев, ^[1] B-деревья и так далее)

Реализации [ править ]

Деревья пальцев с тех пор используются в основных библиотеках Haskell (в реализации Data.Sequence реализация в OCaml. ), и существует ^[7] который был получен на основе проверенной правильной реализации Coq . ^[8] Существует также проверенная реализация на Isabelle (помощник по проверке), из которой можно генерировать программы на Haskell и других (функциональных) языках. ^[9] Деревья пальцев могут быть реализованы с ленивым вычислением или без него . ^[10] но лень позволяет реализовать более простые реализации.

См. также [ править ]

Ссылки [ править ]

↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Хинце, Ральф; Патерсон, Росс (2006), «Деревья пальцев: простая структура данных общего назначения» (PDF) , Журнал функционального программирования , 16 (2): 197–217, doi : 10.1017/S0956796805005769 , S2CID 6881581 .
↑ Перейти обратно: Перейти обратно: ^а ^б Гибянский, Андрей. «Пальчиковые деревья — Эндрю Гибиански» . andrew.gibiansky.com . Проверено 26 октября 2017 г.
^ «Пальцевые деревья сделаны правильно (надеюсь)» . Хорошая математика, плохая математика . Проверено 26 октября 2017 г.
^ Саркар, Абхируп. «Дерево пальцев — идеальная структура данных?» . abhiroop.github.io . Архивировано из оригинала 26 октября 2017 г. Проверено 26 октября 2017 г.
^ Гибас, LJ ; МакКрайт, EM; Пласс, МФ; Робертс, младший (1977), «Новое представление линейных списков», Протокол конференции девятого ежегодного симпозиума ACM по теории вычислений , стр. 49–60 .
^ Цакалидис, А.К. (1985), «AVL-деревья для локализованного поиска», Information and Control , 67 (1–3): 173–194, doi : 10.1016/S0019-9958(85)80034-6 .
^ Еженедельные новости Caml
^ Матье Созо :: Зависимые деревья пальцев в Коке
^ Нордхофф, Бенедикт; Кернер, Стефан; Ламмих, Питер. «Пальчиковые деревья» . Архив формальных доказательств . Проверено 26 ноября 2021 г.
^ Каплан, Х.; Тарьян, Р.Э. (1995), «Постоянные списки с катенацией посредством рекурсивного замедления», Труды двадцать седьмого ежегодного симпозиума ACM по теории вычислений , стр. 93–102 .

Внешние ссылки [ править ]

[:0-1] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Хинце, Ральф; Патерсон, Росс (2006), «Деревья пальцев: простая структура данных общего назначения» (PDF) , Журнал функционального программирования , 16 (2): 197–217, doi : 10.1017/S0956796805005769 , S2CID 6881581 .

[:1-2] Перейти обратно: Перейти обратно: ^а ^б Гибянский, Андрей. «Пальчиковые деревья — Эндрю Гибиански» . andrew.gibiansky.com . Проверено 26 октября 2017 г.

[3] «Пальцевые деревья сделаны правильно (надеюсь)» . Хорошая математика, плохая математика . Проверено 26 октября 2017 г.

[4] Саркар, Абхируп. «Дерево пальцев — идеальная структура данных?» . abhiroop.github.io . Архивировано из оригинала 26 октября 2017 г. Проверено 26 октября 2017 г.

[5] Гибас, LJ ; МакКрайт, EM; Пласс, МФ; Робертс, младший (1977), «Новое представление линейных списков», Протокол конференции девятого ежегодного симпозиума ACM по теории вычислений , стр. 49–60 .

[6] Цакалидис, А.К. (1985), «AVL-деревья для локализованного поиска», Information and Control , 67 (1–3): 173–194, doi : 10.1016/S0019-9958(85)80034-6 .

[7] Еженедельные новости Caml

[8] Матье Созо :: Зависимые деревья пальцев в Коке

[9] Нордхофф, Бенедикт; Кернер, Стефан; Ламмих, Питер. «Пальчиковые деревья» . Архив формальных доказательств . Проверено 26 ноября 2021 г.

[10] Каплан, Х.; Тарьян, Р.Э. (1995), «Постоянные списки с катенацией посредством рекурсивного замедления», Труды двадцать седьмого ежегодного симпозиума ACM по теории вычислений , стр. 93–102 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

v т и Древовидные структуры данных
Поиск деревьев ( динамические наборы / ассоциативные массивы )	2–3 2–3–4 АА (а, б) АВЛ Б B+ Б* Б ^х ( Оптимально ) Бинарный поиск Танцы HTree Интервал Статистика заказов ( Наклон влево ) Красно-черный козел отпущения Распространение Т Треп УБ Сбалансированный по весу
Кучи	Двоичный Биномиальный Мостовая долина д -и Фибоначчи Левый Сопряжение Наклонный бином Перекос от Эмде Боас Слабый
Пытается	Cтрие C-trie (сжатый ADT) Хэш Радикс Суффикс Троичный поиск X-быстрый Y-быстро
пространственных данных Деревья разделения	Мяч БК БСП Декартовский Гильберт Р. k -d ( неявный k -d ) М Метрика MVP Октри PH Приоритет Р Четырехместный Р Р+ Р* Сегмент вице-президент Х
Другие деревья	Крышка Экспоненциальный Фенвик Палец Индекс фрактального дерева Слияние Хэш-календарь iDistance К-и Левый ребенок, правый брат Связать/вырезать Лог-структурированное слияние Меркле ПК Диапазон SPQR Вершина