Fingerträd

Inom datavetenskap är ett fingerträd en rent funktionell datastruktur som kan användas för att effektivt implementera andra funktionella datastrukturer. Ett fingerträd ger amorterad konstant tidsåtkomst till trädets "fingrar" (löven), vilket är där data lagras, och sammanlänkning och uppdelning av logaritmisk tid i storleken på den mindre biten. Den lagrar också i varje intern nod resultatet av att tillämpa någon associativ operation på dess avkomlingar. Dessa "sammanfattningsdata" lagrade i de interna noderna kan användas för att tillhandahålla funktionaliteten hos andra datastrukturer än träd.

Översikt

Fingerträd används som en enkel kö med amorterade O(1) put & get-operationer. Heltal 1 till 21 infogas till höger och extraheras från vänster. Fyrkantiga block representerar värden, "Siffra" (himmelsblå) kan ha 1-4 barn, "Node" (mörkblå) kan ha 2-3 barn, vit cirkel är för "Tom", röd nod representerar "Enkel"-värde och grön noder representerar "djupa" värden. Observera att för varje steg vi tar ner ryggraden, blir enstaka värden och siffror barn kapslade med en ny nivå av noder.

Ralf Hinze och Ross Paterson hävdar att ett fingerträd är en funktionell representation av beständiga sekvenser som kan komma åt ändarna i amorterad konstant tid. Sammanfogning och delning kan göras i logaritmisk tid i storleken på den mindre biten. Strukturen kan också göras till en datastruktur för allmänt ändamål genom att definiera den delade operationen i en allmän form, så att den kan fungera som en sekvens, prioritetskö, sökträd eller prioritetssökkö, bland andra varianter av abstrakta datatyper.

Ett finger är en punkt där man kan komma åt en del av en datastruktur; på imperativa språk kallas detta en pekare. I ett fingerträd är fingrarna strukturer som pekar mot ändarna av en sekvens, eller bladnoderna. Fingrarna läggs till i det ursprungliga trädet för att ge konstant åtkomst till fingrar. På bilderna nedan är fingrarna de linjer som sträcker sig ut från ryggraden till noderna.

Ett fingerträd är sammansatt av olika lager som kan identifieras av noderna längs dess ryggrad . Ryggraden på ett träd kan ses som stammen på samma sätt som träd har löv och en rot. Även om fingerträd ofta visas med ryggraden och grenar som kommer från sidorna, finns det faktiskt två noder på ryggraden på varje nivå som har parats ihop för att göra denna centrala ryggrad. Prefixet är till vänster om ryggraden, medan suffixet är till höger . Var och en av dessa noder har en länk till nästa nivå av ryggraden tills de når roten.

Visar ett 2-3 träd (överst) kan dras upp till ett fingerträd (nederst)

Den första nivån i trädet innehåller endast värden, trädets lövnoder, och är av djup 0. Den andra nivån är av djup 1. Den tredje är av djup 2 och så vidare. Ju närmare roten, desto djupare är underträden i det ursprungliga trädet (trädet innan det var ett fingerträd) pekar noderna på. På detta sätt går arbetet ner i trädet från löven till trädets rot, vilket är motsatsen till den typiska träddatastrukturen. För att få denna fina och ovanliga struktur måste vi se till att originalträdet har ett enhetligt djup. För att säkerställa att djupet är enhetligt, när du deklarerar nodobjektet, måste det parametriseras efter typen av barnet. Noderna på ryggraden av djup 1 och uppåt pekar på träd, och med denna parametrisering kan de representeras av de kapslade noderna.

Att förvandla ett träd till ett fingerträd

Vi börjar denna process med ett balanserat 2-3-träd . För att fingerträdet ska fungera måste alla bladnoder också vara i nivå.

Ett finger är "en struktur som ger effektiv tillgång till noder i ett träd nära en framstående plats." För att göra ett fingerträd måste vi sätta fingrar till höger och vänster ände av trädet och förvandla det som en dragkedja . Detta ger oss den konstanta amorterade tiden tillgång till ändarna av en sekvens.

För att transformera, börja med det balanserade 2-3-trädet.

