Treap

Treap
Typ	Randomiserat binärt sökträd
Tidskomplexitet i stor O-notation
Algoritm Genomsnitt Värsta fall Plats O ( n ) O ( n ) Sök O (log n ) O ( n ) Föra in O (log n ) O ( n ) Radera O (log n ) O ( n )

Inom datavetenskap är treapen och det randomiserade binära sökträdet två närbesläktade former av binära sökträddatastrukturer som upprätthåller en dynamisk uppsättning ordnade nycklar och tillåter binära sökningar bland nycklarna. Efter valfri sekvens av insättningar och raderingar av nycklar är formen på trädet en slumpvariabel med samma sannolikhetsfördelning som ett slumpmässigt binärt träd; i synnerhet, med hög sannolikhet är dess höjd proportionell mot logaritmen för antalet nycklar, så att varje sökning, infogning eller raderingsoperation tar logaritmisk tid att utföra.

Beskrivning

En treap med alfabetisk nyckel och numerisk maxhögordning

Treapen beskrevs första gången av Raimund Seidel och Cecilia R. Aragon 1989; dess namn är en portmanteau av träd och hög . Det är ett kartesiskt träd där varje tangent ges en (slumpmässigt vald) numerisk prioritet. Som med vilket binärt sökträd som helst, inordnade genomgångsordning densamma som nycklarnas sorterade ordning. Trädets struktur bestäms av kravet att det ska vara högordnat: det vill säga att prioritetsnumret för alla icke-bladsnoder måste vara större än eller lika med prioritet för dess barn. Således, som med kartesiska träd mer generellt, är rotnoden den maximalt prioriterade noden, och dess vänstra och högra underträd bildas på samma sätt från undersekvenserna av den sorterade ordningen till vänster och höger om den noden.

Ett likvärdigt sätt att beskriva treapen är att den kan bildas genom att sätta in noderna med högsta prioritet-först i ett binärt sökträd utan att göra någon ombalansering. Därför, om prioriteringarna är oberoende slumptal (från en fördelning över ett tillräckligt stort utrymme av möjliga prioriteringar för att säkerställa att två noder är mycket osannolikt att ha samma prioritet) så har formen på en treap samma sannolikhetsfördelning som formen på ett slumpmässigt binärt sökträd , ett sökträd som bildas genom att infoga noderna utan ombalansering i en slumpmässigt vald infogningsordning. Eftersom slumpmässiga binära sökträd är kända för att ha logaritmisk höjd med hög sannolikhet, gäller detsamma för treaps. Detta speglar det binära sökträdargumentet att quicksort körs i förväntad ${\displaystyle O(n\log n)}-$ tid. Om binära sökträd är lösningar på den dynamiska problemversionen av sortering, så motsvarar Treaps specifikt dynamisk quicksort där prioriteter styr pivotval.

Aragon och Seidel föreslår också att tilldela högre prioriteter till ofta åtkomliga noder, till exempel genom en process som vid varje åtkomst väljer ett slumpmässigt nummer och ersätter nodens prioritet med det numret om det är högre än föregående prioritet. Denna modifiering skulle få trädet att förlora sin slumpmässiga form; istället är det mer sannolikt att noder som används ofta ligger nära trädets rot, vilket gör att sökningar efter dem går snabbare.

Naor och Nissim beskriver en applikation för att upprätthålla auktorisationscertifikat i kryptosystem med offentliga nyckel .

Operationer

Grundläggande operationer

Treaps stöder följande grundläggande operationer:

• För att söka efter ett givet nyckelvärde, tillämpa en standard binär sökalgoritm i ett binärt sökträd, och ignorera prioriteringarna.
• För att infoga en ny nyckel x i treapen, generera en slumpmässig prioritet y för x . Binär sökning efter x i trädet, och skapa en ny nod vid bladpositionen där den binära sökningen bestämmer att en nod för x ska finnas. Sedan, så länge som x inte är roten till trädet och har ett högre prioritetsnummer än dess förälder z , utför sedan en trädrotation som vänder föräldra-barn-relationen mellan x och z .
• För att ta bort en nod x från treapen, om x är ett löv på trädet, ta helt enkelt bort det. Om x har ett enda underordnat z , ta bort x från trädet och gör att z är barnet till föräldern till x (eller gör z till roten av trädet om x inte hade någon förälder). Slutligen, om x har två barn, byt ut dess position i trädet med positionen för dess omedelbara efterföljare z i sorterad ordning, vilket resulterar i ett av de tidigare fallen. I det här sista fallet kan bytet bryta mot heap-order-egenskapen för z , så ytterligare rotationer kan behöva utföras för att återställa denna egenskap.

Bygga en treap

