Nivå förfader problem

Inom grafteori och teoretisk datavetenskap är nivåförfäderproblemet problemet med att förbearbeta ett givet rotat träd T till en datastruktur som kan bestämma förfadern till en given nod på ett givet avstånd från trädets rot .

Mer exakt, låt T vara ett rotat träd med n noder, och låt v vara en godtycklig nod av T . Nivåförfaderfrågan LA( v , d ) begär förfadern till nod v vid djupet d , där djupet för en nod v i ett träd är antalet kanter på den kortaste vägen från trädroten till nod v . Det är möjligt att lösa detta problem med konstant tid per fråga, efter en förbearbetningsalgoritm som tar O( n ) och som bygger en datastruktur som använder O( n ) lagringsutrymme.

Naiva metoder

Nivåförfader till ( v ,2) och vägen från roten r till noden v .

Det enklaste sättet att hitta en nivåförfader till en nod är att klättra upp i trädet mot trädets rot. På vägen till trädets rot kan varje förfader till en nod besökas och därför rapporteras. I det här fallet behöver trädet inte förbehandlas och tiden för att svara på en fråga är O( h ), där "h" är trädets höjd. Detta tillvägagångssätt är inte genomförbart i situationer där trädet kan ha stor höjd och ett stort antal frågor måste bearbetas.

Alternativt kan alla möjliga lösningar förberäknas och lagras i en tabell. I detta fall kan frågorna besvaras i O(1) men utrymmet och förbehandlingstiden är O( n ² ).

De enklaste frågorna som kan besvaras i konstant tid utan någon förbearbetning är LA( v , 0) och LA( v , depth( v )). I det förra fallet är svaret alltid trädets rot och i det senare fallet är svaret själva noden v . Vart och ett av dessa resultat tar O(1).

Genom att lagra vägarna genom trädet i en skev binär slumpmässig tillgångslista kan trädet fortfarande utökas nedåt ett O(1)-steg i taget, men nu kan sökningen fortsätta i O(log( p )), där " p " är avståndet från v till det begärda djupet. Detta tillvägagångssätt är genomförbart när trädet är särskilt brett eller kommer att utökas online och därför inte kan förbehandlas effektivt, eftersom lagrings- och åtkomsttiden helt bestäms av sökvägens längd.

Hopppekaralgoritm

Hopppekaralgoritmen förbearbetar ett träd i O( n log n ) tid och svarar på nivåförfrågningar i O(log n ) tid. Hopppekaralgoritmen associerar upp till log n pekare till varje vertex i trädet. Dessa pekare kallas hopppekare eftersom de hoppar upp i trädet mot trädets rot. För en given nod v i ett träd lagrar algoritmen en array med längd $l$ byglar där $\ell =\lfloor \log _{ 2}(\operatörsnamn {djup} (v))\rgolv$ . Det i: ^e elementet i denna array pekar på den 2: ^e förfadern till v . Att använda sådan datastruktur hjälper oss att hoppa halvvägs upp i trädet från en given nod. När algoritmen ombeds att bearbeta en fråga hoppar vi upprepade gånger upp i trädet med hjälp av dessa pekare. Antalet hopp kommer att vara högst log n och därför kan frågor besvaras i log n tid.

Stegealgoritm

Stegealgoritmen bygger på idén att förenkla ett träd till en samling stigar . Anledningen till detta är det faktum att sökvägar är lättare att fråga när det gäller nivåförfrågningar. Betrakta en väg P som består av n noder med rötter i en nod r. Vi kan lagra sökvägen i en array av storlek n som kallas Ladder och vi kan snabbt svara på en nivåförfaderfråga av LA(v, d) genom att returnera Ladder[d] om djup(v)≤d. Detta tar O( 1 ). Detta kommer dock bara att fungera om det givna trädet är en väg. Annars måste vi bryta ner det i banor. Detta görs i två steg: långvägsnedbrytning och förlängning av de långa vägarna till stegar.

Steg 1: långvägsnedbrytning