Ta de interna noderna längst till vänster och höger i trädet och dra upp dem så att resten av trädet dinglar mellan dem som visas i bilden till höger.

Kombinerar ryggarna för att göra ett standardträd med 2-3 fingrar.

Detta kan beskrivas som:

   
    
     
          

   
      
       data  FingerTree  a  =  Tom  |  Singel  a  |  Djup  (  Siffra  a  )  (  FingerTree  (  Nod  a  ))  (  Siffra  a  )  data  Nod  a  =  Nod2  a  a  |  Nod3  a  a  a

Siffrorna i exemplen som visas är noderna med bokstäver. Varje lista delas med prefixet eller suffixet för varje nod på ryggraden. I ett transformerat 2-3-träd verkar det som om sifferlistorna på den översta nivån kan ha en längd på två eller tre med de lägre nivåerna bara en eller två. För att en viss tillämpning av fingerträd ska fungera så effektivt tillåter fingerträd mellan ett och fyra underträd på varje nivå.

Siffrorna i fingerträdet kan omvandlas till en lista så här:

                     typ  Siffra  a  =  En  a  |  Två  a  a  |  Tre  a  a  a  |  Fyra  a  a  a  a

Och så på bilden, den översta nivån har element av typ a , nästa har element av typ Nod a eftersom noden mellan ryggraden och bladen, och detta skulle fortsätta att betyda att den n: e nivån av trädet har element av typen $Node^{n}$ a , eller 2-3 träd med djup n. Detta betyder att en sekvens av n element representeras av ett träd med djup Θ(log n ). Ännu bättre, ett element d placerar från närmaste ände lagras på ett djup av Θ(log d) i trädet.

Minskningar

${\ börja{aligned}\mathrm {instans} &\ Reduce\ Node\ \mathrm {where} &&\\&reducer\ (\prec )\ (Node2\ a\ b)\ z&=&\ a\ \prec (b\ \ prec \ z)\\&reducer\ (\prec )\ (Node3\ a\ b\ c)\ z&=&\ a\ \prec (\ b\prec (c\ \prec \ z))\\\\&reducel \ (\succ )\ z\ (Node2\ b\ a)\ &=&\ (z\ \succ \ b)\ \succ \ a\\&reducel\ (\succ )\ z\ (Node3\ c\ b \ a)\ &=&\ ((z\ \succ \ c)\succ \ b)\succ \ a\\\end{aligned}}$ ${\begin{aligned}\mathrm {instans} &\ Reduce\ FingerTree\ \mathrm {where} &&\\&reducer\ ( \prec )\ (Tom)\ z\ &=&\ z\\&reducer\ (\prec )\ (Singel\ x)\ z&=&\ x\ \prec \ z\\&reducer\ (\prec )\ ( Deep\ pr\ m\ sf)\ z&=&\ pr\ \prec '\ (m\ \prec ''\ (sf\ \prec '\ z))\\&\ \ \ \ där\\&\ \ \ \ \ \ \ \ (\prec ')\ =reducer\ (\prec )\\&\ \ \ \ \ \ \ \ (\prec '')\ =reducer\ (reducer\ (\prec ))\\ \\&reducel\ (\succ )\ z\ (tom)\ &=&\ z\\&reducel\ (\succ )\ z\ (Singel\ \ x)\ &=&\ z\ \succ \ x\\ &reducel\ (\succ )\ z\ (Deep\ \ pr\ m\ sf)\ &=&\ ((z\ \succ '\ pr)\ \succ ''\ m)\ \succ '\ sf)\ \&\ \ \ \ där\\&\ \ \ \ \ \ \ \ (\succ ')\ =reducel\ (\succ )\\&\ \ \ \ \ \ \ \ (\succ '')\ = reducel\ (reducel\ (\succ ))\\\end{aligned}}$

Deque operationer

Fingerträd gör också effektiva deques . Oavsett om strukturen är beständig eller inte, tar all verksamhet Θ(1) avskriven tid. Analysen kan jämföras med Okasakis implicita deques, den enda skillnaden är att FingerTree-typen lagrar noder istället för par.

