Расслабленное k -d дерево

Расслабленное *k -d* дерево
Расслабленное k -d дерево
Тип	Многомерное БСТ
Изобретенный	1998
Изобретён	Амалия Дуч, Владимир Эстивилл-Кастро и Конрадо Мартинес
Операция
Временная сложность в обозначении большого О
Операция	Средний
Поиск	О( вход )
Вставлять	О( вход )
Удалить	О( вход )
Пространственная сложность
Космос	На )

Расслабленное — это структура данных , K -d-дерево или расслабленное K -мерное дерево которая является вариантом Kd-деревьев . Подобно K-мерным деревьям, расслабленное K-мерное дерево хранит набор n-многомерных записей, каждая из которых имеет уникальный K-мерный ключ x=(x ₀ ,... ,x _K−1 ) . В отличие от деревьев Kd, в расслабленном дереве Kd дискриминанты в каждом узле произвольны. Ослабленные деревья Kd были представлены в 1998 году. ^{[ 1 ]}

Определения

Расслабленное дерево Kd для набора K-мерных ключей представляет собой двоичное дерево, в котором:

Каждый узел содержит K-мерную запись и связан с ним произвольный дискриминант j ∈ {0,1,...,K − 1} .
Для каждого узла с ключом x и дискриминантом j справедлив следующий инвариант: любая запись в левом поддереве с ключом y удовлетворяет условию y _j < x _j , а любая запись в правом поддереве с ключом y удовлетворяет условию y _j ≥ x _j . ^{[ 2 ]}

Если K = 1 , расслабленное дерево Kd является бинарным деревом поиска .

Как и в дереве Kd, расслабленное дерево Kd размера n приводит к разбиению области D на n+1 область, каждая из которых соответствует листу дерева Kd. Ограничивающая рамка (или массив границ) узла {x,j} — это область пространства, ограниченная листом, в который попадает x, когда он вставляется в дерево. Таким образом, ограничивающий прямоугольник корня {y,i} равен [0,1] ^К, ограничивающий прямоугольник корня левого поддерева равен [0,1] × ... × [0,y _i ] × ... × [0,1] и так далее.

Поддерживаемые запросы

Средние временные сложности в расслабленном дереве Kd с n записями составляют:

Запросы с точным соответствием: O(log n)
Запросы с частичным совпадением: O(n ^1−f(с/К)), где:
- указаны атрибуты s из K
- с 0 < f(s/K) < 1, вещественная функция от s/K
Запросы к ближайшему соседу: O(log n) ^{[ 3 ]}

См. также

k -d дерево
неявное k дерево -d , дерево k -d, определяемое неявной функцией расщепления, а не явно сохраненным набором расщеплений.
min/max k -d дерево , k -d дерево, которое связывает минимальное и максимальное значение с каждым из своих узлов.

Ссылки

^ Дач, Амалия; Эстивилл-Кастро, Владимир; Мартинес, Конрадо (14 декабря 1998 г.). Чва, Кён Ён; Ибарра, Оскар Х. (ред.). Рандомизированные K-мерные бинарные деревья поиска . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 198–209 . CiteSeerX 10.1.1.55.3293 . дои : 10.1007/3-540-49381-6_22 . ISBN 9783540653851 .
^ Дач, Амалия; Мартинес, Конрадо (2005). «Повышение производительности многомерного поиска с помощью пальцев» (PDF) . Журнал экспериментальной алгоритмики ACM . 10 . дои : 10.1145/1064546.1180615 . S2CID 2130863 . Проверено 23 августа 2016 г. .
^ Чва, Кён Ён; Ибарра, Оскар Х. (29 июня 2003 г.). Алгоритмы и вычисления: 9-й Международный симпозиум, ISAAC'98, Тэджон, Корея, 14-16 декабря 1998 г., Труды . Спрингер. стр. 202–203. ISBN 9783540493815 . Проверено 23 августа 2016 г. .

[1] Дач, Амалия; Эстивилл-Кастро, Владимир; Мартинес, Конрадо (14 декабря 1998 г.). Чва, Кён Ён; Ибарра, Оскар Х. (ред.). Рандомизированные K-мерные бинарные деревья поиска . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 198–209 . CiteSeerX 10.1.1.55.3293 . дои : 10.1007/3-540-49381-6_22 . ISBN 9783540653851 .

[2] Дач, Амалия; Мартинес, Конрадо (2005). «Повышение производительности многомерного поиска с помощью пальцев» (PDF) . Журнал экспериментальной алгоритмики ACM . 10 . дои : 10.1145/1064546.1180615 . S2CID 2130863 . Проверено 23 августа 2016 г. .

[3] Чва, Кён Ён; Ибарра, Оскар Х. (29 июня 2003 г.). Алгоритмы и вычисления: 9-й Международный симпозиум, ISAAC'98, Тэджон, Корея, 14-16 декабря 1998 г., Труды . Спрингер. стр. 202–203. ISBN 9783540493815 . Проверено 23 августа 2016 г. .

[ 1 ]

[ 2 ]

[ 3 ]