Р-стабло

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

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

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

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

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

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

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

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

Варијанте

  • Р* стабло
  • Р+ стабло
  • Хилбертово Р-стабло
  • Приоритетно Р-стабло (ПР-стабло) - ПР-стабло има перформансе сличне најбољој познатој варијанти Р-стабла у стварним ситуацијама и релевантан распоред података, али их значајно надмашује у екстремнијим случајевима.[1]
други језици
čeština: R-strom
Deutsch: R-Baum
English: R-tree
español: Árbol-R
עברית: עץ R
hrvatski: R-stablo
italiano: R-tree
日本語: R木
한국어: R 트리
polski: R-drzewo
português: Árvores R
українська: R-дерево
中文: R树