Detta är en rekursiv metod som bryter ner ett givet träd i banor. Detta skede börjar med att hitta den längsta rot-till-blad-vägen i trädet. Den tar sedan bort denna väg genom att bryta sina band från trädet vilket kommer att bryta upp resten av trädet i underträd och sedan bearbetar den rekursivt varje underträd. Varje gång en bana bryts ned skapas en array i samband med banan som innehåller elementen på banan från roten till bladet. Basfallet för denna rekursion är när trädet är en bana i vilket fall dess borttagning lämnar en tom graf. Varje vertex v har en unik stege som är den stege som innehåller den och vi kallar den "v:s stege". Men efter detta förbearbetningssteg kan frågorna inte besvaras snabbt. Faktum är att för att svara på en förfaderfråga på nivå måste algoritmen hoppa från en väg till en annan tills den når roten och det kan finnas Θ( √ n ) av sådana banor på en blad-till-rot-bana. Detta leder oss till en algoritm som kan förbehandla trädet i O( n ) tid och svarar på frågor i O( √ n ). För att nå den optimala frågetiden måste vi bearbeta resultaten i ett andra steg som beskrivs nedan.

Steg 2: förlängning av de långa stigarna till stegar

Det första steget av algoritmen bryter ner trädet i ett antal osammanhängande vägar. I det andra steget av algoritmen förlängs varje väg och därför kommer de resulterande vägarna inte att utesluta varandra. I det första steget av algoritmen är varje väg associerad med en array av storleken h' . Vi utökar denna väg genom att lägga till h' omedelbara förfäder överst på banan i samma array. Detta kommer att utöka varje array som högst två gånger sin ursprungliga storlek vilket kommer att resultera i 2n totalt antal noder i alla stegarna. Observera att antalet stegar inte ändras och varje nods stege förblir densamma. Även om en nod v kan listas i flera vägar nu, men dess stege är den som var associerad med v i det första steget av algoritmen. Dessa två steg kan vara processer i O( n ) men frågetiden är inte konstant ännu. Betrakta en förfaderfråga på nivå på en nod u med höjden h. nås en spets med en höjd på minst 2 timmar . Observera att alla noder har en höjd av minst 1 och därför når vi efter att ha gjort detta i gånger en nod med höjden minst 2 i ^och därför behöver vi göra detta högst log n gånger. Detta ger oss en frågetid på O(log n ).

Steg 3: kombinera de två tillvägagångssätten

Det visar sig att stegalgoritmen inte gör susen på egen hand. I själva verket kompletterar hopppekaralgoritmen och stegalgoritmen varandra. De två algoritmerna fungerar i motsatta riktningar: hopppekaralgoritmen gör exponentiellt minskande hopp och stegalgoritmen gör exponentiellt ökande hopp. En kombination av de två algoritmerna kan svara på frågor i O( 1 ) tid. En enda hopppekare tar vilken fråga som helst minst halvvägs upp i trädet, varefter om du klättrar uppför endast en stege kommer frågan att besvara frågan. Detta resulterar i O( n log n ) förbehandlingstid och O( 1 ) frågetid. Förbehandlingen kan reduceras ytterligare till O( n )-tid genom en tillämpning av metoden för fyra ryssar , där trädet reduceras till ett mindre träd med linjär förbearbetning, och en samling mycket små träd, som är tillräckligt små att en uttömmande uppräkning av alla träd och förbearbetningen av dessa träd fortfarande är O( n ) tid. Träd av storlek (log n )/4 räcker.

Berkman och Vishkins lösning

En annan lösning beror på Berkman och Vishkin. Denna lösning är baserad på Eulers turteknik för bearbetning av träd. Den huvudsakliga observationen är att LA( v , d ) är den första noden med djup d som visas i Euler-turen efter det sista uppträdandet av v . Således, genom att konstruera Euler-turen och tillhörande information om djup, reduceras problemet till en fråga på arrayer, kallad find smaller (FS). För en matris A och ett giltigt index i , returnerar FS( i , x ) det första indexet j > i så att A [ i ]< x (här använder vi x = d +1). En effektiv lösning på FS-problemet är svårt i allmänhet, men lättare för det speciella fallet som uppstår från Euler-turer; i detta fall skiljer sig intilliggande element med ±1. Denna idé ger O(1) frågetid, med en förbearbetningsalgoritm av komplexitet O( n log n ). Förbehandlingstiden förbättras till O( n ) genom en tillämpning av metoden för fyra ryssar .

Se även

• Områdesfråga (datastrukturer)
• Lägsta gemensamma anfader