• För att bygga en treap kan vi helt enkelt infoga n värden i treapen där varje tar $O(\log n)$ tid. Därför kan en treap byggas i $O(n\log n)$ tid från en lista värden.

Bulkverksamhet

Förutom operationerna för insättning, radering och uppslagning av ett element har flera snabba "bulk"-operationer definierats på treaps: union , intersection och set difference . Dessa är beroende av två hjälpoperationer, split och join .

• För att dela upp en treap i två mindre treaps, de som är mindre än key x och de som är större än key x , infogar du x i treapen med maximal prioritet – större än prioriteten för någon nod i treapen. Efter denna infogning x att vara rotnoden för treapen, alla värden mindre än x kommer att hittas i den vänstra subtreapen och alla värden större än x kommer att hittas i den högra subtreapen. Detta kostar lika mycket som en enda insättning i treapen.
• Genom att sammanfoga två treaps som är produkten av en tidigare split, kan man säkert anta att det största värdet i den första treapen är mindre än det minsta värdet i den andra treapen. Skapa en ny nod med värdet x , så att x är större än detta maxvärde i den första treppen och mindre än min-värdet i den andra treapen, tilldela den minsta prioritet, ställ sedan in dess vänstra underordnade till den första högen och dess rätta barn till andra högen. Rotera efter behov för att fixa högordningen. Efter det kommer det att vara en lövnod och kan enkelt tas bort. Resultatet är en treap sammanslagen från de två ursprungliga treaps. Detta är i praktiken att "ångra" en split och kostar lika mycket. Mer generellt kan join-operationen fungera på två treaps och en nyckel med godtycklig prioritet (dvs inte nödvändigt att vara den högsta).

Gå med utförd på treaps $T_{1}$ och $T_{2}$ . Höger underordnad av $T_{1}$ efter kopplingen definieras som en koppling av dess tidigare högra underordnade och $T_{2}$ .

Anslutningsalgoritmen är som följer:

 funktion  join(L, k, R)  if  prior(k, k(L)) och prior(k, k(R))  return  Node(L, k, R)  if  prior(k(L), k(R) )  return  Node(vänster(L), k(L), join(höger(L), k, R))  return  Node(join(L, k, vänster(R)), k(R), höger(R) ) 

För att dela $T$ med $x$ görs ett rekursivt delat anrop till antingen vänster eller höger underordnad av $T$ .

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å treaps t ₁ och t ₂ , som representerar mängderna A och B , är en treap t som representerar A ∪ B . Följande rekursiva algoritm beräknar unionen:

    
     funktion  union(t  1  , t  2  ):  om  t  1  = noll:  returnera  t  2  om  t  2  = noll:  returnera  t  1  om  priority(t  1  ) < priority(t  2  ):  byt  t  1  och t  2  t  <  , t  >  ← dela t  2  på tangent(t  1  )  return  join(union(vänster(t  1  ), t  <  ), nyckel(t  1  ), union(höger(t  1  ), t  >  )) 

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

Algoritmen för korsning är liknande, men kräver join- hjälparrutinen. Komplexiteten för var och en av förening, skärning och skillnad är O ( m log n / m ) för treaps av storlekarna m och n , med m ≤ n . Dessutom, eftersom de rekursiva uppmaningarna till union är oberoende av varandra, kan de utföras parallellt .

Split och Union call Gå med men hanterar inte balanseringskriterierna för treaps direkt, en sådan implementering brukar kallas den "join-baserade" implementeringen .

Observera att om hash-värden för nycklar används som prioriteringar och strukturellt lika noder slås samman redan vid konstruktion, så kommer varje sammanfogad nod att vara en unik representation av en uppsättning nycklar. Förutsatt att det bara kan finnas en samtidig rotnod som representerar en given uppsättning nycklar, kan två uppsättningar testas för likhet genom pekarjämförelse, som är konstant i tiden.

Denna teknik kan användas för att förbättra sammanslagningsalgoritmerna så att de presterar snabbt även när skillnaden mellan två uppsättningar är liten. Om ingångsmängderna är lika, kan unions- och skärningsfunktionerna bryta omedelbart och returnera en av ingångsmängderna som ett resultat, medan differensfunktionen bör returnera den tomma mängden.

Låt d vara storleken på den symmetriska skillnaden. De modifierade sammanslagningsalgoritmerna kommer då också att begränsas av O ( d log n / d ) .

Randomiserat binärt sökträd

Det randomiserade binära sökträdet, som introducerades av Martínez och Roura efter Aragons och Seidels arbete med treaps, lagrar samma noder med samma slumpmässiga fördelning av trädformen, men upprätthåller olika information inom trädets noder för att bibehålla dess randomiserad struktur.

