R-träd (datastruktur)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 29 september 2015; kontroller kräver 23 redigeringar .
R-träd
Sorts Flerdimensionellt träd Binärt sökträd
Uppfinningens år 1984
Författare Antonin Guttman
Komplexitet i O-symboler
Medel Som värst
Sök O( log M n ) O( n )
 Mediafiler på Wikimedia Commons

R-tree ( Eng.  R-trees ) är en trädliknande datastruktur ( tree ), föreslagen 1984 av Antonin Guttman . Det liknar ett B-träd , men används för att komma åt rumslig data, det vill säga för att indexera flerdimensionell information , såsom geografiska data med tvådimensionella koordinater ( latitud och longitud ). En typisk fråga med R-träd kan vara: "Hitta alla museer inom 2 kilometer från min nuvarande plats."

Denna datastruktur delar upp ett flerdimensionellt utrymme i en uppsättning hierarkiskt kapslade och möjligen korsande rektanglar (för ett tvådimensionellt utrymme). I fallet med tredimensionellt eller flerdimensionellt utrymme kommer dessa att vara rektangulära parallellepipeder ( kuboider ) eller parallellotoper .

Algoritmerna för insättning och borttagning använder dessa begränsningsrutor för att säkerställa att "nära" objekt placeras på samma bladvertex. I synnerhet kommer det nya objektet att träffa bladets topp som behöver den minsta expansionen av sin begränsningsruta. Varje bladnodelement lagrar två datafält: ett sätt att identifiera de data som beskriver objektet (eller själva datan) och begränsningsrutan för detta objekt.

På liknande sätt använder sökalgoritmer ( t.ex. korsning, inkludering, grannskap) begränsningsrutor för att bestämma om de ska söka i en undernod. De flesta av hörnen berörs alltså aldrig under sökningen. Precis som med B-träd gör denna egenskap hos R-träd dem lämpliga för databaser , där hörn kan bytas ut till disk efter behov.

För att dela upp översvämmade hörn kan olika algoritmer användas, vilket leder till uppdelningen av R-träd i undertyper: kvadratiska och linjära.

Inledningsvis garanterade inte R-träd bra prestanda i värsta fall , även om de fungerade bra på riktiga data. Men 2004 publicerades en ny algoritm som bestämmer prioriterade R-träd . Det hävdas att denna algoritm är lika effektiv som de mest effektiva moderna metoderna, och samtidigt är optimal för värsta fall [1] .

R-trädstruktur

Varje hörn av R-trädet har ett variabelt antal element (inte mer än något förutbestämt maximum). Varje element i en icke-bladspunkt lagrar två datafält: ett sätt att identifiera den underordnade vertexen, och en begränsningsruta (kuboid) som omsluter alla element i den underordnade vertexen. Alla lagrade tuplar lagras på samma djupnivå, så trädet är perfekt balanserat. När du designar ett R-träd måste du ställa in några konstanter:

För att algoritmerna ska fungera korrekt måste villkoret MinEntries <= MaxEntries / 2 uppfyllas. Rotnoden kan ha från 2 till MaxEntries avkomlingar. Ofta väljs MinEntries = 2, då är samma villkor uppfyllda för roten som för resten av hörnen. Det är också ibland klokt att avsätta separata konstanter för antalet punkter i bladens hörn, eftersom du ofta kan göra fler av dem.

Algoritmer

Infoga

Konstruktionen av ett R-träd sker som regel genom att upprepade gånger anropa operationen att infoga ett element i trädet. Idén med infogning liknar infogning i ett B-träd : om att lägga till ett element till nästa vertex resulterar i ett spill, då delas vertexet. Nedan är den klassiska infogningsalgoritmen som beskrivs av Antonin Guttman .

Infoga funktion
  • Anropar ChooseLeaf för att välja bladet där elementet ska läggas till. Om insättningen görs kan trädet delas och klyvningen kan gå hela vägen till toppen. I det här fallet returnerar ChooseLeaf två SplitNodes att infoga i roten
  • Anropar funktionen AdjustBounds, som utökar rotens begränsningsruta till den punkt som ska infogas
  • Kontrollerar om ChooseLeaf returnerade SplitNodes som inte är noll, då växer trädet en nivå upp: från och med detta ögonblick är roten vertex vars barn är samma SplitNodes
