Splay arbore

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 8 septembrie 2016; verificările necesită 19 modificări .
arbore în expansiune
Tip de Lemn
Anul inventiei 1985
Autor Daniel Slitor și Robert Andre Tarjan
Complexitatea în simbolurile O
In medie În cel mai rău caz
Consumul de memorie Pe) Pe)
Căutare O(log n) O(log n)
Introduce O(log n) O(log n)
Îndepărtarea O(log n) O(log n)

Un  arbore splay sau un arbore oblic este un arbore binar de căutare care menține proprietatea echilibrului. Acest arbore aparține clasei de „arbori de autoreglare” care mențin echilibrul necesar de ramificare a arborelui pentru a se asigura că căutările, adăugările și ștergerile pot fi efectuate în timp logaritmic din numărul de elemente stocate. Acest lucru se face fără a utiliza câmpuri suplimentare în nodurile arborelui (cum ar fi, de exemplu, în arbori roșu-negru sau arbori AVL , unde culoarea vârfurilor și, respectiv, adâncimea subarborelui sunt stocate în vârfuri). În schimb, operația de splay, din care fac parte rotațiile, este efectuată de fiecare dată când este accesat arborele.

Costul contabil pentru o operațiune cu un arbore este.

Arborele în expansiune a fost inventat de Robert Tarjan și Daniel Slator în 1983.

Operațiuni

Splay (extindere)

Operarea de bază a arborelui. Constă în deplasarea vârfului la rădăcină folosind executarea secvențială a trei operații: Zig, Zig-Zig și Zig-Zag. Să notăm vârful pe care vrem să-l mutăm la rădăcină ca x , părintele său - p și părintele p (dacă există) - g .

Zig: executat când p este rădăcina. Arborele este rotit de-a lungul unei muchii între x și p . Există doar ca un caz de margine și rulează o singură dată la sfârșit, când adâncimea inițială a lui x era impară.

Zig-Zig: Se execută atunci când ambii x și p sunt fii stângi (sau dreapta). Arborele este rotit de-a lungul marginii dintre g și p și apoi de-a lungul marginii dintre p și x .

Zig-Zag: rulează când x este un copil drept și p  este un copil stâng (sau invers). Arborele este rotit de-a lungul marginii dintre p și x și apoi de-a lungul marginii dintre x și g .

Caută (căută un element)

Căutarea este efectuată ca într-un arbore de căutare binar normal. Când este găsit un element, lansăm Splay pentru el.

Inserare (adăugarea unui element)

Rulați Split() pe elementul adăugat (vezi Split(), reamintire: folosește cel mai apropiat element mai mare sau egal al arborelui existent) și agățați arborii rezultați de elementul care urmează să fie adăugat.

Șterge (ștergerea unui element)

Găsim un element în arbore, facem un Splay pentru el, îi facem pe copiii săi arborele Merge actual.

Merge (unirea a doi copaci)

Pentru a îmbina arborii T1 și T2, în care toate cheile din T1 sunt mai mici decât cheile din T2, facem Splay pentru elementul maxim al lui T1, atunci rădăcina lui T1 nu va avea un copil potrivit. După aceea facem din T2 copilul drept al lui T1.

Împărțire (împărțirea unui copac în două părți)

Pentru a împărți arborele cu x, găsiți cel mai mic element care este mai mare sau egal cu x și faceți un Splay pentru el. După aceea, ne desprindem de rădăcina copilului stâng și returnăm cei 2 copaci rezultați.

Implementare

O implementare a unui arbore în expansiune ar fi o implementare care folosește 3 pointeri la fiecare vârf: un pointer către copiii din dreapta și din stânga și, de asemenea, către părinte. Acest lucru evită implementarea recursivă, care, la rândul său, va economisi memorie. Dezavantajul în acest caz este un număr mai mare de sarcini pentru actualizarea pointerilor, care poate afecta performanța finală.

Mai jos este o implementare a unui arbore în expansiune folosind 3 pointeri per nod. De asemenea, în această implementare, operația Splay este utilizată în toate operațiunile de bază efectuate pe arbore - la inserare, ștergere și căutare pentru a obține un echilibru mai bun al arborelui.

