Toppträd

Ett toppträd är en datastruktur baserad på ett binärt träd för orootade dynamiska träd som huvudsakligen används för olika vägrelaterade operationer. Det tillåter enkla dela-och-härska-algoritmer . Det har sedan dess utökats för att dynamiskt upprätthålla olika egenskaper hos ett träd som diameter, centrum och median.

Ett toppträd $\Re$ definieras för ett underliggande träd ${\mathcal {T}}$ och en uppsättning $\partial {T}$ av högst två hörn som kallas External Gränspunkten

En bild som visar ett toppträd byggt på ett underliggande träd (svarta noder) Ett träd uppdelat i kantkluster och hela toppträdet för det. Fyllda noder i toppträdet är vägkluster, medan små cirkelnoder är lövkluster. Den stora cirkelnoden är roten. Versaler betecknar kluster, icke versaler är noder.

Ordlista

Gränsnod

Se Boundary Vertex

Boundary Vertex

En vertex i ett anslutet underträd är ett Boundary Vertex om det är förbundet med en vertex utanför underträdet med en kant.

Yttre gränshörn

Upp till ett par hörn i det översta trädet $\Re$ kan kallas External Boundary Vertices, de kan ses som Boundary Vertices i klustret som representerar hela toppträdet.

Klunga

Ett kluster är ett sammankopplat underträd med högst två gränspunkt . Uppsättningen av Boundary Vertices för ett givet kluster ${\mathcal {C}}$ betecknas som $\partial {C}.$ Med varje kluster ${\mathcal {C}}$ kan användaren associera viss metainformation $I({\mathcal {C}}) ,$ och ge metoder för att underhålla den under de olika interna operationerna .

Path Cluster

Om $\pi ({\mathcal {C}})$ innehåller minst en kant så kallas ${\mathcal {C}}$ för ett Path Cluster .

Point Cluster

Se Leaf Cluster

Lövkluster

Om $\pi ({\mathcal {C}})$ inte innehåller någon kant, dvs ${\mathcal {C}}$ har bara en Boundary Vertex så har ${\ mathcal {C}}$ kallas en Leaf Cluster .

Kantkluster

Ett kluster som innehåller en enda kant kallas ett kantkluster .

Bladkantskluster

Ett blad i det ursprungliga klustret representeras av ett kluster med bara en enda gränspunkt och kallas ett bladkantkluster .

Path Edge Cluster

Kantkluster med två gränsnoder kallas Path Edge Cluster .

Intern nod

En nod i ${\mathcal {C}}$ \ $\partial {C}$ kallas en intern nod av ${\mathcal {C}}.$

Klusterväg

Vägen mellan Boundary Vertices för ${\mathcal {C}}$ kallas klusterbanan för ${\mathcal {C}}$ och den betecknas med $\pi ({\mathcal {C}}).$

Sammanslagbara kluster

Två kluster ${\mathcal {A}}$ och ${\mathcal {B}}$ är sammanslagbara om ${\mathcal {A}}\cap {\mathcal {B }}$ är en singleton-uppsättning (de har exakt en nod gemensam) och ${\mathcal {A}}\cup {\mathcal {B}}$ är ett kluster.

Introduktion

Toppträd används för att underhålla en dynamisk skog (uppsättning träd) under länk- och avverkningsoperationer.

Grundidén är att upprätthålla ett balanserat binärt träd $\Re$ med logaritmisk höjd i antalet noder i det ursprungliga trädet ${\mathcal {T}}$ (dvs i ${\mathcal {O}}(\log n)$ tid) ; det översta trädet representerar i huvudsak den rekursiva underuppdelningen av det ursprungliga trädet ${\mathcal {T}}$ i kluster .

I allmänhet kan trädet ${\mathcal {T}}$ ha vikt på sina kanter.

Det finns en en-till-en överensstämmelse med kanterna på det ursprungliga trädet ${\mathcal {T}}$ och lövnoderna i det översta trädet $\Re$ och varje inre nod av ${ \displaystyle \Re }$ representerar ett kluster som bildas på grund av föreningen av klustren som är dess underordnade.

Översta trädets datastruktur kan initieras i ${\mathcal {O}}(n)$ tid.

