R-træ (datastruktur)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 29. september 2015; checks kræver 23 redigeringer .
R-træ
Type Multidimensionelt træ Binært søgetræ
Opfindelsens år 1984
Forfatter Antonin Guttman
Kompleksitet i O-symboler
Gennemsnit I værste fald
Søg O( log M n ) O( n )
 Mediefiler på Wikimedia Commons

R-træ ( eng.  R-trees ) er en trælignende datastruktur ( træ ), foreslået i 1984 af Antonin Guttman . Det ligner et B-træ , men bruges til at få adgang til rumlige data, det vil sige til at indeksere multidimensionel information , såsom geografiske data med todimensionelle koordinater ( breddegrad og længdegrad ). En typisk forespørgsel , der bruger R-træer, kan være: "Find alle museer inden for 2 kilometer fra min nuværende placering."

Denne datastruktur opdeler et flerdimensionelt rum i et sæt hierarkisk indlejrede og muligvis krydsende rektangler (for et todimensionelt rum). I tilfælde af tredimensionelt eller multidimensionelt rum vil disse være rektangulære parallelepipeder ( cuboids ) eller parallelotoper .

Indsættelses- og fjernelsesalgoritmerne bruger disse afgrænsningskasser til at sikre, at "tætte" objekter placeres på det samme bladspids. Især vil det nye objekt ramme det bladspids, der har brug for den mindste udvidelse af sin afgrænsningsramme. Hvert bladknudeelement gemmer to datafelter: en måde at identificere de data, der beskriver objektet (eller selve dataene) og afgrænsningsrammen for dette objekt.

På samme måde bruger søgealgoritmer (f.eks. skæringspunkter, inklusion, kvarter) afgrænsningsfelter til at beslutte, om der skal søges i en underknude. De fleste hjørner bliver således aldrig rørt under søgningen. Som med B-træer gør denne egenskab ved R-træer dem velegnede til databaser , hvor toppunkter kan skiftes ud til disk efter behov.

For at opdele overløbende hjørner kan forskellige algoritmer bruges, hvilket fører til opdelingen af ​​R-træer i undertyper: kvadratisk og lineær.

Oprindeligt garanterede R-træer ikke god worst-case ydeevne , selvom de fungerede godt på rigtige data. Men i 2004 blev en ny algoritme offentliggjort , der bestemmer prioriterede R-træer . Det hævdes, at denne algoritme er lige så effektiv som de mest effektive moderne metoder, og samtidig er optimal for worst case [1] .

R-træstruktur

Hvert hjørne af R-træet har et variabelt antal elementer (ikke mere end et forudbestemt maksimum). Hvert element i et toppunkt uden blade gemmer to datafelter: en måde at identificere det underordnede toppunkt på og en afgrænsningsramme (kasseform), der omslutter alle elementer i det underordnede toppunkt. Alle opbevarede tupler opbevares i samme dybdeniveau, så træet er perfekt afbalanceret. Når du designer et R-træ, skal du indstille nogle konstanter:

For at algoritmerne skal fungere korrekt, skal betingelsen MinEntries <= MaxEntries / 2 være opfyldt. Rodnoden kan have fra 2 til MaxEntries efterkommere. Ofte vælges MinEntries = 2, så er de samme betingelser opfyldt for roden som for resten af ​​hjørnerne. Det er også nogle gange klogt at afsætte separate konstanter for antallet af punkter i bladspidser, da du ofte kan lave flere af dem.

Algoritmer

Indsæt

Konstruktionen af ​​et R-træ sker som regel ved gentagne gange at kalde operationen med at indsætte et element i træet. Idéen med indsættelse svarer til indsættelse i et B-træ : hvis tilføjelse af et element til det næste toppunkt resulterer i et overløb, så opdeles toppunktet. Nedenfor er den klassiske indsættelsesalgoritme beskrevet af Antonin Guttman .

Indsæt funktion
  • Kalder ChooseLeaf for at vælge det blad, hvor elementet skal tilføjes. Hvis indsættelsen er udført, kan træet flækkes, og flækken kan gå helt til toppen. I dette tilfælde returnerer ChooseLeaf to SplitNodes til at indsætte i roden
  • Kalder funktionen AdjustBounds, som udvider rodens afgrænsningsramme til det punkt, der indsættes
  • Kontrollerer, om ChooseLeaf returnerede ikke-nul SplitNodes, så vokser træet et niveau op: fra dette øjeblik er roden det toppunkt, hvis børn er de samme SplitNodes
Funktionen ChooseLeaf
  • hvis input er et blad (rekursionsbase), så:
    • kalder DoInsert-funktionen, som direkte indsætter elementet i træet og returnerer to blade, hvis der sker en opdeling
    • ændrer toppunktets afgrænsningsrektangel, så det matcher det indsatte element
    • returnerer SplitNodes returneret af DoInsert
  • hvis input er et ikke-blads toppunkt:
    • af alle børn vælges den, hvis grænser kræver den mindste stigning for at indsætte det givne element
    • kalder rekursivt ChooseLeaf på det valgte barn
    • fikser afgrænsende rektangler
    • hvis splittedNodes fra det rekursive kald er nul, så forlader vi funktionen, ellers:
      • hvis NumEntries < MaxEntries, så tilføj et nyt vertex til børnene, rens SplitNodes
      • ellers (når der ikke er noget sted at indsætte), sammenkæder vi arrayet af børn med det nye vertex og sender den resulterende funktion til LinearSplitNodes-funktionen eller en anden vertex-opdelingsfunktion, og returnerer fra ChooseLeaf de SplitNodes, som den brugte opdelingsfunktion returnerede til os .
LinearSplit-funktionen

Forskellige algoritmer kan bruges til at adskille hjørner, dette er en af ​​dem. Den har kun lineær kompleksitet og er nem at implementere, selvom den ikke giver den mest optimale adskillelse. Men praksis viser, at en sådan kompleksitet normalt er tilstrækkelig.

  • for hver koordinat for hele sættet af delte hjørner beregnes forskellen mellem den maksimale nedre grænse af rektanglet ved denne koordinat og den mindste øvre grænse, derefter normaliseres denne værdi med forskellen mellem de maksimale og minimale koordinater for punkterne det originale sæt til at bygge hele træet
  • find maksimum af denne normaliserede spredning over alle koordinater
  • sæt som de første børn for de returnerede knudepunkter node1 og node2 de knudepunkter fra inputlisten, hvor maksimum blev nået, fjern dem fra inputlisten, juster grænserne for node1 og node2
  • derefter udføres indsættelse for de resterende hjørner:
    • hvis der er så få knudepunkter tilbage på listen, at hvis alle føjes til et af output-hjørnerne, så vil det indeholde MinEntries-hjørnepunkter, så føjes resten til den, vend tilbage fra funktionen
    • hvis et af hjørnerne allerede har et maksimum af børn, så lægges resten til det modsatte, retur
    • for det næste toppunkt fra listen sammenlignes det med hvor meget afgrænsningsrammen skal øges, når den indsættes i hver af de to fremtidige toppunkter, hvor den er mindre, indsættes den der
Den fysiske indsættelsesfunktion DoInsert
  • hvis der er ledige pladser ved toppunktet, så indsættes punktet der
  • hvis der ikke er nogen pladser, så kædes børnene af toppunktet sammen med det indsatte punkt, og LinearSplit-funktionen eller en anden opdelingsfunktion kaldes, hvilket returnerer to opdelte hjørner, som vi returnerer fra doInsert
Partitionering med klyngealgoritmer

Nogle gange bruges i stedet for et R-træ det såkaldte cR-træ (c står for clustered ). Den grundlæggende idé er, at klyngealgoritmer såsom k-midler bruges til at adskille hjørner eller punkter . Kompleksiteten af ​​k-midler er også lineær, men i de fleste tilfælde giver den et bedre resultat end den lineære Guttman-separationsalgoritme, i modsætning til hvilken den ikke kun minimerer det samlede areal af kassernes kuverter, men også afstanden mellem dem og overlapningsområdet. Til punktklynger bruges den valgte metrik for det oprindelige mellemrum; til toppunktklynger kan du bruge afstanden mellem midten af ​​deres konvolutter af parallelepipeder eller den maksimale afstand mellem dem.

Klyngealgoritmer tager ikke højde for det faktum, at antallet af efterkommere af et toppunkt er begrænset oppefra og nede af algoritmens konstanter. Hvis klyngeopdelingen giver et uacceptabelt resultat, kan du bruge den klassiske algoritme til dette sæt, da dette ikke sker ofte i praksis.

En interessant idé er at bruge clustering i flere klynger, hvor flere kan være mere end to. Det skal dog tages i betragtning, at dette pålægger visse begrænsninger på parametrene for p-træstrukturen.

Bemærk, at der udover cR-træet er dets variation clR-træ baseret på klyngemetoden, hvor en iterativ algoritme til løsning af "placeringsproblemet" bruges som centrum. Algoritmen har en kvadratisk beregningskompleksitet, men giver konstruktionen af ​​mere kompakte konvolutter af parallelepipeder i strukturens toppunkter.

Søg

At søge i et træ er ret trivielt, du skal bare tage højde for det faktum, at hvert punkt i rummet kan være dækket af flere hjørner.

Fjernelse

Denne algoritme [2] fjerner noget indtastning E fra R-træet. Algoritmen består af følgende trin:

  • Søg efter den node, der indeholder posten. Kald FindLeaf- søgefunktionen for at finde bladet L, der indeholder post E. Stop algoritmen, hvis posten ikke findes.
  • Sletning af en post. Slet post E fra ark L.
  • Opdater ændringer. Kald CondenseTree -funktionen for L-indgangen.
  • Kontrol af træets rod. Hvis træets rod ikke er en bladknude med kun én indgang tilbage, så gør denne indtastning til træets rod.

FindLeaf funktion

Lad T være roden af ​​træet, og lad E være den ønskede indgang.

  • Undertræsøgning. Hvis T ikke er en bladknude, så kontroller hver forekomst af en E-indgang i hver T-indgang i henhold til følgende betingelse: hvis indgangen E er inkluderet i rektanglet af en post i T, så kald FindLeaf- funktionen .
  • Søg efter en post i en bladknude. Hvis T er et blad, så find posten E i dette blad, og returner det, hvis det findes.

CondenseTree funktion

Lad post E blive slettet fra ark L. Derefter er det nødvendigt at fjerne den node, der har få poster tilbage (mindre end MinEntries) og flytte dens poster. Når du flytter op i træet, skal du om nødvendigt slette poster (efter samme kriterier). På vej til roden skal du genberegne rektanglerne, så de bliver så små som muligt. Algoritmen er beskrevet nedenfor. Denne funktion kan også implementeres ved hjælp af rekursion.

  • Initialisering. Lad N = L og Q være sættet af fjerntliggende noder, indledningsvis tomme.
  • Find upstream node. Hvis N er en rod, skal du gå til det sidste trin i algoritmen (indsætte poster igen). Ellers lad P være forælderen til node N.
  • Udelukkelse af små noder. Hvis node N har færre MinEntries-indgange, skal du fjerne N fra P og tilføje det til Q.
  • Genberegning af rektangler. Hvis N ikke er blevet fjernet, så genberegn dets rektangel, så det indeholder alle poster i N.
  • Bevægelse op i træet. Lad N = P. Gentag det andet trin med at finde den overordnede node.
  • Indsættelse af "forældreløse" poster. Du skal genindsætte poster fra sættet Q. Hvis posten i Q er en bladknude, så indsæt alle dens poster ved hjælp af Indsæt -algoritmen . Hvis Q ikke er en bladknude, så skal den indsættes, så alle dens bladknuder er på samme træniveau som træets bladknuder (ved egenskaben for R-træet, ifølge hvilken alle bladknuder gemmes på samme trædybdeniveau).

Diskussion af R-træer

Fordele

  • gemmer effektivt rumligt lokaliserede grupper af objekter
  • balanceret betyder i værste fald hurtigt opslag
  • indsættelse/sletning af et enkelt punkt kræver ikke væsentlig ombygning af træet (dynamisk indeks)

Ulemper

  • følsom over for rækkefølgen af ​​de tilføjede data
  • vertex afgrænsningskasser kan overlappe hinanden

Se også

  • Liste over datastrukturer (træer)

Noter

  1. ↑ The Priority R-Tree: A Practically Efficiency and Worst-Case Optimal R-Tree , SIGMOD. Arkiveret fra originalen den 6. marts 2021. Hentet 12. oktober 2011.
  2. ↑ Antonin Guttman. [ https://klevas.mif.vu.lt/~algis/DSA/guttman.pdf R-TREES. EN DYNAMISK INDEKSSTRUKTUR TIL RUMLIG SØGNING]  //  ACM. - 1984. Arkiveret 24. marts 2018.

Links