#ifndef SPLAYTREE_H #define SPLAYTREE_H template < typename T > class SplayTree { privat : struct SplayNode { Nod * leftChild ; Nodul * rightChild Nod * părinte ; date T ; Nod ( const T & cheie = T ()) : leftChild ( nullptr ), rightChild ( nullptr ), părinte ( nullptr ), cheie ( cheie ) {} ~ Nodul () { șterge leftChild ; șterge rightChild ; } } * rădăcină ; privat : SplayNode * _Successor ( SplayNode * localRoot ) const { SplayNode * succesor = localRoot ; if ( succesor -> rightChild != nullptr ) { succesor = _Minim ( succesor -> rightChild ); } altfel { while ( succesor != root || succesor != succesor -> parent -> leftChild ) { succesor = succesor -> părinte ; } } returnare succesor ; } SplayNode * _Predecesor ( SplayNode * localRoot ) const { SplayNode * predecesor = localRoot ; if ( predecesor -> leftChild != nullptr ) { predecesor = _Maximum ( predecesor -> leftChild ); } altfel { while ( predecesor != root || predecesor != predecesor -> parent -> rightChild ) { predecesor = predecesor -> părinte ; } } returnează predecesorul ; } SplayNode * _Minimum ( SplayNode * localRoot ) const { SplayNode * minimum = localRoot ; while ( minimum -> leftChild != nullptr ) minimum = minimum -> leftChild ; randament minim ; } SplayNode * _Maximum ( SplayNode * localRoot ) const { SplayNode * maximum = localRoot ; while ( maximum -> rightChild != nullptr ) maximum = maximum -> rightChild ; randament maxim ; } SplayNode * _Search ( const T & key ) { SplayNode * searchedElement = root ; while ( searchedElement != nullptr ) { if ( searchedElement -> data < cheie ) searchedElement = searchedElement -> rightChild ; else if ( cheie < searchedElement -> data ) searchedElement = searchedElement -> leftChild ; else if ( searchedElement -> data == cheie ) { _Splay ( searchedElement ); return searchedElement ; } } returnează nullptr ; } void _LeftRotate ( SplayNode * localRoot ) { SplayNode * rightChild = localRoot -> rightChild ; localRoot -> rightChild = rightChild -> leftChild ; if ( rightChild -> leftChild != nullptr ) rightChild -> leftChild -> părinte = localRoot ; _Transplant ( localRoot , rightChild ); rightChild -> leftChild = localRoot ; rightChild -> leftChild -> părinte = rightChild ; } void _RightRotate ( SplayNode * localRoot ) { SplayNode * leftChild = localRoot -> leftChild ; localRoot -> leftChild = leftChild -> rightChild ; if ( leftChild -> rightChild != nullptr ) leftChild -> rightChild -> părinte = localRoot ; _Transplant ( localRoot , leftChild ); leftChild -> rightChild = localRoot ; leftChild -> rightChild -> părinte = leftChild ; } void _Transplant ( SplayNode * localParent , SplayNode * localChild ) { if ( localParent -> parent == nullptr ) root = localChild ; else if ( localParent == localParent -> părinte -> leftChild ) localParent -> părinte -> 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 == root ) { if ( pivotElement == pivotElement -> parent -> leftChild ) { _RightRotate ( pivotElement -> părinte ); } else if ( pivotElement == pivotElement -> parent -> rightChild ) { _LeftRotate ( pivotElement -> părinte ); } } altfel { // Zig-Zig pas. if ( pivotElement == pivotElement -> părinte -> stângaCopil && pivotElement -> parent == pivotElement -> parent -> parent -> leftChild ) { _RightRotate ( pivotElement -> părinte -> părinte ); _RightRotate ( pivotElement -> părinte ); } else if ( pivotElement == pivotElement -> parent -> rightChild && pivotElement -> parent == pivotElement -> parent -> parent -> rightChild ) { _LeftRotate ( pivotElement -> părinte -> părinte ); _LeftRotate ( pivotElement -> părinte ); } // Pas în zig-zag. else if ( pivotElement == pivotElement -> parent -> rightChild && pivotElement -> parent == pivotElement -> parent -> parent -> leftChild ) { _LeftRotate ( pivotElement -> părinte ); _RightRotate ( pivotElement -> părinte ); } else if ( pivotElement == pivotElement -> parent -> leftChild && pivotElement -> parent == pivotElement -> parent -> parent -> rightChild ) { _RightRotate ( pivotElement -> părinte ); _LeftRotate ( pivotElement -> părinte ); } } } } public : SplayTree () { root = nullptr ; } virtual ~ SplayTree () { șterge rădăcină ; } void Insert ( const T & key ) { SplayNode * preInsertPlace = nullptr ; SplayNode * insertPlace = root ; while ( insertPlace != nullptr ) { preInsertPlace = insertPlace ; if ( insertPlace -> data () < key ) insertPlace = insertPlace -> rightChild ; else if ( cheie <= insertPlace -> data ) insertPlace = insertPlace -> leftChild ; } SplayNode * insertElement = SplayNode nou ( cheie ); 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 ( cheie ); if ( removeElement != nullptr ) { if ( removeElement -> rightChild == nullptr ) _Transplant ( removeElement , removeElement -> leftChild ); else if ( removeElement -> leftChild == nullptr ) _Transplant ( removeElement , removeElement -> rightChild ); else { 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 ); } șterge removeElement ; } } bool Căutare ( const T & cheie ) { return _Căutare ( cheie ) != nullptr ; } bool isEmpty () const { return root == nullptr ; } T Succesor ( const T & key ) { if ( _Succesor ( _Căutare ( cheie )) != nullptr ) { return _Successor ( _Search ( cheie )) -> getValue (); } altfel { întoarcere -1 ; } } T Predecesor ( const T & key ) { if ( _Predecesor ( _Căutare ( cheie )) != nullptr ) { return _Predecesor ( _Search ( cheie )) -> getValue (); } altfel { întoarcere -1 ; } } }; #endif //SPLAYTREE_H

Notă

Un arbore în expansiune oferă o structură cu auto-modificare - o structură caracterizată printr-o tendință de a păstra nodurile accesate frecvent în apropierea vârfului copacului, în timp ce nodurile accesate rar se deplasează mai aproape de frunze. Astfel, timpul de acces la nodurile vizitate frecvent va fi mai mic, iar timpul de acces la nodurile vizitate rar va fi mai mare decât media.

Un arbore în expansiune nu are funcții de echilibrare explicite, dar procesul de înclinare a nodurilor către rădăcină ajută la menținerea echilibrului arborelui.

Vezi și

  • Copaci echilibrați (auto-echilibrați):
  • Lista structurilor de date (arbori)

Literatură

  • Thomas H. Kormen et al.Algoritmi : construcție și analiză. - Ed. a II-a. - M . : Editura Williams , 2007. - S. 1296. - ISBN 5-8459-0857-4 .
  • Daniel Sleater, Robert Tarjan. O structură de date pentru arbori dinamici. - Journal of Computer and System Sciences, 1983. - S. 262-391.