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

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

А расслабленный K-d дерево или расслабленный K-мерное дерево это структура данных, которая является вариантом K-d деревья. Подобно K-мерным деревьям, расслабленное K-мерное дерево хранит набор n-многомерных записей, каждая из которых имеет уникальный K-мерный ключ. х = (х0,... ,ИксК − 1). В отличие от деревьев K-d, в расслабленном K-d дереве дискриминанты в каждом узле произвольны. Расслабленные деревья K-d были представлены в 1998 году.[1]

Определения

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

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

Если К = 1, расслабленное K-d дерево - это двоичное дерево поиска.

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

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

Средние временные сложности в расслабленном K-d дереве с п записи:

  • Запросы с точным соответствием: O (log n)
  • Запросы с частичным соответствием: O (n1 − f (с / К)), куда:
    • s из K атрибутов указаны
    • при 0
  • Запросы ближайшего соседа: O (log n)[3]

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

  • k-d дерево
  • неявный k-d дерево, а k-d дерево, определенное неявной функцией разделения, а не явно сохраненным набором разделений
  • мин Макс k-d дерево, а k-d дерево, которое связывает минимальное и максимальное значение с каждым из его узлов

использованная литература

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