Därför är det översta trädet $\Re$ over ( ${\mathcal {T}},$$\partial {T}$ ) ett binärt träd så att

• Noderna för $\Re$ är kluster av ( ${\mathcal {T}},$${\displaystyle \partial {T}} )$ ;
• Bladen på $\Re$ är kanterna på ${\mathcal {T}};$
• Syskonkluster är grannar i den meningen att de skär varandra i en enda vertex, och då är deras moderkluster deras förening.
• Roten till $\Re$ är själva trädet ${\mathcal {T}}$ , med en uppsättning av högst två yttre gränspunkt.

Ett träd med en enda vertex har ett tomt toppträd, och ett med bara en kant är bara en enda nod.

Dessa träd är fritt utökade och tillåter användaren en mängd olika flexibilitet och produktivitet utan att gå in på detaljerna i datastrukturens interna funktion, något som också kallas Black Box .

Dynamiska operationer

Följande tre är de användartillåtna skogsuppdateringarna.

• Länk(v, w): Där $v$ och $w$ är hörn i olika träd ${\mathcal {T}}$ ₁ och ${\mathcal {T} }$ ₂ . Den returnerar ett enda toppträd som representerar $\Re$ _v $\cup$$\Re$ _w $\cup {(v,w)}$
• Cut(v, w) : Tar bort kanten ${(v,w)}$ från ett träd ${\mathcal {T}}$ med toppträdet $\ Re ,$ därigenom förvandlar den till två träd ${\mathcal {T}}$ _v och ${\mathcal {T}}$ _w och returnerar två toppträd $\Re$ _v och $\Re$ _w .
• Expose(S) : Anropas som en subrutin för att implementera de flesta frågorna i ett toppträd. $S$ innehåller högst 2 hörn. Den gör ursprungliga yttre hörn att vara normala hörn och gör hörn från ${\displaystyle S} till$ de nya yttre gränshörnen i det översta trädet. Om $S$ inte är tom returnerar det det nya rotklustret ${\mathcal {C}}$ med $\partial {C}=S.$ Expose({v,w}) misslyckas om hörnen kommer från olika träd.

Intern verksamhet

Skogsuppdateringarna utförs alla av en sekvens av högst ${\mathcal {O}}(\log n)$ Interna operationer, vars sekvens beräknas i ytterligare ${\mathcal {O}}(\log n)$ tid. Det kan hända att under en träduppdatering kan ett lövkluster ändras till ett bankluster och tvärtom. Uppdateringar av toppträdet görs uteslutande av dessa interna operationer.

I $I({\mathcal {C}})$ genom att anropa en användardefinierad funktion associerad med varje intern operation.

• Slå samman $({\mathcal {A}},{\mathcal {B}}){:}$ Här ${\mathcal {A}}$ och ${ \mathcal {B}}$ är sammanslagbara kluster , det returnerar ${\mathcal {C}}$ som det överordnade klustret för ${\mathcal {A}}$ och ${\mathcal {B}}$ och med gränspunkten som gränspunkten för ${\mathcal {A}}\cup {\mathcal {B}}.$ Beräknar $I({\mathcal {C}})$ med $I( {\mathcal {A}})$ och $I({\mathcal {B}}).$
• Split $({\mathcal {C}}){:}$ Här är ${\mathcal {C}}$ rotklustret ${\mathcal {A}}\cup {\mathcal {B}}.$ Den uppdaterar $I({\mathcal {A}})$ och $I ({\mathcal {B}})$ med $I({\mathcal {C}})$ och sedan tar det bort klustret ${\mathcal {C}}$ från ${ \displaystyle \Re }$ .

Split implementeras vanligtvis med metoden Clean $({\mathcal {C}})$ som anropar användarmetod för uppdateringar av $I({\mathcal {A}})$ och $I({\mathcal {B}})$ med $I({\mathcal {C}})$ och uppdaterar $I({\mathcal {C}})$ så att det är känt att det inte behövs någon väntande uppdatering i dess underordnade. Då förkastas ${\displaystyle {\mathcal {C}}} utan att anropa användardefinierade funktioner.$ Rengöring krävs ofta för frågor utan att dela upp . Om Split inte använder Clean-subrutinen och Clean krävs, kan dess effekt uppnås med overhead genom att kombinera Merge och Split .