Funktionen ChooseLeaf
  • om ingången är ett löv (rekursionsbas), då:
    • anropar DoInsert-funktionen, som direkt infogar elementet i trädet och returnerar två blad om en splittring inträffar
    • ändrar vertexets avgränsande rektangel för att matcha det infogade elementet
    • returnerar SplitNodes som returneras av DoInsert
  • om ingången är en icke-bladspunkt:
    • av alla barn väljs den vars gränser kräver minsta ökning för att infoga det givna elementet
    • anropar rekursivt ChooseLeaf på det valda barnet
    • fixar avgränsande rektanglar
    • om de splittedNodes från det rekursiva anropet är noll, lämnar vi funktionen, annars:
      • om NumEntries < MaxEntries, lägg sedan till en ny vertex till barnen, rengör SplitNodes
      • annars (när det inte finns någon plats att infoga), sammanfogar vi arrayen av barn med den nya vertexen och skickar den resulterande funktionen till LinearSplitNodes-funktionen eller en annan vertexdelningsfunktion, och returnerar från ChooseLeaf de SplitNodes som den använda splittningsfunktionen returnerade till oss .
Funktionen LinearSplit

Olika algoritmer kan användas för att separera hörn, detta är en av dem. Den har bara linjär komplexitet och är lätt att implementera, även om den inte ger den mest optimala separationen. Praxis visar dock att en sådan komplexitet vanligtvis är tillräcklig.

  • för varje koordinat för hela uppsättningen av delade hörn beräknas skillnaden mellan den maximala nedre gränsen för rektangeln vid denna koordinat och den minsta övre gränsen, sedan normaliseras detta värde av skillnaden mellan de maximala och minimala koordinaterna för punkterna i den ursprungliga uppsättningen för att bygga hela trädet
  • hitta maximum av denna normaliserade spridning över alla koordinater
  • ställ in som de första underordnade hörnen för de returnerade hörnen nod1 och nod2 de hörn från indatalistan där maximinivån nåddes, ta bort dem från indatalistan, justera gränserna för nod1 och nod2
  • sedan utförs infogning för de återstående hörnen:
    • om det finns så få hörn kvar i listan att om alla läggs till i en av utgående hörn, så kommer den att innehålla MinEntries-hörn, sedan läggs resten till den, återvänd från funktionen
    • om en av hörnen redan har maximalt med barn, så läggs resten till motsatsen, retur
    • för nästa hörn från listan jämförs den med hur mycket begränsningsrutan ska ökas när den infogas i var och en av de två framtida hörnen, där den är mindre, infogas den där
Den fysiska infogningsfunktionen DoInsert
  • om det finns fria platser vid spetsen, så sätts punkten in där
  • om det inte finns några platser, så sammanlänkas hörnets barn med den infogade punkten och LinearSplit-funktionen eller en annan delningsfunktion anropas, vilket returnerar två delade hörn, som vi returnerar från doInsert
Partitionering med klustringsalgoritmer

Ibland, istället för ett R-träd, används det så kallade cR-trädet (c står för clustered ). Grundidén är att klustringsalgoritmer som k-medel används för att separera hörn eller punkter . Komplexiteten hos k-medel är också linjär, men i de flesta fall ger den ett bättre resultat än den linjära Guttman-separationsalgoritmen, i motsats till vilken den inte bara minimerar den totala arean av lådornas kuvert, utan också avståndet mellan dem och överlappningsområdet. För punktklustring används det valda måttet för det ursprungliga utrymmet; för vertexklustring kan du använda avståndet mellan mitten av deras envelopper av parallellepipederna eller det maximala avståndet mellan dem.

Klustringsalgoritmer tar inte hänsyn till det faktum att antalet avkomlingar till en vertex begränsas uppifrån och under av algoritmens konstanter. Om klusterdelningen ger ett oacceptabelt resultat kan du använda den klassiska algoritmen för denna uppsättning, eftersom detta inte händer ofta i praktiken.

En intressant idé är att använda klustring i flera kluster, där flera kan vara fler än två. Det bör dock beaktas att detta medför vissa begränsningar för parametrarna för p-trädstrukturen.

Observera att förutom cR-trädet finns dess variation clR-träd baserat på klustringsmetoden, där en iterativ algoritm för att lösa "placeringsproblemet" används som centrum. Algoritmen har en kvadratisk beräkningskomplexitet, men tillhandahåller konstruktionen av mer kompakta envelopper av parallellepipeder i strukturvertexposterna.

Sök

Att söka i ett träd är ganska trivialt, du behöver bara ta hänsyn till det faktum att varje punkt i rymden kan täckas av flera hörn.

Borttagning

Denna algoritm [2] tar bort någon post E från R-trädet. Algoritmen består av följande steg:

  • Sök efter noden som innehåller posten. Anrop FindLeaf- sökfunktionen för att hitta bladet L som innehåller post E. Stoppa algoritmen om posten inte hittas.
  • Ta bort en post. Ta bort post E från blad L.
  • Uppdatera ändringar. Anropa CondenseTree- funktionen för L-posten.
  • Kontrollera trädets rot. Om roten på trädet inte är en lövnod med bara en post kvar, gör den inmatningen till trädets rot.

FindLeaf-funktion

Låt T vara roten till trädet och låt E vara den önskade posten.

  • Underträdsökning. Om T inte är en bladnod, kontrollera då varje förekomst av en E-post i varje post av T enligt följande villkor: om posten E ingår i rektangeln för en post i T, anropa FindLeaf- funktionen .
  • Sök efter en post i en lövnod. Om T är ett löv, leta reda på posten E i det här bladet, och om det hittas, returnera det.

CondenseTree funktion

Låt post E raderas från blad L. Sedan är det nödvändigt att eliminera noden som har få poster kvar (mindre än MinEntries) och flytta dess poster. När du flyttar upp i trädet, om nödvändigt, radera poster (med samma kriterier). På vägen till roten, räkna om rektanglarna, gör dem så små som möjligt. Algoritmen beskrivs nedan. Denna funktion kan också implementeras med hjälp av rekursion.

  • Initialisering. Låt N = L och Q vara uppsättningen av avlägsna noder, initialt tomma.
  • Hitta uppströms nod. Om N är en rot, gå sedan till det sista steget i algoritmen (infoga poster igen). Låt annars P vara föräldern till nod N.
  • Uteslutning av små noder. Om nod N har färre MinEntries-poster, ta sedan bort N från P och lägg till det i Q.
  • Omräkning av rektanglar. Om N inte har tagits bort, räkna om dess rektangel så att den innehåller alla poster i N.
  • Rörelse upp i trädet. Låt N = P. Upprepa det andra steget för att hitta den överordnade noden.
  • Infoga "föräldralösa" poster. Du måste infoga poster från uppsättningen Q igen. Om posten i Q är en bladnod, infoga alla dess poster med hjälp av Insert- algoritmen . Om Q inte är en lövnod, måste den infogas så att alla dess lövnoder är på samma trädnivå som trädets lövnoder (genom egenskapen för R-trädet, enligt vilken alla lövnoder lagras på samma träddjupsnivå).

Diskussion om R-träd

Fördelar

  • effektivt lagra rumsligt lokaliserade grupper av objekt
  • balanserad betyder snabb uppslag i värsta fall
  • att infoga/ta bort en enskild punkt kräver ingen betydande ombyggnad av trädet (dynamiskt index)

Nackdelar

  • känslig för ordningen på de tillagda uppgifterna
  • vertex begränsningsrutor kan överlappa varandra

Se även

  • Lista över datastrukturer (träd)

Anteckningar

  1. ↑ Det prioriterade R-trädet: Ett praktiskt taget effektivt och värsta fallet optimalt R-träd , SIGMOD. Arkiverad från originalet den 6 mars 2021. Hämtad 12 oktober 2011.
  2. ↑ Antonin Guttman. [ https://klevas.mif.vu.lt/~algis/DSA/guttman.pdf R-TRÄD. EN DYNAMISK INDEXSTRUKTUR FÖR RUMSLIG SÖKNING]  //  ACM. - 1984. Arkiverad 24 mars 2018.

Länkar