Splay träd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 september 2016; kontroller kräver 19 redigeringar .
expanderande träd
Sorts Trä
Uppfinningens år 1985
Författare Daniel Slitor och Robert Andre Tarjan
Komplexitet i O-symboler
Medel Som värst
Minnesförbrukning På) På)
Sök O(log n) O(log n)
Föra in O(log n) O(log n)
Borttagning O(log n) O(log n)

Ett  splayträd eller skevträd är ett binärt sökträd som upprätthåller balansegenskapen. Detta träd tillhör klassen av "självreglerande träd" som upprätthåller den nödvändiga balansen av förgrening av trädet för att säkerställa att sökningar, tillägg och raderingar kan utföras i logaritmisk tid från antalet lagrade element. Detta görs utan att använda några ytterligare fält i trädets noder (som till exempel i rödsvarta träd eller AVL-träd , där vertexfärgen respektive underträdsdjupet lagras i hörnen). Istället utförs spridningsoperationen, som rotationer är en del av, varje gång trädet öppnas.

Redovisningskostnad per operation med ett träd är.

Det expanderande trädet uppfanns av Robert Tarjan och Daniel Slator 1983.

Operationer

Splay (expansion)

Grundläggande träddrift. Det består i att flytta spetsen till roten genom att sekventiellt utföra tre operationer: Zig, Zig-Zig och Zig-Zag. Låt oss beteckna vertexet som vi vill flytta till roten som x , dess förälder - p , och föräldern p (om den finns) - g .

Zig: körs när p är roten. Trädet roteras längs en kant mellan x och p . Finns bara som ett kantfall och körs bara en gång i slutet, när det initiala djupet för x var udda.

Zig-Zig: Körs när både x och p är vänster (eller höger) söner. Trädet roteras längs kanten mellan g och p , och sedan längs kanten mellan p och x .

Zig-Zag: Körs när x är ett höger barn och p  är ett vänster barn (eller vice versa). Trädet roteras längs kanten mellan p och x och sedan längs kanten mellan x och g .

Sök (sök efter ett element)

Sökningen utförs som i ett vanligt binärt sökträd. När ett element hittas startar vi Splay för det.

Infoga (lägga till ett element)

Kör Split() på elementet som läggs till (se Split(), påminnelse: det använder det närmaste större eller lika element i det befintliga trädet) och häng de resulterande träden efter elementet som ska läggas till.

Ta bort (ta bort ett element)

Vi hittar ett element i trädet, gör en Splay för det, gör dess barn till det nuvarande Merge-trädet.

Sammanfoga (sammanfoga två träd)

För att slå samman träden T1 och T2, där alla nycklar i T1 är mindre än nycklarna i T2, gör vi Splay för det maximala elementet av T1, då kommer roten av T1 inte att ha ett rätt barn. Efter det gör vi T2 till det rätta barnet till T1.

Split (dela ett träd i två delar)

För att dela trädet med x, hitta det minsta elementet som är större än eller lika med x och gör en Splay för det. Efter det lossnar vi från roten på det vänstra barnet och returnerar de 2 resulterande träden.

Implementering

En implementering av ett expanderande träd skulle vara en implementering som använder 3 pekare vid varje vertex: en pekare till höger och vänster barn, och även till föräldern. Detta undviker rekursiv implementering, vilket i sin tur kommer att spara minne. Nackdelen i det här fallet är ett större antal uppdrag för uppdatering av pekare, vilket kan påverka den slutliga prestandan.

Nedan är en implementering av ett expanderande träd med 3 pekare per nod. I den här implementeringen används Splay-operationen i alla grundläggande operationer som utförs på trädet - när du infogar, tar bort och söker för att uppnå en bättre balans i trädet.

