Р+ стабло

Из Википедије, слободне енциклопедије

Р+ стабло је метод за преглед података користећи локацију, често (x, y) координате, а често и за локације на површини Земље. Претраживање за један број је решен проблем; претраживање 2 или више, и захтев за локацијама које су близу у x и y правцима захтева коришћење „лукавијих“ алгоритама.

У основи, Р+ стабло је стабло структуре података, варијанта Р стабла, које се користи за индексирање просторних информација.

Разлика између Р+ и Р стабала[уреди]

Р+ стабла су компромис између Р-стабла и КД-стабла: оне избегавају преклапање унутрашњих чворова убацивањем објекта у више листова, ако је потребно. Покривеност је цела област која покрива све сродне квадрате. Преклапање је цела област која се налази у два или више чворова.[1] Минимална покривеност смањује количину празног простора који је покривен чворовима Р стабла. Минимално преклапање смањује скуп путева претраге до листова (што је чак битније за време приступања него за минималну покривеност). Ефикасна претрага захтева минималну покривеност и преклапање.

Р+ стабла се разликују од Р стабала по:

  • За чворове се не гарантује да ће бити бар пола попуњени
  • Ставке било ког унутрашњег чвора се не преклапају
  • Идентификација објекта може да се чува у више од једног лист-чвора

Предности[уреди]

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

Мане[уреди]

  • Пошто се квадрати дуплирају, Р+ стабло може бити веће од Р стабла које је направљено на основу истих података.
  • Конструкција и одржавање Р* стабла је много компликованије од конструкције и одржавања Р стабла и његових других варијанти.

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

  1. ^ Härder & Rahm (2007), стр. 285, 286.

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