Р-стабло

Из Википедије, слободне енциклопедије
Једноставан примјер Р-стабла за 2D квадрате

Р-стабла су стабла структуре података слична Б-стаблима, кориштена за приступ просторним подацима тј., за индексирање вишедимензионих информација; нпр., (X, Y) координате простиорних података. Уобичајена употреба Р-стабла могла би бити: „Пронађи све музеје унутар 2км од моје тренутне локације“.

Структуру података дјели хијерархијски просторно угнежђен, са могућим преклапањем, минимални обухватни квадрат (MBR, још познат као bounding box, тј. „квадрат (rectangle)", од чега „Р“ у Р-стаблу).

Сваки чвор Р-стабла има промјењив број улаза (до неког предефинисаног максимума). Сваким улазом унутар не-лисног чвора похрањују се два податка: начин идентификације чвора насљедника и минимална обухватна кутија свих улаза унутар чвора насљедника.

Алгоритми уноса и брисања обухватних кутија користе обухватне кутије из чворова да осигурају да су „оближњи“ елементи постављени у исти лисни чвор (поготово, нови елемент ће ићи у лисни чвор који захтијева најмање увећање обухватне кутије). Сваки улаз унутар лисног чвора похрањује два податка: начин идентификације стварног елемента податка (који, алтернативно, могу бити постављени директно у чвор), и оквирну кутију елемента податка.

Слично, алгоритми претраге (напримјер; пресјек, садржавање, најближи) користе обухватне кутије да одреде дали да претражују унутар чвора насљедника. У том случају, већина чворова у стаблу нису никада „додирнути“ током претраге. Као Б-стабла, ово чини Р-стабла погодним за базе података, гдје чворови могу бити похрањени у меморију кад је то потребно.

Различити алгоритми могу бити искоришћени да раздвоје чворове када они постану препуни, резултујући квадратном и линеарном подтипу Р-стабла.

Р-стабла не гарантују традиционално добре перформансе у кризним случајима, али генерално се добро сналазе у стварним ситуацијама. Ипак, нови алгоритам који дефинише Приоритете у Р-стаблу је објавњен 2004-те и обећава ефикасност као тренутно најефикасанији метод и има исти оптимум у кризним случајевима.

Варијанте[уреди]

  • Р* стабло
  • Р+ стабло
  • Хилбертово Р-стабло
  • Приоритетно Р-стабло (ПР-стабло) - ПР-стабло има перформансе сличне најбољој познатој варијанти Р-стабла у стварним ситуацијама и релевантан распоред података, али их значајно надмашује у екстремнијим случајевима.[1]

Алгоритам[уреди]

Претрага[уреди]

Улаз је квадрат претраге (Query box). Претрага је слична претраги у Б-стаблу. Почиње из корјеног чвора стабла. Сваки унутрашњи чвор садржи сет квадрата и показивача ка одговарајућем чвору насљеднику и сваки лисни чвор садржи квадрате просторних објеката (показивач ка неком просторном објекту може бити ту). За сваки квадрат и чвору, мора бити одлучено дали се преклапа са претражним квадратом или не. Ако да, одговарајући чвор насљедник мора такође бити претражен. Претрага се ради рекурзивно све док сви преклапајући чворови не буду заобиђени. Када је лисни чвор достигнут, садржане обухватне кутије (квадрати) се тестирају квадратом претраге и објекти (ако их има) се смјештају у резултујући скуп ако леже унутар претражног квадрата.

Уметање[уреди]

За уметање објекта, стабло се пређе рекурзивно од корјеног чвора. Сви квадрати у текућем интерном чвору се испитују. Ограничење најмање покривености је упослено за уметање објеката, тј., кутија која треба најмање увећање да обухвати нови објекат је одабрана. У случају гдје више од једног квадрата испуњава тај услов, одабере се онај са најмањом површином. Уметање се наставља рекурзивно у одабраном чвору. Једном кад је достигнут лисни чвор, ако лисни чвор није пун, непосредно се умеће објекат. Ако је лисни чвор попуњен, он мора бити подијељен прије уметања. Неколико алгоритама за подјелу је предложено за добре перформансе Р-стабла.

Уметање паковања[уреди]

  • Sort-Tile-Recursive (STR) [2]
  • Паковано хилбертово стабло - Користи Хилбертову вриједност центра квадрата да сортира лисне чворовеи сагради стабло рекурзивно.
  • најближи-X - Квадрати су сортирани на x-координатуи и чворови су креирани.

Види још[уреди]

Референце[уреди]

  1. ^ Lars Arge, Mark de Berg, Herman J. Haverkort, Ke Yi: The Priority RTree: A Practically Efficient and WorstCase Optimal RTree, Приступљено 24. 4. 2013.
  2. ^ Scott T. Leutenegger, Jeffrey M. Edgington and Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing, Приступљено 24. 4. 2013.

Литература[уреди]

Спољашње везе[уреди]