Tangoträd
Ett tangoträd är en typ av binärt sökträd som föreslagits av Erik D. Demaine , Dion Harmon, John Iacono och Mihai Pătrașcu 2004. Det är uppkallat efter Buenos Aires , varav tangon är emblematisk.
Det är ett online binärt sökträd som uppnår ett konkurrensförhållande i förhållande till det offline optimala binära sökträdet , samtidigt som man bara använder ytterligare minnesbitar per nod. Detta förbättrades jämfört med det tidigare mest kända konkurrensförhållandet, som var .
Strukturera
Tangoträd fungerar genom att dela upp ett binärt sökträd i en uppsättning föredragna banor , som i sig lagras i hjälpträd (så att tangoträdet representeras som ett träd med träd).
Referensträd
För att konstruera ett tangoträd simulerar vi ett komplett binärt sökträd som kallas referensträdet , som helt enkelt är ett traditionellt binärt sökträd som innehåller alla element. Detta träd dyker aldrig upp i själva implementeringen, utan är den konceptuella grunden bakom följande delar av ett tangoträd.
I synnerhet är höjden på referensträdet ⌈log 2 ( n +1)⌉. Detta är lika med längden på den längsta vägen och därmed storleken på det största hjälpträdet. Genom att hålla hjälpträden någorlunda balanserade kan höjden på hjälpträden begränsas till O (log log n ). Detta är källan till algoritmens prestandagarantier.
Föredragna vägar
Först definierar vi för varje nod dess föredragna barn , som informellt är det senast besökta barnet genom en traditionell binär sökträdsuppslagning. Mer formellt, överväg ett underträd T , rotat på p , med barn l (vänster) och r (höger). Vi ställer in r som det föredragna underordnade av p om den senast öppnade noden i T finns i underträdet som är rotat till r , och l som det föredragna barnet annars. Observera att om den senast öppnade noden för T är p själv, så är l det föredragna barnet per definition.
En föredragen väg definieras genom att börja vid roten och följa de föredragna barnen tills du når en lövnod. Att ta bort noderna på denna väg delar upp resten av trädet i ett antal underträd, och vi återkommer på varje underträd (bildar en föredragen väg från dess rot, vilket delar upp underträdet i fler underträd).
Hjälpträd
För att representera en föredragen sökväg lagrar vi dess noder i ett balanserat binärt sökträd , närmare bestämt ett rött–svart träd . För varje icke-bladsnod n i en föredragen bana P , har den ett icke-föredraget underordnat c , som är roten till ett nytt hjälpträd. Vi fäster detta andra hjälpträds rot ( c ) till n i P , och länkar därmed ihop hjälpträden. Vi förstärker också hjälpträdet genom att vid varje nod lagra minsta och maximala djupet (djupet i referensträdet, det vill säga) för noderna i underträdet under den noden.
Algoritm
Sökande
För att söka efter ett element i tangoträdet simulerar vi helt enkelt sökning i referensträdet. Vi börjar med att söka den föredragna sökvägen kopplad till roten, som simuleras genom att söka hjälpträdet som motsvarar den önskade sökvägen. Om hjälpträdet inte innehåller det önskade elementet, avslutas sökningen på föräldern till roten av underträdet som innehåller det önskade elementet (början av en annan föredragen sökväg), så vi fortsätter helt enkelt genom att söka hjälpträdet efter den önskade sökvägen , och så vidare.
Uppdaterar
För att bibehålla strukturen hos tangoträdet (hjälpträd motsvarar föredragna vägar) måste vi göra en del uppdateringsarbete närhelst föredragna barn ändras som ett resultat av sökningar. När ett föredraget barn ändras, lossnar den övre delen av en föredragen väg från den nedre delen (som blir sin egen föredragna väg) och återansluts till en annan föredragen väg (som blir den nya nedre delen). För att göra detta effektivt kommer vi att definiera kapnings- och sammanfogningsoperationer på våra hjälpträd.
Ansluta sig
Vår join- operation kommer att kombinera två hjälpträd så länge de har egenskapen att den ena toppnoden (i referensträdet) är ett barn till den andras nedre nod (i huvudsak att motsvarande föredragna vägar kan sammanfogas). Detta kommer att fungera baserat på sammanlänkning av röd-svarta träd, som kombinerar två träd så länge de har egenskapen att alla element i det ena är mindre än alla element i det andra, och split , vilket gör det omvända. I referensträdet, notera att det finns två noder i den översta vägen så att en nod är i den nedre sökvägen om och endast om dess nyckel-värde är mellan dem. För att nu förena den nedre banan till den översta banan delar vi helt enkelt den övre banan mellan de två noderna, sammanfogar sedan de två resulterande hjälpträden på vardera sidan av den nedre banans hjälpträd, och vi har vårt sista, sammanfogade hjälpträd.
Skära
Vår klippoperation kommer att bryta en föredragen väg i två delar vid en given nod, en övre del och en bottendel. Mer formellt kommer det att dela upp ett hjälpträd i två hjälpträd, så att det ena innehåller alla noder på eller över ett visst djup i referensträdet, och det andra innehåller alla noder under det djupet. Som i join , notera att den övre delen har två noder som fäster den nedre delen. Således kan vi helt enkelt dela på var och en av dessa två noder för att dela upp vägen i tre delar, sedan sammanfoga de två yttre så att vi slutar med två delar, toppen och botten, som önskat.
Analys
För att begränsa konkurrensförhållandet för tangoträd måste vi hitta en lägre gräns för prestandan för det optimala offlineträdet som vi använder som riktmärke. När vi väl hittar en övre gräns för tangoträdets prestanda kan vi dela upp dem för att begränsa konkurrensförhållandet.
Interfolieringsbunden
För att hitta en nedre gräns för arbetet som utförs av det optimala offline-binära sökträdet använder vi återigen begreppet föredragna barn. När vi överväger en åtkomstsekvens (en sekvens av sökningar) håller vi reda på hur många gånger en referensträdnods föredragna underordnade växlar. Det totala antalet switchar (summat över alla noder) ger en asymptotisk nedre gräns för det arbete som utförs av en binär sökträdsalgoritm på den givna åtkomstsekvensen. Detta kallas interfoliens nedre gräns .
Tangoträd
För att koppla detta till tangoträd kommer vi att hitta en övre gräns för det arbete som utförs av tangoträdet för en given åtkomstsekvens. Vår övre gräns kommer att vara där k är antalet interfolierar.
Den totala kostnaden är uppdelad i två delar, sökning efter elementet och uppdatering av tangoträdets struktur för att bibehålla de rätta invarianterna (byta föredragna barn och omarrangera föredragna vägar).
Sökande
För att se att sökningen (ej uppdatering) passar in i denna gräns, notera helt enkelt att varje gång en extra trädsökning misslyckas och vi måste flytta till nästa extra träd, resulterar det i en föredragen underordnad byte (eftersom den överordnade föredragna sökvägen nu byter riktning för att gå med i den underordnade sökvägen). Eftersom alla hjälpträdsökningar misslyckas utom den sista (vi slutar naturligtvis när en sökning är framgångsrik), söker vi hjälpträd. Varje sökning tar , eftersom ett hjälpträds storlek begränsas av , referensträdets höjd.
Uppdaterar
Uppdateringskostnaden ryms också inom denna gräns, eftersom vi bara behöver utföra en klippning och en sammanfogning för varje besökt hjälpträd. En enda klipp- eller sammanfogningsoperation tar bara ett konstant antal sökningar, splittringar och sammanlänningar , som var och en tar logaritmisk tid i storleken på hjälpträdet, så vår uppdateringskostnad är .
Konkurrensförhållande
Tangoträd är -kompetitiva, eftersom arbetet som utförs av det optimala offline binära sökträdet är åtminstone linjärt i k (det totala antalet föredragna underordnade växlar), och arbetet som utförs av tangoträdet är som mest .
Se även
- ^ a b Demaine, ED; Harmon, D.; Iacono, J.; Pătraşcu, M. (2007). "Dynamisk optimalitet—nästan" (PDF) . SIAM Journal on Computing . 37 (1): 240. doi : 10.1137/S0097539705447347 .