Istället för att lagra slumpmässiga prioriteringar på varje nod, lagrar det randomiserade binära sökträdet ett litet heltal vid varje nod, antalet avkomlingar (som räknar sig själv som en); dessa siffror kan bibehållas under trädrotationsoperationer vid endast en konstant extra tid per rotation. När en nyckel x ska infogas i ett träd som redan har n noder väljer infogningsalgoritmen med sannolikhet 1/( n + 1) att placera x som trädets nya rot, och annars anropar den infogningsproceduren rekursivt för att infoga x i det vänstra eller högra underträdet (beroende på om dess nyckel är mindre än eller större än roten). Antalet avkomlingar används av algoritmen för att beräkna de nödvändiga sannolikheterna för de slumpmässiga valen vid varje steg. Att placera x vid roten av ett underträd kan utföras antingen som i treapen genom att infoga det vid ett löv och sedan rotera det uppåt, eller genom en alternativ algoritm som beskrivs av Martínez och Roura som delar upp underträdet i två delar för att användas som vänster och höger underordnade av den nya noden.

Borttagningsproceduren för ett randomiserat binärt sökträd använder samma information per nod som infogningsproceduren, men till skillnad från infogningsproceduren behöver den bara i genomsnitt O(1) slumpmässiga beslut för att sammanfoga de två underträden som faller från vänster och höger barn i den borttagna noden till ett enda träd. Det beror på att underträden som ska sammanfogas är i genomsnitt på djupet Θ(log n); att sammanfoga två träd av storleken n och m behöver i genomsnitt Θ(log(n+m)) slumpmässiga val. Om det vänstra eller högra underträdet för noden som ska raderas är tomt, är joinoperationen trivial; annars väljs vänster eller höger underordnat av den borttagna noden som den nya underträdroten med sannolikhet proportionell mot dess antal avkomlingar, och kopplingen fortsätter rekursivt.

Jämförelse

Informationen som lagras per nod i det randomiserade binära trädet är enklare än i en treap (ett litet heltal snarare än ett slumptal med hög precision), men den gör ett större antal anrop till slumptalsgeneratorn (O(log n ) anrop per infogning eller radering snarare än ett samtal per infogning) och infogningsproceduren är något mer komplicerad på grund av behovet av att uppdatera antalet ättlingar per nod. En mindre teknisk skillnad är att det i en treap finns en liten sannolikhet för en kollision (två nycklar får samma prioritet), och i båda fallen kommer det att finnas statistiska skillnader mellan en verklig slumptalsgenerator och pseudoslumptalet generator som vanligtvis används på digitala datorer. Men i vilket fall som helst är skillnaderna mellan den teoretiska modellen för perfekta slumpmässiga val som används för att designa algoritmen och kapaciteten hos faktiska slumptalsgeneratorer försvinnande små.

Även om treapen och det randomiserade binära sökträdet båda har samma slumpmässiga fördelning av trädformer efter varje uppdatering, kan historiken för modifieringar av träden som utförs av dessa två datastrukturer över en sekvens av infognings- och raderingsoperationer vara annorlunda. Till exempel, i en treap, om de tre siffrorna 1, 2 och 3 infogas i ordningen 1, 3, 2 och sedan siffran 2 raderas, kommer de återstående två noderna att ha samma förälder-barn-relation som de gjorde innan mittnumret infogades. I ett randomiserat binärt sökträd är det lika troligt att trädet efter raderingen är något av de två möjliga träden på dess två noder, oberoende av hur trädet såg ut före infogningen av mittnumret.

Implicit treap

En implicit treap är en enkel variant av en vanlig treap som kan ses som en dynamisk array som stöder följande operationer i $O(\log n)$ :

• Infoga ett element i valfri position
• Ta bort ett element från valfri position
• Hitta summa, minimum eller maximum element i ett givet intervall.
• Tillägg, målning i ett givet intervall
• Omvända element i ett givet intervall

Tanken bakom en implicit treap är att använda arrayindex som en nyckel, men att inte lagra det explicit. Annars skulle en uppdatering (infogning/borttagning) resultera i ändringar av nycklarna i $O(n)$ noder i trädet.

Nyckelvärdet ( implicit nyckel) för en nod T är antalet noder mindre än den noden plus en. Observera att sådana noder kan finnas inte bara i dess vänstra underträd utan också i vänstra underträd av dess förfäder P, om T är i det högra underträdet av P.

Därför kan vi snabbt beräkna den implicita nyckeln för den aktuella noden när vi utför en operation genom att ackumulera summan av alla noder när vi går ner i trädet. Observera att denna summa inte ändras när vi besöker det vänstra underträdet, men det kommer att öka med $cnt(T\högerpil L)+1$ när vi besöker det högra underträdet.