Ansökan

Fingerträd kan användas för att bygga andra träd. Till exempel kan en prioritetskö implementeras genom att märka de interna noderna med minimiprioriteten för dess barn i trädet, eller en indexerad lista/array kan implementeras med en märkning av noder efter antalet löv i deras barn. Andra applikationer är sekvenser med slumpmässig åtkomst, som beskrivs nedan, ordnade sekvenser och intervallträd .

Fingerträd kan ge amorterad O(1) skjutande, reversering, popning, O(log n) lägga till och dela; och kan anpassas för att vara indexerade eller ordnade sekvenser. Och som alla funktionella datastrukturer är det i sig beständigt ; det vill säga att äldre versioner av trädet alltid finns bevarade.

Slumpvis åtkomstsekvenser

Fingerträd kan effektivt implementera sekvenser med slumpmässig åtkomst. Detta bör stödja snabba positionsoperationer inklusive åtkomst till det n: te elementet och uppdelning av en sekvens vid en viss position. För att göra detta kommenterar vi fingerträdet med storlekar.

       
    

   
     0
            newtype  Storlek  =  Storlek  {  getSize  ::  N  }  härledande  (  Ekv  ,  Ord  )  instans  Monoid  Storlek  där  ∅  =  Storlek  Storlek  m  ⊕  Storlek  n  =  Storlek  (  m  +  n  )

N är för naturliga tal . Den nya typen behövs eftersom typen är bärare av olika monoider. En annan ny typ behövs fortfarande för elementen i sekvensen, som visas nedan.

        
        

     
      newtype  Elem  a  =  Elem  {  getElem  ::  a  }  newtype  Seq  a  =  Seq  (  FingerTree  Size  (  Elem  a  ))  instans  Uppmätt  (  Elem  a  )  Storlek  där  ||  Elem  ||  =  Storlek  1

Dessa kodrader visar att instans fungerar som ett basfall för att mäta storlekarna och elementen är av storlek ett. Användningen av newtype s orsakar inte körtidsstraff i Haskell eftersom storleks- och Elem -typerna i ett bibliotek skulle vara dolda för användaren med omslagsfunktioner.

Med dessa ändringar kan längden på en sekvens nu beräknas i konstant tid.

Första publiceringen

Finger trees publicerades först 1977 av Leonidas J. Guibas och förfinades med jämna mellanrum sedan (t.ex. en version med AVL-träd , icke-lata fingerträd, enklare 2-3 fingerträd som visas här, B-Trees och så vidare)

Genomföranden

Fingerträd har sedan använts i Haskell- kärnbiblioteken (i implementeringen av Data.Sequence ), och det finns en implementering i OCaml som härrörde från en beprövad korrekt Coq -implementering. Det finns även en verifierad implementering i Isabelle (proof assistant) från vilken program i Haskell och andra (funktionella) språk kan genereras. Fingerträd kan implementeras med eller utan lat utvärdering , men lathet möjliggör enklare implementeringar.

Se även

externa länkar

Träddatastrukturer
Sökträd ( dynamiska uppsättningar / associativa arrayer )	2–3 2–3–4 AA (a,b) AVL B B+ B* B ^x ( Optimal ) Binär sökning Dans HTree Intervall Beställningsstatistik ( Vänsterlutad ) Röd–svart Syndabock Splay T Treap DU ÄR Viktbalanserad
Högar	Binär Binom Brodal Fibonacci Vänsterman Parning Skev van Emde Boas Svag
Försöker	Ctrie C-trie (komprimerad ADT) Hash Radix Ändelse Ternär sökning X-snabb Y-snabb
Rumsliga datapartitioneringsträd	Boll BK BSP kartesiska Hilbert R k -d ( implicit k -d ) M Metrisk MVP Octree PH Prioritet R Quad R R+ R* Segmentet VP X
Andra träd	Omslag Exponentiell Fenwick Finger Fraktalträdindex Fusion Hash kalender iDistance K-ary Vänster-barn höger-syskon Länka/klippa Loggstrukturerad sammanslagning Merkle PQ Räckvidd SPQR Topp