Дерево поиска пальцем
В информатике деревья поиска пальцев — это тип двоичного дерева поиска , в котором хранятся указатели на внутренние узлы, называемые пальцами . Пальцы ускоряют поиск, вставку и удаление элементов, близких к пальцам, давая амортизированный поиск O (log n), а также амортизированный O(1) вставок и удалений. Его не следует путать с деревом пальцев или деревом расширения , хотя оба могут использоваться для реализации деревьев поиска пальцев.
Гуибас и др. [ 1 ] представил деревья поиска пальцев, опираясь на B-деревья . Исходная версия поддерживает поиск по отпечатку пальца за время O(log d), где d — количество элементов между пальцем и целью поиска. Обновления занимают время O(1), при этом поддерживаются только подвижные пальцы O(1). Перемещение пальца в p-позиции требует времени O(log p). Хаддлстон и Мельхорн усовершенствовали эту идею, создав B-деревья, связанные уровнями. [ 2 ]
Цакалидис предложил версию, основанную на деревьях AVL , которая облегчает поиск с концов дерева; его можно использовать для реализации структуры данных с несколькими пальцами, используя несколько таких деревьев. [ 3 ]
Чтобы выполнить пальцевый поиск в двоичном дереве, идеальный способ — начать с пальца и искать вверх к корню, пока не достигнем наименьшего общего предка , [ 4 ] [ 5 ] также называемый поворотным узлом , [ 3 ] x и y, а затем идем вниз, чтобы найти искомый элемент. Определить, является ли узел предком другого, нетривиально.
Treaps — рандомизированная древовидная структура, предложенная Зейделем и Арагоном. [ 5 ] обладает тем свойством, что ожидаемая длина пути двух элементов расстояния d равна O(log d ). Для пальцевого поиска они предложили добавлять указатели для быстрого определения наименьшего общего предка (LCA) или для поддержания в каждом узле минимального и максимального значений его поддерева.
Написана глава книги, в которой подробно рассматриваются деревья поиска пальцев. [ 4 ] В котором Бродал предложил алгоритм, позволяющий выполнять поиск по отпечаткам пальцев за время O(log d) без необходимости какой-либо дополнительной бухгалтерской информации; этот алгоритм достигает этого путем одновременного поиска вниз от последнего кандидата LCA.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Гибас, ЖЖ (1977). «Новое представление линейных списков». Материалы девятого ежегодного симпозиума ACM по теории вычислений - STOC '77 . стр. 49–60. CiteSeerX 10.1.1.527.7294 . дои : 10.1145/800105.803395 . S2CID 2414154 .
- ^ Хаддлстон; Мельхорн, Курт (1982). «Новая структура данных для представления отсортированных списков». Акта Информатика . 17 (2): 157–184. дои : 10.1007/BF00288968 . S2CID 10397918 .
- ^ Перейти обратно: а б Цакалидис, Афанасиос К. (1985). «AVL-деревья для локализованного поиска» . Информация и контроль . 67 (1–3): 173–194. дои : 10.1016/S0019-9958(85)80034-6 .
- ^ Перейти обратно: а б Бродал, Герт Столтинг (2005). «11. Поиск пальцем» (PDF) . В Мехте, Динеш П.; Сахни, Сартадж (ред.). Справочник по структурам данных и приложениям . Чепмен и Холл / CRC Press . ISBN 978-1584884354 . Проверено 1 января 2013 г.
- ^ Перейти обратно: а б Зейдель, Р .; Арагон, Чехия (1996). «Рандомизированные деревья поиска». Алгоритмика . 16 (4–5): 464–497. CiteSeerX 10.1.1.122.6185 . дои : 10.1007/BF01940876 . S2CID 9370259 .
 | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |