Back

ⓘ Р+ стабло




                                     

ⓘ Р+ стабло

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

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

                                     

1. Разлика између Р+ и Р стабала

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

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

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

2. Предности

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

3. Мане

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

Users also searched:

...