De följande två funktionerna är analoga med de två ovanstående och används för baskluster.

• Skapa $(v,w){:}$ Skapar ett kluster ${\mathcal {C}}$ för kanten $(v,w).$ Sätter $\partial {C}=\partial$$(v,w).$$I({\mathcal {C}})$ beräknas från början.
• Eradicate $({\mathcal {C}}){:}$${\mathcal {C}}$ är kantklustret $(v,w).$ Användardefinierad funktion anropas för att bearbeta $I({\mathcal {C}})$ och än klustret ${\mathcal {C}}$ tas bort från det översta trädet.

Icke lokal sökning

Användaren kan definiera Välj $({\mathcal {C}}){:}$ operation som för ett rot (icke-blad)-kluster väljer ett av dess underordnade kluster. Blackboxen i det översta trädet tillhandahåller sökrutinen ${\displaystyle ({\mathcal {C}}){:}},$ som organiserar Välj- frågor och omorganisering av det översta trädet (med hjälp av de interna operationerna) så att den lokaliserar den enda kant i skärningspunkten mellan alla valda kluster. Ibland bör sökningen begränsas till en väg. Det finns en variant av icke-lokal sökning för sådana ändamål. Om det finns två yttre gränspunkter i rotklustret ${\mathcal {C}}$ , söks kanten endast på banan $\pi ({\mathcal {C}})$ . Det räcker att göra följande modifiering: Om endast ett av rotklustrets barn är sökvägskluster, väljs det som standard utan att anropa Choose -operationen.

Exempel på icke-lokal sökning

Att hitta i:te kanten på längre väg från $v$ till $w$ kan göras med ${\mathcal {C}}$ =Expose({v,w}) följt av Sök ( ${\mathcal {C}}$ ) med lämplig Välj . För att implementera Välj använder vi global variabel som representerar $v$ och global variabel som representerar $i.$ Välj väljer klustret ${\mathcal {A}}$ med $v\in \partial {A}$ om längden på $\ pi ({\mathcal {A}})$ är åtminstone $i$ . För att stödja operationen måste längden bibehållas i $I$ .

Liknande uppgift skulle kunna formuleras för graf med kanter med icke-enhetslängder. I så fall skulle avståndet kunna adressera en kant eller en vertex mellan två kanter. Vi skulle kunna definiera Välj så att kanten som leder till vertexet returneras i det senare fallet. Det kan finnas definierad uppdatering som ökar alla kantlängder längs en bana med en konstant. I ett sådant scenario görs dessa uppdateringar i konstant tid bara i rotklustret. Clean krävs för att distribuera den försenade uppdateringen till barnen. Rengöringen ska anropas innan Välj anropas . För att bibehålla längden i $I$ skulle i så fall behöva bibehålla enhetslängd i $I$ också.

Att hitta mitten av trädet som innehåller vertex $v$ kan göras genom att hitta antingen bicenterkant eller kant med mitten som en ändpunkt. Kanten kunde hittas av ${\mathcal {C}}$ =Expose({v}) följt av Search( ${\mathcal {C}}$ ) med lämplig Välj . Välj mellan barn ${\mathcal {A}},$${\mathcal {B}}$ med $a\in \partial {A} \cap \partial {B}$ barnet med högre maxdistans $(a)$ . För att stödja operationen bör det maximala avståndet i klusterunderträdet från en gränspunkt bibehållas i $I$ . Det kräver underhåll av klustrets väglängd också.

Intressanta resultat och applikationer

Ett antal intressanta applikationer som ursprungligen implementerades med andra metoder har enkelt implementerats med hjälp av det översta trädets gränssnitt. Några av dem inkluderar

