Syndbock träd

Syndbock träd
Typ	träd
Uppfunnet	1989
Uppfunnet av	Arne Andersson, Igal Galperin, Ronald L. Rivest
Komplexiteter i stor O-notation
Rymdkomplexitet Plats $O(n)$ Tidskomplexitet Fungera Amorteras Värsta fall Sök $O(\log n)$ $O(\log n)$ Föra in $O(\log n)$ $O(n)$ Radera $O(\log n)$ $O(n)$

Inom datavetenskap är ett syndabocksträd ett självbalanserande binärt sökträd $) {\displaystyle { \color {Blå}O(\log n)}}$ uppfunnit av Arne Andersson 1989 och igen av Igal Galperin och Ronald L. Rivest 1993. Det ger värsta tänkbara uppslagstid (med $n$ som antalet poster) och $O(\log n)$ amorterad infogning och radering tid.

Till skillnad från de flesta andra självbalanserande binära sökträd som också ger värsta fallet $O(\log n)$ uppslagstid, har syndabocksträd inga extra per-nodminne i jämförelse med ett vanligt binärt sökträd : förutom nyckel och värde lagrar en nod endast två pekare till undernoderna. Detta gör syndabocksträd lättare att implementera och, på grund av datastrukturjustering , kan det minska nodoverhead med upp till en tredjedel.

Istället för de små inkrementella ombalanseringsoperationerna som används av de flesta balanserade trädalgoritmer, väljer syndabocksträd sällan men dyrt en "syndabock" och bygger om underträdet som är rotat vid syndabocken till ett fullständigt binärt träd. Således har syndabocksträd $O(n)$ uppdateringsprestanda i värsta fall.

Teori

Ett binärt sökträd sägs vara viktbalanserat om hälften av noderna är till vänster om roten och hälften till höger. En α-viktsbalanserad nod definieras som att den uppfyller ett avslappnad viktbalanskriterium:

storlek(vänster) ≤ α*storlek(nod) storlek(höger) ≤ α*storlek(nod)

Där storlek kan definieras rekursivt som:

    
         0
    
        
 funktionsstorlek  (nod)  är  om  nod = noll  ,  returnera  annars  returstorlek  (nod->vänster) + storlek(nod->höger) + 1  slut om  slutfunktion 

Även ett degenererat träd (länkad lista) uppfyller detta villkor om α=1, medan ett α=0.5 bara skulle matcha nästan kompletta binära träd .

Ett binärt sökträd som är α-viktsbalanserat måste också vara α-höjdbalanserat , dvs.

 höjd(träd) ≤ golv(stock  1/α  (storlek(träd))) 

Genom kontraposition är ett träd som inte är α-höjdbalanserat inte α-viktbalanserat.

Syndbocksträd är inte garanterade att hålla α-viktsbalansen hela tiden, men är alltid löst α-höjdbalanserade i det

 höjd(syndabocksträd) ≤ golv(stock  1/α  (storlek(träd))) + 1. 

Brott mot detta höjdbalansvillkor kan upptäckas vid insättningstillfället och innebär att ett brott mot viktbalansvillkoret måste föreligga.

Detta gör att syndabocksträd liknar rödsvarta träd genom att de båda har restriktioner för sin höjd. De skiljer sig dock mycket åt i deras implementeringar för att avgöra var rotationerna (eller i fallet med syndabocksträd, ombalanseringar) äger rum. Medan röd-svarta träd lagrar ytterligare "färg"-information i varje nod för att bestämma platsen, hittar syndabocksträd en syndabock som inte är α-viktbalanserad att utföra ombalanseringen på. Detta är löst likt AVL-träd , genom att de faktiska rotationerna beror på "balanser" av noder, men sättet att bestämma balansen skiljer sig mycket åt. Eftersom AVL-träd kontrollerar balansvärdet vid varje infogning/borttagning, lagras det vanligtvis i varje nod; syndabocksträd kan bara beräkna det efter behov, vilket bara är när en syndabock behöver hittas.