#ifndef SPLAYTREE_H #definiera SPLAYTREE_H mall < typnamn T > klass SplayTree { privat : struct SplayNode { Nod * leftChild ; Nod * rightChild Nod * förälder ; T data ; Nod ( const T & key = T ()) : leftChild ( nullptr ), rightChild ( nullptr ), parent ( nullptr ), key ( key ) {} ~ Node () { ta bort leftChild ; ta bort rightChild ; } } * rot ; privat : SplayNode * _Successor ( SplayNode * localRoot ) const { SplayNode * successor = localRoot ; if ( efterföljare -> rightChild != nullptr ) { successor = _Minimum ( efterföljare -> rightChild ); } annat { while ( efterföljare != rot || efterträdare != efterträdare -> förälder -> vänsterBarn ) { successor = successor -> parent ; } } returnera efterträdare ; } SplayNode * _Predecessor ( SplayNode * localRoot ) const { SplayNode * predecessor = localRoot ; if ( föregångare -> leftChild != nullptr ) { predecessor = _Maximum ( föregångare -> leftChild ); } annat { while ( föregångare != rot || föregångare != föregångare -> förälder -> högerChild ) { predecessor = predecessor -> parent ; } } återvända föregångare ; } SplayNode * _Minimum ( SplayNode * localRoot ) const { SplayNode * minimum = localRoot ; while ( minimum -> leftChild != nullptr ) minimum = minimum -> leftChild ; avkastning minimum ; } SplayNode * _Maximum ( SplayNode * localRoot ) const { SplayNode * maximum = localRoot ; while ( max -> rightChild != nullptr ) maximum = maximum -> rightChild ; returnera maximalt ; } SplayNode * _Search ( konst T & nyckel ) { SplayNode * searchedElement = rot ; while ( searchedElement != nullptr ) { if ( searchedElement -> data < key ) searchedElement = searchedElement -> rightChild ; else if ( nyckel < searchedElement -> data ) searchedElement = searchedElement -> leftChild ; else if ( sökteElement -> data == nyckel ) { _Splay ( söktElement ); returnera söktElement ; } } returnera nullptr ; } void _LeftRotate ( SplayNode * localRoot ) { SplayNode * rightChild = localRoot -> rightChild ; localRoot -> rightChild = rightChild -> leftChild ; if ( rightChild -> leftChild != nullptr ) rightChild -> leftChild -> parent = localRoot ; _Transplantation ( localRoot , rightChild ); rightChild -> leftChild = localRoot ; rightChild -> leftChild -> parent = rightChild ; } void _RightRotate ( SplayNode * localRoot ) { SplayNode * leftChild = localRoot -> leftChild ; localRoot -> leftChild = leftChild -> rightChild ; if ( leftChild -> rightChild != nullptr ) leftChild -> rightChild -> parent = localRoot ; _Transplantation ( localRoot , leftChild ); leftChild -> rightChild = localRoot ; leftChild -> rightChild -> parent = leftChild ; } void _Transplant ( SplayNode * localParent , SplayNode * localChild ) { if ( localParent -> parent == nullptr ) root = localChild ; else if ( localParent == localParent -> parent -> leftChild ) localParent -> parent -> leftChild = localChild ; else if ( localParent == localParent -> parent -> rightChild ) localParent -> parent -> rightChild = localChild ; if ( localChild != nullptr ) localChild -> parent = localParent -> parent ; } void _Splay ( SplayNode * pivotElement ) { while ( pivotElement != root ) { if ( pivotElement -> parent == rot ) { if ( pivotElement == pivotElement -> parent -> leftChild ) { _RightRotate ( pivotElement -> parent ); } else if ( pivotElement == pivotElement -> parent -> rightChild ) { _LeftRotate ( pivotElement -> parent ); } } annat { // Zig-Zig steg. if ( pivotElement == pivotElement -> förälder -> leftChild && pivotElement -> parent == pivotElement -> parent - > parent - > leftChild ) { _RightRotate ( pivotElement -> parent - > parent ); _RightRotate ( pivotElement -> parent ); } else if ( pivotElement == pivotElement -> parent -> rightChild && pivotElement -> parent == pivotElement -> parent - > parent - > rightChild ) { _LeftRotate ( pivotElement -> parent - > parent ); _LeftRotate ( pivotElement -> parent ); } // Zig-Zag steg. else if ( pivotElement == pivotElement -> parent -> rightChild && pivotElement -> parent == pivotElement -> parent - > parent - > leftChild ) { _LeftRotate ( pivotElement -> parent ); _RightRotate ( pivotElement -> parent ); } else if ( pivotElement == pivotElement -> förälder -> leftChild && pivotElement -> parent == pivotElement -> parent - > parent - > rightChild ) { _RightRotate ( pivotElement -> parent ); _LeftRotate ( pivotElement -> parent ); } } } } offentliga : SplayTree () { root = nullptr ; } virtuell ~ SplayTree () { ta bort rot ; } void Insert ( const T & key ) { SplayNode * preInsertPlace = nullptr ; SplayNode * insertPlace = rot ; while ( insertPlace != nullptr ) { preInsertPlace = insertPlace ; if ( insertPlace -> data () < nyckel ) insertPlace = insertPlace -> rightChild ; else if ( nyckel <= insertPlace -> data ) insertPlace = insertPlace -> leftChild ; } SplayNode * insertElement = ny SplayNode ( nyckel ); insertElement -> parent = preInsertPlace ; if ( preInsertPlace == nullptr ) root = insertElement ; else if ( preInsertPlace -> data < insertElement -> data ) preInsertPlace -> rightChild = insertElement ; else if ( insertElement -> data < preInsertPlace -> data ) preInsertPlace -> leftChild = insertElement ; _Splay ( insertElement ); } void Ta bort ( konst T & nyckel ) { SplayNode * removeElement = _Search ( nyckel ); if ( removeElement != nullptr ) { if ( removeElement -> rightChild == nullptr ) _Transplant ( removeElement , removeElement -> leftChild ); else if ( removeElement -> leftChild == nullptr ) _Transplant ( removeElement , removeElement -> rightChild ); annat { SplayNode * newLocalRoot = _Minimum ( removeElement -> rightChild ); if ( newLocalRoot -> parent != removeElement ) { _Transplant ( newLocalRoot , newLocalRoot -> rightChild ); newLocalRoot -> rightChild = removeElement -> rightChild ; newLocalRoot -> rightChild -> parent = newLocalRoot ; } _Transplant ( removeElement , newLocalRoot ); newLocalRoot -> leftChild = removeElement -> leftChild ; newLocalRoot -> leftChild -> parent = newLocalRoot ; _Splay ( newLocalRoot ); } ta bort removeElement ; } } bool Sök ( const T & nyckel ) { return _Search ( nyckel ) != nullptr ; } bool isEmpty () const { return root == nullptr ; } T Efterträdare ( konst T & nyckel ) { if ( _Successor ( _Search ( nyckel )) != nullptr ) { return _Successor ( _Search ( nyckel )) -> getValue (); } annat { returnera -1 ; } } T -föregångare ( konst T & nyckel ) { if ( _Predecessor ( _Search ( nyckel )) != nullptr ) { returnera _Predecessor ( _Search ( nyckel )) -> getValue (); } annat { returnera -1 ; } } }; #endif //SPLAYTREE_H

Notera

Ett expanderande träd ger en självmodifierande struktur – en struktur som kännetecknas av en tendens att hålla ofta åtkomliga noder nära toppen av trädet, medan noder som sällan nås rör sig närmare löven. Således kommer åtkomsttiden till ofta besökta noder att vara kortare, och åtkomsttiden till sällan besökta noder kommer att vara längre än genomsnittet.

Ett expanderande träd har inga explicita balanseringsfunktioner, men processen att sneda noder mot roten hjälper till att hålla trädet balanserat.

Se även

  • Balanserade (självbalanserande) träd:
  • Lista över datastrukturer (träd)

Litteratur

  • Thomas H. Kormen et al Algoritmer: konstruktion och analys. - 2:a uppl. - M . : Williams Publishing House , 2007. - S. 1296. - ISBN 5-8459-0857-4 .
  • Daniel Sleater, Robert Tarjan. En datastruktur för dynamiska träd. - Journal of Computer and System Sciences, 1983. - S. 262-391.