Пальчиковое дерево - Finger tree

Для двоичного дерева поиска см. дерево поиска пальцем.

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

Обзор

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

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

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

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

2-3 дерева и оно превратилось в пальчиковое дерево
Показывает, что 2-3 дерева (вверху) можно втянуть в пальмовое дерево (внизу)

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

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

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

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

Чтобы преобразиться, начните со сбалансированного 2-3 дерева.

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

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

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

данные FingerTree а = Пустой                     | Одинокий а                     | Глубокий (Цифра а) (FingerTree (Узел а)) (Цифра а)данные Узел а = Узел 2 а а | Узел 3 а а а

Цифры в показанных примерах - это узлы с буквами. Каждый список разделен префиксом или суффиксом каждого узла на корешке. В преобразованном дереве 2-3 кажется, что списки цифр на верхнем уровне могут иметь длину два или три, а нижние уровни имеют длину только один или два. Для того, чтобы некоторые приложения деревьев пальцев работали так эффективно, деревья пальцев допускают от одного до четырех поддеревьев на каждом уровне. Цифры дерева пальцев могут быть преобразованы в список следующим образом:[1]

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

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

Скидки

Deque операции

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

Заявление

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

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

Последовательности произвольного доступа

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

Новый тип Размер = Размер{ getSize :: N }  получение (Уравнение, Ord)пример Моноид Размер куда  ∅ = Размер 0  Размер м ⊕ Размер п = Размер (м + п)

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

Новый тип Elem а = Elem{ getElem :: а }Новый тип Seq а = Seq (FingerTree Размер (Elem а))пример Измерено (Elem а) Размер куда  ||Elem|| = Размер 1

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

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

Первая публикация

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

Реализации

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

Смотрите также

Рекомендации

  1. ^ а б c d е ж грамм час я Хинце, Ральф; Патерсон, Росс (2006), «Деревья пальцев: простая структура данных общего назначения» (PDF), Журнал функционального программирования, 16 (2): 197–217, Дои:10.1017 / S0956796805005769.
  2. ^ а б Гибянский, Андрей. «Деревья пальцев - Андрей Гибянский». andrew.gibiansky.com. Получено 2017-10-26.
  3. ^ "Пальцы сделаны правильно (надеюсь)". Хорошая математика, плохая математика. Получено 2017-10-26.
  4. ^ Саркар, Абхируп. "Дерево пальцев - окончательная структура данных?". abhiroop.github.io. Получено 2017-10-26.
  5. ^ Гибас, Л. Дж.; McCreight, E.M .; Plass, M. F .; Робертс, Дж. Р. (1977), "Новое представление линейных списков", Запись конференции девятого ежегодного симпозиума ACM по теории вычислений, стр. 49–60.
  6. ^ Цакалидис, А. К. (1985), "AVL-деревья для локализованного поиска", Информация и контроль, 67 (1–3): 173–194, Дои:10.1016 / S0019-9958 (85) 80034-6.
  7. ^ Еженедельные новости Caml
  8. ^ Матье Созо :: Зависимые деревья пальцев в Coq
  9. ^ Kaplan, H .; Тарьян, Р.Э. (1995), «Постоянные списки с цепочкой через рекурсивное замедление», Материалы двадцать седьмого ежегодного симпозиума ACM по теории вычислений, стр. 93–102.

внешняя ссылка