Пальчиковое дерево
-
Описание пальцевого дерева
- Пальцевое дерево — функциональная структура данных, используемая для эффективной реализации других структур данных.
- Обеспечивает амортизированный постоянный доступ к листьям и логарифмическое время объединения и разделения.
- Внутренние узлы хранят сводные данные, используемые для функциональности структур данных.
-
Структура пальцевого дерева
- Пальцы — точки доступа к частям структуры данных.
- Пальцы добавляются к исходному дереву для постоянного доступа.
- Пальцевое дерево состоит из слоев, идентифицируемых по узлам вдоль корешка.
- Корешок — ствол дерева, на каждом уровне есть по два узла, соединенных в пару.
-
Преобразование дерева в пальцевое
- Начинается со сбалансированного дерева 2-3.
- Пальцы добавляются к концам дерева, образуя застежку-молнию.
- Пальцы обеспечивают постоянный доступ к концам последовательности.
-
Операции и сокращения
- Операции деквалификации занимают Θ(1) амортизированного времени.
- Сокращения используются для эффективного представления данных.
-
Приложения и реализации
- Пальцевое дерево может использоваться для создания других деревьев, таких как приоритетные очереди и индексированные списки.
- Реализовано в основных библиотеках Haskell, OCaml, Isabelle и других языках.
-
История и развитие
- Впервые опубликовано в 1977 году Леонидасом Дж. Гибасом.
- С тех пор уточнялось и реализовывалось в различных языках и средах.