Демалған k-d ағашы - Relaxed k-d tree

Босаңсыды к-d ағаш
ТүріКөпөлшемді BST
Ойлап тапты1998
Ойлап тапқанАмалия Дуч, Владимир Эстивилл-Кастро және Конрадо Мартинес
Уақыттың күрделілігі жылы үлкен O белгісі
АлгоритмОрташаЕң нашар жағдай
ҒарышO (n)O (n)
ІздеуO (журнал n)O (n)
КірістіруO (журнал n)O (n)
ЖоюO (журнал n)O (n)

A босаңсыды Қ-d ағаш немесе босаңсыды Қ-өлшемді ағаш нұсқасы болып табылатын мәліметтер құрылымы болып табылады K-d ағаштары. K өлшемді ағаштар сияқты, босаңсыған K өлшемді ағашта әрқайсысында ерекше өлшемді кілт бар n өлшемді жазбалар жиынтығы сақталады x = (x0, ..., xK − 1). K-d ағаштарынан айырмашылығы, босаңсыған K-d ағашында әр түйіндегі дискриминанттар ерікті болып табылады. Босанған К-д ағаштары 1998 жылы енгізілген.[1]

Анықтамалар

K өлшемді кілттер жиынтығына арналған босаңсытылған K-d ағашы дегеніміз екілік ағаш, онда:

  1. Әр түйінде K-өлшемді жазба бар және ерікті дискриминантпен байланысты j ∈ {0,1, ..., K - 1}.
  2. Кілті бар әр түйін үшін х және дискриминантты j, келесі инвариант дұрыс: оң кілт кезіндегі жазба y кілтімен қанағаттандырылады жj j және сол жақ кіші ағаштағы у кілтімен кез келген жазба қанағаттандырады жj ≥ xj.[2]

Егер K = 1, босаңсыған K-d ағашы - бұл екілік іздеу ағашы.

K-d ағашындағыдай, жай өлшемдегі K-d ағашы n D доменінің бөлігін тудырады n + 1 әрқайсысы K-d ағашындағы жапыраққа сәйкес келеді. {X, j} түйінінің шекті қорапшасы (немесе шектер жиымы) - бұл жапырақпен бөлінген кеңістіктің, ол ағашқа енгізген кезде х түсіп кетеді. Сонымен, {y, i} түбірінің шектік өрісі [0,1]Қ, сол жақ ағаштың түбірінің шектеу өрісі [0,1] × ... × [0, yмен] × ... × [0,1] және т.б.

Қолдау көрсетілетін сұраулар

-Мен босаңсыған К-д ағашындағы уақыттың орташа күрделілігі n жазбалар:

  • Нақты сәйкестік сұраулары: O (log n)
  • Ішінара сәйкестік сұраулары: O (n1 − f (s / K)), мұнда:
    • K атрибуттарының ішіндегі бөліктер көрсетілген
    • 0
  • Жақын маңдағы сұраулар: O (log n)[3]

Сондай-ақ қараңыз

  • к-d ағаш
  • жасырын к-d ағаш, а к-d ағашы анық сақталған бөліністер жиынтығынан гөрі айқын емес бөлу функциясымен анықталады
  • мин / макс к-d ағаш, а кминималды және максималды мәнді әр түйінмен байланыстыратын -д ағаш

Әдебиеттер тізімі

  1. ^ Дуч, Амалия; Эстивилл-Кастро, Владимир; Мартинес, Конрадо (1998-12-14). Чва, Кён-Ён; Ибарра, Оскар Х. (ред.) Кездейсоқ өлшемді екілік іздеу ағаштары. Информатика пәнінен дәрістер. Springer Berlin Heidelberg. бет.198–209. CiteSeerX  10.1.1.55.3293. дои:10.1007/3-540-49381-6_22. ISBN  9783540653851.
  2. ^ Дуч, Амалия; Мартинес, Конрадо (2005). «Саусақ көмегімен көп өлшемді іздеудің жұмысын жақсарту» (PDF). ACM Journal of Experimental Algorithmics. 10. Алынған 23 тамыз 2016.
  3. ^ Чва, Кён-Ён; Ибарра, Оскар Х. (2003-06-29). Алгоритмдер және есептеу: 9-шы Халықаралық симпозиум, ISAAC'98, Теджон, Корея, 14-16 желтоқсан, 1998 ж., Іс жүргізу. Спрингер. 202–203 бет. ISBN  9783540493815. Алынған 23 тамыз 2016.