Anslutningsalgoritmen för en implicit treap är som följer:

         
       
              
        
               
    
               
     
 void  join  (  pitem  &  t  ,  pitem  l  ,  pitem  r  )  {  if  (  !  l  ||  !  r  )  t  =  l  ?  l  :  r  ;  annars  om  (  l  ->  föregående  >  r  ->  föregående  )  gå med  (  l  ->  r  ,  l  ->  r  ,  r  ),  t  =  l  ;  annars  gå med  (  r  ->  l  ,  l  ,  r  ->  l  ),  t  =  r  ;  upd_cnt  (  t  );  } 

Den delade algoritmen för en implicit treap är som följer:

               0 
     
              0 
          
       
                 
    
                     
     
 void  split  (  pitem  t  ,  pitem  &  l  ,  pitem  &  r  ,  int  key  ,  int  add  =  )  {  if  (  !  t  )  return  void  (  l  =  r  =  );  int  cur_key  =  add  +  cnt  (  t  ->  l  );  //implicit nyckel  if  (  nyckel  <=  cur_key  )  split  (  t  ->  l  ,  l  ,  t  ->  l  ,  key  ,  add  ),  r  =  t  ;  annars  dela  (  t  ->  r  ,  t  ->  r  ,  r  ,  nyckel  ,  lägg till  +  1  +  cnt  (  t  ->  l  )),  l  =  t  ;  upd_cnt  (  t  );  } 

Operationer

Sätt in element

För att infoga ett element vid position pos delar vi upp arrayen i två undersektioner [0...pos-1] och [pos..sz] genom att anropa splitfunktionen och vi får två träd $T1$ och $T2$ . Sedan slår vi samman $T1$ med den nya noden genom att anropa join -funktionen. Slutligen anropar vi join-funktionen för att slå samman $T1$ och $T2$ .

Ta bort element

Vi hittar elementet som ska raderas och utför en join på dess underordnade L och R. Vi ersätter sedan elementet som ska raderas med trädet som blev resultatet av joinoperationen.

Hitta summa, minimum eller maximum i ett givet intervall

För att utföra denna beräkning kommer vi att gå tillväga enligt följande:

• Först kommer vi att skapa ett ytterligare fält F för att lagra värdet på målfunktionen för intervallet som representeras av den noden. vi kommer att skapa en funktion som beräknar värdet F baserat på värdena för L och R barn i noden. Vi kommer att kalla denna målfunktion i slutet av alla funktioner som modifierar trädet, dvs , split och join.
• För det andra måste vi bearbeta en fråga för ett givet intervall [A..B]: Vi kommer att anropa s plit - funktionen två gånger och dela upp treapen i $T1$ som innehåller ${\ displaystyle \{1..A-1\}}$ , $T2$ som innehåller $\{A..B\}$ och $T3$ som innehåller $\{B+1..n\}$ . Efter att frågan har besvarats kommer vi att anropa join -funktionen två gånger för att återställa den ursprungliga treapen.

Tillägg/målning i ett givet intervall

För att utföra denna operation kommer vi att fortsätta enligt följande:

• Vi kommer att skapa ett extra fält D som kommer att innehålla mervärdet för underträdet. Vi kommer att skapa en funktions- push som kommer att användas för att sprida denna förändring från en nod till dess barn. Vi kommer att anropa denna funktion i början av alla funktioner som modifierar trädet, dvs dela upp och ansluta så att informationen inte går förlorad efter eventuella ändringar i trädet.

Vänd om i ett givet intervall

För att visa att underträdet för en given nod måste vändas för varje nod kommer vi att skapa ett extra booleskt fält R och sätta dess värde till sant. För att sprida denna förändring kommer vi att byta nodens barn och ställa in R till sant för dem alla.

Se även

• Fingersökning

externa länkar

• Samling av treapreferenser och info av Cecilia Aragon
• Öppna datastrukturer - Avsnitt 7.2 - Treap: A Randomized Binary Search Tree , Pat Morin
• Animerad treap
• Randomiserade binära sökträd . Föreläsningsanteckningar från en kurs av Jeff Erickson vid UIUC. Trots titeln handlar det i första hand om treaps och hoppa över listor ; randomiserade binära sökträd nämns endast kortfattat.
• En högpresterande nyckel-värdebutik baserad på treap av Junyi Sun
• VB6 implementering av treaps . Visual Basic 6 implementering av treaps som ett COM-objekt.
• ActionScript3-implementering av en treap
• Ren Python och Cython in-memory treap och duptreap
• Treaps i C# . Av Roy Clemmons
• Pure Go i minnet, oföränderliga läckerheter
• Pure Go persistent treap nyckel-värde lagringsbibliotek