Viktbalanserat träd

För annan användning, se Optimalt binärt sökträd .

Inom datavetenskap är viktbalanserade binära träd ( WBT ) en typ av självbalanserande binära sökträd som kan användas för att implementera dynamiska uppsättningar , ordböcker (kartor) och sekvenser. Dessa träd introducerades av Nievergelt och Reingold på 1970-talet som träd med begränsad balans, eller BB[α]-träd . Deras vanligare namn beror på Knuth .

Ett välkänt exempel är en Huffman-kodning av en korpus .

Liksom andra självbalanserande träd lagrar WBT:er bokföringsinformation om balans i sina noder och utför rotationer för att återställa balansen när den störs av insättnings- eller raderingsoperationer. Specifikt lagrar varje nod storleken på underträdet som är rotat vid noden, och storlekarna på vänster och höger underträd hålls inom någon faktor av varandra. Till skillnad från balansinformationen i AVL-träd (med information om höjden på underträd) och röd-svarta träd (som lagrar en fiktiv "färg"-bit), är bokföringsinformationen i en WBT en faktiskt användbar egenskap för applikationer: antalet element i ett träd är lika med storleken på dess rot, och storleksinformationen är exakt den information som behövs för att implementera operationerna i ett ordningsstatistiskt träd, nämligen att få det n :e största elementet i en uppsättning eller bestämma ett elements index i sorterad ordning.

Viktbalanserade träd är populära i den funktionella programmeringsgemenskapen och används för att implementera uppsättningar och kartor i MIT Scheme, SLIB och implementeringar av Haskell .

Beskrivning

Ett viktbalanserat träd är ett binärt sökträd som lagrar storleken på underträden i noderna. Det vill säga, en nod har fält

• nyckel , av valfri beställd typ
• värde (valfritt, endast för mappningar)
• vänster , höger , pekare till nod
• storlek , av typen heltal.

Per definition är storleken på ett blad (vanligtvis representerad av en nollpekare ) noll. Storleken på en intern nod är summan av storleken på dess två barn plus ett: ( storlek[n] = storlek[n.vänster] + storlek[n.höger] + 1) . Baserat på storleken definierar man vikten till vikt[n] = storlek[n] + 1 .

Binära trädrotationer .

Operationer som modifierar trädet måste se till att vikten av de vänstra och högra underträden i varje nod förblir inom någon faktor α av varandra, med samma ombalanseringsoperationer som används i AVL-trädet : rotationer och dubbla rotationer. Formellt definieras nodbalans enligt följande:

En nod är α -viktsbalanserad om vikt[n.vänster] ≥ α·vikt[n] och vikt[n.höger] ≥ α·vikt[n] .

Här är α en numerisk parameter som ska bestämmas vid implementering av viktbalanserade träd. Större värden på α ger "mer balanserade" träd, men inte alla värden på α är lämpliga; Nievergelt och Reingold bevisade det

$\alpha <1-{\frac {\sqrt {2}}{2}}\approx 0,29289$

är en nödvändig förutsättning för att balanseringsalgoritmen ska fungera. Senare arbete visade en nedre gräns på 2 ⁄ 11 för α , även om den kan göras godtyckligt liten om en anpassad (och mer komplicerad) ombalanseringsalgoritm används.

Att tillämpa balansering korrekt garanterar att ett träd med n element kommer att ha höjd

$h\leq \log _{\frac {1}{1-\alpha }}n={\frac {\log _{2}n}{\log _{2}\left({\frac {1}{1-\alpha }}\right)}}=O(\log n )$

Antalet balanseringsoperationer som krävs i en sekvens av n insättningar och deletioner är linjärt i n , dvs balansering tar en konstant mängd omkostnader i en amortiserad mening.

Medan att bibehålla ett träd med den lägsta sökkostnaden kräver fyra typer av dubbla rotationer (LL, LR, RL, RR som i ett AVL-träd) i infogning/radering, om vi bara önskar logaritmisk prestanda, är LR och RL de enda rotationer som krävs i ett enda pass uppifrån och ner.

Set operationer och bulk operationer

Flera setoperationer har definierats på viktbalanserade träd: union , intersection och set difference . Sedan kan snabba bulkoperationer på infogningar eller borttagningar implementeras baserat på dessa inställda funktioner. Dessa uppsättningsoperationer är beroende av två hjälpoperationer, Split och Join . Med den nya verksamheten kan implementeringen av viktbalanserade träd bli effektivare och mer parallelliserbar.