Till skillnad från de flesta andra självbalanserande sökträd är syndabocksträd helt flexibla när det gäller deras balansering. De stöder vilket α som helst så att 0,5 < α < 1. Ett högt α-värde resulterar i färre balanser, vilket gör insättningen snabbare men uppslagningar och raderingar långsammare, och vice versa för ett lågt α. I praktiska tillämpningar kan därför ett α väljas beroende på hur ofta dessa åtgärder ska utföras.

Operationer

Slå upp

Uppslagningen ändras inte från ett standard binärt sökträd och har en värsta tid på $O(\log n)$ . Detta är i motsats till splayträd som har en värsta tid på $O(n)$ . Den reducerade nodminnesoverheaden jämfört med andra självbalanserande binära sökträd kan ytterligare förbättra referenslokalitet och cachning.

Införande

Insättning implementeras med samma grundläggande idéer som ett obalanserat binärt sökträd , dock med några betydande ändringar.

När man hittar insättningspunkten måste även djupet på den nya noden registreras. Detta implementeras via en enkel räknare som inkrementeras under varje iteration av uppslagningen, vilket effektivt räknar antalet kanter mellan roten och den infogade noden. Om denna nod bryter mot egenskapen α-höjdbalans (definierad ovan), krävs en ombalansering.

För att återbalansera genomgår ett helt underträd rotat i en syndabock en balanseringsoperation. Syndabocken definieras som en förfader till den infogade noden som inte är α-viktbalanserad. Det kommer alltid att finnas minst en sådan förfader. Ombalansering av någon av dem kommer att återställa den α-höjdbalanserade egenskapen.

Ett sätt att hitta en syndabock är att klättra från den nya noden tillbaka upp till roten och välja den första noden som inte är α-viktbalanserad.

Att klättra tillbaka upp till roten kräver $O(\log n)$ lagringsutrymme, vanligtvis tilldelat på stacken, eller överordnade pekare. Detta kan faktiskt undvikas genom att peka varje barn på sin förälder när du går ner och reparera på promenaden tillbaka upp.

För att avgöra om en potentiell nod är en livskraftig syndabock måste vi kontrollera dess a-viktsbalanserade egenskap. För att göra detta kan vi gå tillbaka till definitionen:

storlek(vänster) ≤ α*storlek(nod) storlek(höger) ≤ α*storlek(nod)

Men en stor optimering kan göras genom att inse att vi redan känner till två av de tre storlekarna, vilket bara lämnar den tredje att beräkna.

Betrakta följande exempel för att visa detta. Om vi ​​antar att vi klättrar tillbaka upp till roten:

storlek(förälder) = storlek(nod) + storlek(syskon) + 1

Men som:

storlek (insatt nod) = 1.

Fallet trivialiseras till:

storlek[x+1] = storlek[x] + storlek(syskon) + 1

Där x = denna nod, x + 1 = förälder och storlek(syskon) är det enda funktionsanrop som faktiskt krävs.

När syndabocken har hittats byggs underträdet som är rotat vid syndabocken om helt för att vara perfekt balanserat. Detta kan göras i ${\displaystyle O(n)}-$ tid genom att korsa underträdets noder för att hitta deras värden i sorterad ordning och rekursivt välja medianen som roten till underträdet.

Eftersom ombalanseringsoperationer tar ${\displaystyle O(n)}-$ tid (beroende på antalet noder i underträdet), har insättning en prestanda i värsta fall av $O(n)$ tid . Men eftersom dessa värsta scenarier är utspridda tar insättningen $O(\log n)$ amorterad tid.

Skiss av bevis för kostnad för införande

Definiera obalansen för en nod v som det absoluta värdet av skillnaden i storlek mellan dess vänstra nod och höger nod minus 1, eller 0, beroende på vilket som är störst. Med andra ord:

$I(v)=\operatörsnamn {max} (|\operatörsnamn {vänster} (v)-\ operatornamn {höger} (v)|-1,0)$

Omedelbart efter återuppbyggnad av ett underträd med rötter i v , I( v ) = 0.

Lemma: Omedelbart före återuppbyggnaden av underträdet rotat vid v , $I(v)\in \Omega (|v|)$ ( $\Omega$ är Big Omega notation .)

Bevis på lemma:

Låt $v_{0}$ vara roten till ett underträd direkt efter ombyggnaden. $h(v_{0})=\log(|v_{0}|+1)$ . Om det finns $\Omega (|v_{0}|)$ degenererade infogningar (det vill säga där varje infod nod ökar höjden med 1), då $I(v)\in \Omega (|v_{0}|)$ , $h(v)=h(v_ {0})+\Omega (|v_{0}|)$ och $\log(|v|)\leq \log (|v_{0}|+1)+1$ .

Eftersom $I(v)\in \Omega (|v|)$ före ombyggnaden, fanns det $\Omega (|v|)$ insättningar i underträdet med rötter i $v$ som inte resulterade i ombyggnad. Var och en av dessa infogningar kan utföras i $O(\log n)$ tid. Den sista infogningen som orsakar ombyggnadskostnader $O(|v|)$ . Med hjälp av aggregerad analys blir det tydligt att den amorterade kostnaden för en infogning är $O(\log n)$ :

${\Omega (|v|)O(\log n)+ O(|v|) \över \Omega (|v|)}=O(\log n)$

Radering

Syndbocksträd är ovanliga eftersom radering är lättare än insättning. För att möjliggöra radering måste syndabocksträd lagra ett extra värde med träddatastrukturen. Denna egenskap, som vi kommer att kalla MaxNodeCount, representerar helt enkelt det högsta uppnådda NodeCount. Den är inställd på NodeCount närhelst hela trädet balanseras om, och efter infogning är satt till max(MaxNodeCount, NodeCount).

För att utföra en radering tar vi helt enkelt bort noden som du skulle göra i ett enkelt binärt sökträd, men om

NodeCount ≤ α*MaxNodeCount

sedan balanserar vi om hela trädet om roten, och kommer ihåg att ställa in MaxNodeCount till NodeCount.

Detta ger radering en prestanda i värsta fall av ${\displaystyle O(n)}-$ tid, medan den amorterade tiden är $O(\log n)$ .

Skiss av bevis för kostnad för radering

Anta att syndabocksträdet har $n$ element och just har byggts om (med andra ord, det är ett komplett binärt träd). Som mest $n/2-1$ raderingar kan utföras innan trädet måste byggas om. Var och en av dessa raderingar tar $O(\log n)$ tid (den tid det tar att söka efter elementet och flagga det som borttaget). Raderingen $n/2$ gör att trädet byggs om och tar $O(\log n)+O(n)$ (eller bara $O(n)$ ) tid. Genom att använda aggregerad analys blir det tydligt att den amorterade kostnaden för en radering är $O(\log n)$ :

${\sum _ {1}^{n/2}O(\log n)+O(n) \över n/2}={{n \over 2}O(\log n)+O(n) \över n/2 }=O(\log n)\$

Etymologi

Namnet Syndbocksträd "[...] är baserat på den vanliga visdomen att när något går fel, är det första som folk tenderar att göra att hitta någon att skylla på (syndabocken)." I Bibeln är en syndabock ett djur som rituellt belastas med andras synder och sedan drivs bort.

Se även

• Splay träd
• Träd
• Trädrotation
• AVL-träd
• B-träd
• T-träd

externa länkar

• Galpern, Igal (september 1996). Om att konsultera en uppsättning experter och söka (PDF) (doktorsavhandling). MIT .
• Morin, Pat. "Kapitel 8 - Syndbocksträd" . Öppna datastrukturer (i pseudokod) (0,1G β ed.) . Hämtad 2017-09-16 .