Splay træ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 8. september 2016; checks kræver 19 redigeringer .
ekspanderende træ
Type Træ
Opfindelsens år 1985
Forfatter Daniel Slitor og Robert Andre Tarjan
Kompleksitet i O-symboler
Gennemsnit I værste fald
Hukommelsesforbrug På) På)
Søg O(log n) O(log n)
Indsæt O(log n) O(log n)
Fjernelse O(log n) O(log n)

Et  spredningstræ eller skævt træ er et binært søgetræ , der opretholder balanceegenskaben. Dette træ tilhører klassen af ​​"selvregulerende træer", der opretholder den nødvendige balance mellem forgrening af træet for at sikre, at søgninger, tilføjelser og sletninger kan udføres i logaritmisk tid fra antallet af lagrede elementer. Dette gøres uden brug af yderligere felter i træets noder (som f.eks. i rød-sorte træer eller AVL-træer , hvor hhv. vertexfarven og undertræets dybde er gemt i knudepunkterne). I stedet udføres sprøjteoperationen, som rotationer er en del af, hver gang træet tilgås.

Regnskabsomkostninger pr. operation med et træ er.

Det ekspanderende træ blev opfundet af Robert Tarjan og Daniel Slator i 1983.

Operationer

Splay (udvidelse)

Grundlæggende trædrift. Det består i at flytte toppunktet til roden ved hjælp af sekventiel udførelse af tre operationer: Zig, Zig-Zig og Zig-Zag. Lad os betegne det toppunkt, som vi ønsker at flytte til roden som x , dens overordnede - p , og forælderen p (hvis den findes) - g .

Zig: udføres, når p er roden. Træet roteres langs en kant mellem x og p . Eksisterer kun som et kanttilfælde og kører kun én gang i slutningen, når den indledende dybde af x var ulige.

Zig-Zig: Udføres , når både x og p er venstre (eller højre) sønner. Træet roteres langs kanten mellem g og p , og derefter langs kanten mellem p og x .

Zig-Zag: Kører når x er et højre barn og p  er et venstre barn (eller omvendt). Træet roteres langs kanten mellem p og x og derefter langs kanten mellem x og g .

Søg (søg efter et element)

Søgningen udføres som i et normalt binært søgetræ. Når et element er fundet, starter vi Splay for det.

Indsæt (tilføj et element)

Kør Split() på elementet, der tilføjes (se Split(), påmindelse: det bruger det nærmeste større eller lige store element i det eksisterende træ), og hæng de resulterende træer efter elementet, der skal tilføjes.

Slet (sletning af et element)

Vi finder et element i træet, laver et Splay til det, gør dets børn til det nuværende Merge-træ.

Flet (sammenlægning af to træer)

For at fusionere træerne T1 og T2, hvor alle nøgler i T1 er mindre end nøglerne i T2, laver vi Splay for det maksimale element i T1, så vil roden af ​​T1 ikke have et rigtigt barn. Derefter gør vi T2 til det rigtige barn af T1.

Split (ved at dele et træ i to dele)

For at opdele træet med x skal du finde det mindste element, der er større end eller lig med x, og lave et Splay for det. Derefter løsnes vi fra roden af ​​det venstre barn og returnerer de 2 resulterende træer.

Implementering

En implementering af et ekspanderende træ ville være en implementering, der bruger 3 pointere ved hvert vertex: en pegepind til højre og venstre børn, og også til forælderen. Dette undgår rekursiv implementering, som igen vil spare hukommelse. Ulempen i dette tilfælde er et større antal opgaver til opdatering af pointere, hvilket kan påvirke den endelige præstation.

Nedenfor er en implementering af et ekspanderende træ ved hjælp af 3 pointere pr. node. Også i denne implementering bruges Splay-operationen i alle grundlæggende operationer, der udføres på træet - ved indsættelse, sletning og søgning for at opnå en bedre balance i træet.