• ([SLEATOR OCH TARJAN 1983]). Vi kan upprätthålla en dynamisk samling av viktade träd i ${\mathcal {O}}(\log n)$ tid per länk och klipp, vilket stöder frågor om den maximala kantvikten mellan två hörn i $O(\log n)$ tid.
  • Bevisöversikt: Det innebär att vid varje nod bibehålla den maximala vikten (max_wt) på dess klusterbana, om det är ett punktkluster så initieras max_wt( ${\displaystyle {\mathcal {C}}} som$$-\infty .$ När ett kluster är en förening av två kluster är det maxvärdet för de två sammanslagna klustren. Om vi ​​måste hitta max wt mellan $v$ och $w$ så gör vi ${\mathcal {C}}=$ Exponera $( v,w),$ och rapportera max_wt $({\mathcal {C}}).$
• ([SLEATOR OCH TARJAN 1983]). I scenariot för ovanstående applikation kan vi också lägga till en gemensam vikt $x$ till alla kanter på en given bana $v$ · · · $w$ i ${ \displaystyle {\mathcal {O}}(\log n)}$ tid.
  • Bevisöversikt: Vi introducerar en vikt som kallas extra( ${\mathcal {C}}$ ) som ska läggas till alla kanter i $\pi ({\mathcal {C}}).$ Som underhålls på lämpligt sätt ; split( ${\mathcal {C}}$ ) kräver att för varje sökvägsunderlag ${\mathcal {A}}$ av ${\mathcal {C}},$ vi set max_wt(A) := max_wt( ${\mathcal {A}}$ ) + extra( ${\mathcal {C}}$ ) och extra( ${\mathcal {A }}$ ) := extra( ${\mathcal {A}}$ ) + extra( ${\mathcal {C}}$ ). För ${\mathcal {C}}$ := join( ${\mathcal {A}},$${\mathcal {B}}$ ), sätter vi max_wt( ${\mathcal {C}}$ ) := max {max_wt( ${\mathcal {A}}$ ), max_wt( ${\mathcal {B}}$ )} och extra ( ${\mathcal {C}}$ ) := 0. Slutligen, för att hitta den maximala vikten på banan $v$ · · · $w,$ sätter vi ${\ displaystyle {\mathcal {C}}}$ := Exponera $(v,w)$ och returnera max_wt( ${\mathcal {C}}$ ).
• ([GOLDBERG ET AL. 1991]). Vi kan be om maxvikten i det underliggande trädet som innehåller en given vertex $v$ i ${\mathcal {O}}(\log n)$ tid.
  • Bevisöversikt: Detta kräver att ytterligare information bibehålls om den maximala vikten utanför klustervägkanten i ett kluster under operationerna Merge och Split.
• Avståndet mellan två hörn $v$ och $w$ kan hittas i ${\mathcal {O}}(\log n)$ tid som längd(Expose $(v,w)$ ).
  • Bevisöversikt: Vi kommer att behålla längdlängden ( ${\mathcal {C}}$ ) för klustervägen. Längden bibehålls som den maximala vikten förutom att om ${\mathcal {C}}$ skapas av en sammanfogning (Merge), är längd( ${\displaystyle {\mathcal {C}}} )$ summan av längder lagrade med dess vägbarn.
• Frågor om ett träds diameter och dess efterföljande underhåll tar ${\mathcal {O}}(\log n)$ tid.
• Centern och medianen kan underhållas under operationerna Länk (Sammanfoga) och Klipp (Dela) och efterfrågas av icke-lokal sökning i ${\mathcal {O}}(\log n)$ tid.

• Toppträd används i toppmoderna algoritmer för dynamisk tvåkantsuppkoppling . I det här problemet, på samma sätt som dynamisk anslutning , är grafen föremål för kantborttagningar och -infogningar, såväl som frågor som frågar om ett par hörn är tvåkantsanslutna eller om det finns en brygga som skiljer dem åt. Holm, de Lichtenberg och Thorup ger en deterministisk algoritm med amorterad uppdateringstid $O(\log ^{4}n)$ och $O(\log n/\log \log n)$ frågetid. Efterföljande arbete av Holm, Rotenberg och Thorup förbättrar detta till en amorterad uppdateringstid på $O(\log ^{2}n\log ^{2}\log n)$ , även genom att använda toppträd.

• Grafen kan underhållas så att man kan uppdatera kantuppsättningen och ställa frågor om vertex 2-anslutning. Amorterad komplexitet för uppdateringar är $O(\log ^{5}n)$ . Frågor skulle kunna implementeras ännu snabbare. Algoritmen är inte trivial, $I({\mathcal {C}})$ använder $\Theta (\log ^{2}n)$ mellanslag.

• Toppträd kan användas för att komprimera träd på ett sätt som aldrig är mycket sämre än DAG- komprimering, men kan vara exponentiellt bättre.

Genomförande

Toppträd har implementerats på en mängd olika sätt, några av dem inkluderar implementering med hjälp av en flernivåpartition (Topträd och dynamiska grafalgoritmer Jacob Holm och Kristian de Lichtenberg. Teknisk rapport), och även genom att använda Sleator-Tarjan st-träd (vanligtvis med amorterade tidsgränser), Frederickson's Topology Trees (med värsta fall tidsgränser) (Alstrup et al. Maintaining Information in Fully Dynamic Trees with Top Trees).

Amorterade implementeringar är enklare och med små multiplikativa faktorer i tidskomplexitet. Tvärtom tillåter de värsta tänkbara implementeringarna att påskynda frågor genom att stänga av onödiga informationsuppdateringar under sökningen (implementerat av persistenstekniker ). Efter att frågan har besvarats används det ursprungliga tillståndet för det översta trädet och frågeversionen kasseras.

Använda flernivåpartitionering

Varje partitionering av kluster i ett träd ${\mathcal {T}}$ kan representeras av ett klusterpartitionsträd CPT $({\mathcal {T}}),$ genom att ersätta varje kluster i trädet ${\mathcal {T}}$ av en kant. Om vi ​​använder en strategi P för att partitionera ${\mathcal {T}}$ så skulle CPT vara CPT _P ${\mathcal {T}}.$ Detta görs rekursivt tills endast en kant återstår.

Vi skulle märka att alla noder i motsvarande toppträd $\Re$ är unikt mappade i kanterna på denna flernivåpartition. Det kan finnas några kanter i flernivåpartitionen som inte motsvarar någon nod i det översta trädet, det är de kanter som endast representerar ett enda barn i nivån under det, dvs ett enkelt kluster. Endast de kanter som motsvarar sammansatta kluster motsvarar noder i toppträdet $\Re .$

En partitioneringsstrategi är viktig medan vi delar upp trädet ${\mathcal {T}}$ i kluster. Endast en noggrann strategi säkerställer att vi hamnar i en ${\mathcal {O}}(\log n)$ höjd Multilevel Partition (och därmed toppträdet).

• Antalet kanter i efterföljande nivåer bör minska med en konstant faktor.
• Om en lägre nivå ändras av en uppdatering bör vi kunna uppdatera den omedelbart ovanför den med som mest ett konstant antal infogningar och borttagningar.

Ovanstående partitioneringsstrategi säkerställer underhållet av det översta trädet i ${\mathcal {O}}(\log n)$ tid.

Se även

• Länka/klippa träd
• Euler turträd
• Dynamisk algoritm
• Dynamisk anslutning

• Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg och Mikkel Thorup , Upprätthålla information i helt dynamiska träd med toppträd , ACM Transactions on Algorithms (TALG), Vol. 1 (2005), 243–264, doi : 10.1145/1103963.1103966
• Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg och Mikkel Thorup , Poly-logaritmiska deterministiska helt dynamiska algoritmer för anslutning, minsta spännträd, 2-kant och biconnectivity, Journal of the ACM, Vol. 48 Issue 4 (juli 2001), 723–760, doi : 10.1145/502090.502095
•   Donald Knuth . The Art of Computer Programming : Fundamental Algorithms , tredje upplagan. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Avsnitt 2.3: Träd, s. 308–423.
•   Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest och Clifford Stein . Introduktion till algoritmer, andra upplagan. MIT Press och McGraw-Hill, 2001. ISBN 0-262-03293-7 . Avsnitt 10.4: Representerande rotade träd, s. 214–217. Kapitel 12–14 (Binära sökträd, rödsvarta träd, utökade datastrukturer), s. 253–320.

externa länkar

• Upprätthålla information i helt dynamiska träd med toppträd. Alstrup et al
• Självjusterande toppträd. Tarjan och Werneck, Proc. 16:e SoDA, 2005