• Join : Funktionen Join finns på två viktbalanserade träd t ₁ och t ₂ och en nyckel k och kommer att returnera ett träd som innehåller alla element i t 1 _, t ₂ samt k . Det kräver k är större än alla nycklar i t ₁ och mindre än alla nycklar i t ₂ . Om de två träden har den balanserade vikten, enkelt en ny nod med det vänstra underträdet t ₁ , roten k och det högra underträdet t ₂ . Antag att t ₁ har tyngre vikt än t ₂ (det andra fallet är symmetriskt). Join följer den högra ryggraden på t ₁ tills en nod c som är balanserad med t ₂ . Vid denna tidpunkt skapas en ny nod med vänster underordnat c , rot k och höger underordnat t _{2 för att ersätta c.} Den nya noden kan ogiltigförklara den viktbalanserade invarianten. Detta kan fixas med en enkel eller dubbel rotation förutsatt att $\alpha <1-{\frac {1}{\sqrt {2}}}$
• Dela : För att dela upp ett viktbalanserat träd i två mindre träd, de som är mindre än tangenten x och de som är större än tangenten x , ritar du först en bana från roten genom att infoga x i trädet. Efter denna infogning kommer alla värden mindre än x att hittas till vänster om banan, och alla värden större än x kommer att hittas till höger. Genom att tillämpa Join slås alla underträd på vänster sida samman nedifrån och upp med hjälp av tangenter på banan som mellannoder från botten till toppen för att bilda det vänstra trädet, och den högra delen är symmetrisk. För vissa applikationer Split också ett booleskt värde som anger om x visas i trädet. Kostnaden för Split är ${\displaystyle O(\log n)} ,$ ordning efter trädets höjd. Denna algoritm har faktiskt ingenting att göra med några speciella egenskaper hos ett viktbalanserat träd, och är därför generisk för andra balanseringssystem som AVL-träd .

Anslutningsalgoritmen är som följer:

 funktion  joinRightWB(TL  ,  k,  TR  ) (l, k', c) = exponera(TL  )  om  balans  (|T  L  |, |  TR  |)  return  Node(TL  ,  k,  TR  )  else  T' = joinRightWB(c, k, TR  )  (l', k', r') = exponera(T')  if  (balans(|l|,|T'|))  return  Node(l, k', T')  else if  (balans(|l|,|l'|) och balans(|l|+|l'|,|r'|)) returnera rotateLeft(Node(  l  , k', T'))  annat  returnera rotateLeft(Node(l, k', rotateRight(T'))  funktion  joinLeftWB(T  L  , k,  TR  ) /* symmetrisk till joinRightWB */  function  join(T  L  , k,  TR  )  if  (heavy(T  L  , T  R  )) return joinRightWB(TL  ,  k,  TR  )  if  (heavy(TR  ,  T  L  )) return joinLeftWB(TL  ,  k,  TR  ) Node(TL  ,  k,  TR  ) 

Här betyder balans $(x,y)$ två vikter $x$ och $y$ är balanserade. expose(v)=(l, k, r) betyder att extrahera en trädnod $v$ s vänstra underordnade $l$ , nyckeln till noden $k$ och det högra barnet $r$ . Node(l, k, r) betyder att skapa en nod av vänster underordnad $l$ , tangent $k$ och höger underordnad $r$ .

Den delade algoritmen är som följer:

 funktion  split(T, k)  if  (T = noll) return (noll, falskt, noll) (L, (m, c), R) = exponera(T)  om  (k = m) return (L, sant, R )  if  (k < m) (L', b, R') = split(L, k)  return  (L', b, join(R', m, R))  if  (k > m) (L', b, R') = split(R, k)  return  (join(L, m, L'), b, R)) 

Föreningen av två viktbalanserade träd t ₁ och t ₂ som representerar mängderna A och B , är ett viktbalanserat träd t som representerar A ∪ B . Följande rekursiva funktion beräknar denna union:

     funktion  union(t  1  , t  2  ):  om  t  1  = noll:  returnera  t  2  om  t  2  = noll:  returnera  t  1  t  <  , t  >  ← dela t  2  på t  1  .root  return  join(union(left(t)  1  ), t  <  ), t  1  .root, union(höger(t  1  ), t  >  )) 

Här antas Split returnera två träd: ett som håller tangenterna minus dess inmatningsnyckel, ett håller de större tangenterna. (Algorithmen är oförstörande , men en destruktiv version på plats finns också.)

Algoritmen för korsning eller skillnad är liknande, men kräver Join2- hjälparrutinen som är samma som Join men utan mittentangenten. Baserat på de nya funktionerna för union, korsning eller differens, kan antingen en nyckel eller flera nycklar infogas i eller raderas från det viktbalanserade trädet. Eftersom Split och Union kallar Join men inte hanterar balanseringskriterierna för viktbalanserade träd direkt, kallas en sådan implementering vanligtvis för de joinbaserade algoritmerna .

Komplexiteten för var och en av förening, skärningspunkt och skillnad är $O\left(m\log \left({n \over m}+1\right)\right)$ för två viktbalanserade träd i storlekarna $m$ och $n(\geq m)$ . Denna komplexitet är optimal när det gäller antalet jämförelser. Ännu viktigare, eftersom de rekursiva anropen till förening, skärningspunkt eller skillnad är oberoende av varandra, kan de exekveras parallellt med ett parallellt djup $O(\log m\log n)$ . När $m=1$ har den kopplingsbaserade implementeringen samma beräkningsriktade acykliska graf (DAG) som insättning och radering av ett element om roten av det större trädet används för att dela upp det mindre trädet.