#ifndef SPLAYTREE_H #define SPLAYTREE_H skabelon < typenavn T > klasse SplayTree { privat : struct SplayNode { Node * leftChild ; Node * rightChild Node * forælder ; T data ; Node ( const T & key = T ()) : leftChild ( nullptr ), rightChild ( nullptr ), forælder ( nullptr ), nøgle ( key ) {} ~ Node () { slet venstreBarn ; slette rightChild ; } } * rod ; privat : SplayNode * _Successor ( SplayNode * localRoot ) const { SplayNode * successor = localRoot ; if ( efterfølger -> rightChild != nullptr ) { successor = _Minimum ( successor -> rightChild ); } andet { while ( efterfølger != root || efterfølger != efterfølger -> forælder -> venstreBarn ) { efterfølger = efterfølger -> forælder ; } } returnere efterfølger ; } SplayNode * _Predecessor ( SplayNode * localRoot ) const { SplayNode * predecessor = localRoot ; if ( forgænger -> leftChild != nullptr ) { predecessor = _Maksimum ( forgænger -> leftChild ); } andet { while ( forgænger != root || forgænger != forgænger -> forælder -> højreBarn ) { predecessor = predecessor -> forælder ; } } returnere forgænger ; } SplayNode * _Minimum ( SplayNode * localRoot ) const { SplayNode * minimum = localRoot ; while ( minimum -> leftChild != nullptr ) minimum = minimum -> leftChild ; afkast minimum ; } SplayNode * _Maximum ( SplayNode * localRoot ) const { SplayNode * maksimum = localRoot ; while ( max -> rightChild != nullptr ) maximum = maximum -> rightChild ; retur maksimum ; } SplayNode * _Search ( const T & key ) { SplayNode * searchedElement = root ; while ( searchedElement != nullptr ) { if ( searchedElement -> data < key ) searchedElement = searchedElement -> rightChild ; else if ( nøgle < searchedElement -> data ) searchedElement = searchedElement -> leftChild ; else if ( searchedElement -> data == key ) { _Splay ( søgtElement ); returnere søgtElement ; } } returnere nullptr ; } void _LeftRotate ( SplayNode * localRoot ) { SplayNode * rightChild = localRoot -> rightChild ; localRoot -> rightChild = rightChild -> leftChild ; if ( rightChild -> leftChild != nullptr ) rightChild -> leftChild -> parent = localRoot ; _Transplant ( 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 ; _Transplant ( 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 = localPrent -> parent ; } void _Splay ( SplayNode * pivotElement ) { while ( pivotElement != root ) { if ( pivotElement -> parent == root ) { if ( pivotElement == pivotElement -> parent -> leftChild ) { _RightRotate ( pivotElement -> overordnet ); } else if ( pivotElement == pivotElement -> parent -> rightChild ) { _LeftRotate ( pivotElement -> overordnet ); } } andet { // Zig-Zig trin. if ( pivotElement == pivotElement -> parent -> leftChild && pivotElement -> parent == pivotElement -> parent -> parent -> leftChild ) { _RightRotate ( pivotElement -> parent -> parent ); _RightRotate ( pivotElement -> overordnet ); } else if ( pivotElement == pivotElement -> forælder -> rightChild && pivotElement -> parent == pivotElement -> parent -> parent -> rightChild ) { _LeftRotate ( pivotElement -> parent -> parent ); _LeftRotate ( pivotElement -> overordnet ); } // Zig-Zag trin. else if ( pivotElement == pivotElement -> parent -> rightChild && pivotElement -> parent == pivotElement -> parent -> parent -> leftChild ) { _LeftRotate ( pivotElement -> overordnet ); _RightRotate ( pivotElement -> overordnet ); } andet hvis ( pivotElement == pivotElement -> forælder -> venstreBarn && pivotElement -> parent == pivotElement -> parent -> parent -> rightChild ) { _RightRotate ( pivotElement -> overordnet ); _LeftRotate ( pivotElement -> overordnet ); } } } } offentligt : SplayTree () { root = nullptr ; } virtual ~ SplayTree () { delete root ; } void Indsæt ( const T & key ) { SplayNode * preInsertPlace = nullptr ; SplayNode * insertPlace = root ; while ( insertPlace != nullptr ) { preInsertPlace = insertPlace ; if ( insertPlace -> data () < key ) insertPlace = insertPlace -> rightChild ; ellers hvis ( tast <= insertPlace -> data ) insertPlace = insertPlace -> leftChild ; } SplayNode * insertElement = ny SplayNode ( nøgle ); 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 Remove ( const T & key ) { SplayNode * removeElement = _Search ( nøgle ); if ( fjernElement != nullptr ) { if ( removeElement -> rightChild == nullptr ) _Transplant ( removeElement , removeElement -> leftChild ); else if ( removeElement -> leftChild == nullptr ) _Transplant ( removeElement , removeElement -> rightChild ); andet { 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 ); } slet removeElement ; } } bool Søg ( const T & key ) { return _Search ( key ) != nullptr ; } bool isEmpty () const { return root == nullptr ; } T Efterfølger ( konst T & nøgle ) { if ( _Successor ( _Søg ( nøgle )) != nullptr ) { returner _Successor ( _Søg ( nøgle )) -> getValue (); } andet { returnere -1 ; } } T Forgænger ( konst T & nøgle ) { if ( _Forgænger ( _Søg ( tast )) != nullptr ) { returner _Forgænger ( _Søg ( tast )) -> getValue (); } andet { returnere -1 ; } } }; #endif //SPLAYTREE_H

Bemærk

Et ekspanderende træ giver en selvmodificerende struktur - en struktur kendetegnet ved en tendens til at holde hyppigt tilgåede noder nær toppen af ​​træet, mens sjældent tilgåede noder bevæger sig tættere på bladene. Således vil adgangstiden til hyppigt besøgte noder være mindre, og adgangstiden til sjældent besøgte noder vil være længere end gennemsnittet.

Et ekspanderende træ har ikke nogen eksplicitte balanceringsfunktioner, men processen med at skæve noder mod roden er med til at holde træet i balance.

Se også

  • Balancerede (selvbalancerende) træer:
  • Liste over datastrukturer (træer)

Litteratur

  • Thomas H. Kormen et al. Algoritmer: konstruktion og analyse. - 2. udg. - M . : Williams Publishing House , 2007. - S. 1296. - ISBN 5-8459-0857-4 .
  • Daniel Sleater, Robert Tarjan. En datastruktur for dynamiske træer. - Tidsskrift for Computer- og Systemvidenskab, 1983. - S. 262-391.