Rašireno drvo

Rašireno drvo je samopodešavajuće binarno drvo pretrage sa dodatnim svojstvom da se nedavno pristupljenim elementima brzo pristupa iznova. Ovo drvo je u mogućnosti da obavlja operacije kao što su umetanje, traženje i brisanje u amortizovanom vremenu O (log n). Za mnoge nizove neslučajnih operacija, raširena drvo imaju bolje performanse nego druga drva za pretragu, čak i kada je specifičan obrazac niza podataka nepoznat. Rašireno drvo su osmislili Daniel Dominic Sleator i Robert Endre Tarjan 1985. godine.

Sve uobičajene operacije nad binarnim stablom su kombinovane sa jednom osnovnom operacijom koja se zove širenje. Širenje drveta za određeni element sređuje drvo tako da je taj element smešten u koren drveta. Jedan način da se ovo uradi je da prvo izvršimo uobičajenu pretragu binarnog stabla kako bismo pronašli element koji je u pitanju i onda primenimo rotacije drveta na određeni način kako bismo doveli element do vrha. Alternativno, algoritam tipa odozdo-nagore može kombinovati pretragu i prepoznavanje drvata u jednu fazu.

PrednostiUredi

Dobre perofrmanse za rašireno drvo zavise od činjenice da je samooptimizujuče, u smislu da se čvorovi kojima se često pristupa pomeraju bliže korenu, gde im se može pristupiti brže. Visina stabla u najgorem slučaju --- iako neverovatna --- je O(n), dok je prosečna O(log n). Činjenica da su često korišćeni čvorovi blizu korena je prednost za gotovo sve praktične aplikacije i posebno je korisna za implementaciju keševa i algoritama za „skupljanje đubreta“ (recikliranje memorije koja programu više nije potrebna).

Neke od prednosti su:

  • Jednostavna implementacija --- jednostavnija nego druga samobalansirajuća binarna stabla pretrage, poput crveno-crnih ili AVL-stabala
  • Upredive performase --- analiza srednjeg slučaja daje iste rezultate kao za druga stabla
  • Malo zauzeće memorije --- raširena stabla ne moraju da čuvaju nikakve dodatne podatke kako bi se samobalansirala
  • Mogućnost kreiranja stalne strukture podataka od raširenih stabala --- koja omogućava da se pristupi i prethodnoj i novoj verziji nakon ađuriranja. Ovo mođe biti korisno u funkcionalnom programiranju i treba amortizovan O(log n) dodatni memorijski prostor po ažuriranju
  • Dobro radi sa čvorovima koji sadržie identičke ključeve --- u suprotnosti sa drugim tipovima samobalansirajućih stabala. Čak i sa identičkim ključevima, performanse ostaju amortizovano O(log n). Sve operacije nad drvetom održavaju redosled identičkih ključeva u drvetu, što je svojstvo slično stabilnim algoritmima sortiranja. Dobro osmišljena operacija traženja može da vrati čvor koji je najviše levo ili čvor koji je najviše desno za dati ključ.

ManeUredi

Najznačajnija mana raširenih drveta je ta što visina raširenog drveta može biti linearna. Na primer, ovo će biti slučaj posle pristupanja svakom od n elemenata u neopadajućem redosledu. Kako visina drveta odgovara vremenu pristupa u najgorem slučaju, to znali da će stvarni trošak ove operacije biti prilično visok. Međutim, amortizovani trošak najgoreg slučaja je logaritamski, O(log n). Takođe, očekivani trošak pristupa može biti smanjen na O(log n) koristeći nasumičnu varijantu raširenog drveta.[1]

Rašireno drvo može biti gore od statičkog drveta za najviše konstantan faktor.

OperacijeUredi

ŠirenjeUredi

Kada se pristupa čvoru x, operacija širenja se izršava nad x kako bi ga pomerila do korena. Kako bismo izvršili operaciju širenja, izvodimo niz koraka širenja, od čega svaki pomera x bliže korenu. Izvođenjem operacije širenja nad čvorom koji nas zanima nakon svakog pristupa, nedavno pristupljeni čvorovi se drže bliže korenu i drvo ostaje balansirano, čime smo postigli amortizovanu vremensku složenost u obećanim granicama.

Svaki korak zavisi od tri faktora

  • Da li je   levo ili desno dete svog oca, čvora  
    • Da li je   koren ili ne, i ako nije
      • Da li je   levo ili desno dete svog oca, čvora  

Takođe, važno je ne zaboraviti da podesimo da   ("pradeda“ čvora  ) sada pokazuje na x nakon svake operacije širenja. Ako   ne postoji, onda je   očigledno koren, i kao takav na koren mora biti postavljen.

Postoji tri vrste operacija širenja, od kojih svaka ima „levi“ i „desni“ slučaj. Kako bi ovaj tekst bio sažetiji, samo jedan od slučajeva je prikazan za svaku vrstu. Te vrste su:

Cik korak: Ovaj korak se vrži kada je   koren. Drvo se rotira u odnosu na granu između   i  . Cik koraci postoje kako bi se obradili izuzeti slučajevi parnosti i biće rađeni samo kao poslednji korak u operaciji širenja i samo kad   ima dubinu koja je neparan broj na početku operacije.

Cik-cik korak: Ovaj korak se vrši kada   nije koren i   i   su oba desni sinovi ili su oba levi sinovi. Slika iskod ilustruje slučaj kada su   i   oba levi sinovi. Drvo se rotira u odnosu na granu koja spaja   sa svojim ocem  , i potom se rotira u odnosu na granu koja spaja   i  . Primetite da su cik-cik koraci jedino što odvaja raširena drveta od metode rotiraj do korena koju su predstavili Alen i Munro pre nego što su raširena drva predtavnjena.

Cik-cak korak: Ovaj korak se vrši kada   nije koren i kada je   desno dete i   je levo dete svog oca ili obratno. Drvo se rotira u odnosu na granu koja je između   i  , i onda se rotira u odnosu na rezultujuču granu između   i  . (slika).

UmetanjeUredi

Kako bismo umetnuli čvor   u rašireno drvo:

  1. Prvo vršimo umetanje kao da je u pitanju uobičajeno binarno drvo pretrage.
  2. Potom „širimo“ umetnuti čvor   do vrha drveta.

BrisanjeUredi

Kako bismo obrisali čvor  , koristimo isti metod kao u slučaju binarnog stabla pretrage: ako   ima dva sina, zamenimo njegovu vrednost bilo sa najvećim čvorom u levom podstablu ili sa najmanjim čvorom u desnom podstablu. Onda brišemo taj čvor (čija je vrednost sada u čvoru  ). Na ovaj način, brisanje je pojednostavljeno na problem brisanja čvora bez sinova ili sa jednim sinom.

Za razliku od binarnog drva pretrage, u raširenom drvu, širimo oca obrisanog čvora do vrha drveta ILI čvor koji treba da bude obrisan je prvo raširen, tj. postavljen da bude koren drveta i onda se briše. Ova operacija deli početno drvo na dva poddrveta. Sada se jednostavno najveći element levog poddrveta širi do vrha (METODA 1) ili se najmanji element desnog poddrveta (METODA 2) širi do vrha. Desno poddrvo postaje desno dete rezultujećeg levog poddrveta (za METODU 1). Koren levog poddrveta je koren spojenog drveta.

ImplementacijaUredi

Ispod je implementacija raširenih drva u programskom jeziku C++, koja koristi pokazivače da predstavi svaki čvor drveta. Ova implemetnacija je bazirana na drugoj metodi brisanja u rašireno drvu. Takođe, suprotno prethodnim definicijama, ova C++ verzija NE širi drvo posle operacija pretrage - drvo se širi samo na umetanjima i brisanjima.

#include <functional>

#ifndef SPLAY_TREE
#define SPLAY_TREE

template< typename T, typename Comp = std::less< T > >
class splay_tree {
private:
  Comp comp;
  unsigned long p_size;
  
  struct node {
    node *left, *right;
    node *parent;
    T key;
    node( const T& init = T( ) ) : left( 0 ), right( 0 ), parent( 0 ), key( init ) { }
  } *root;
  
  void left_rotate( node *x ) {
    node *y = x->right;
    x->right = y->left;
    if( y->left ) y->left->parent = x;
    y->parent = x->parent;
    if( !x->parent ) root = y;
    else if( x == x->parent->left ) x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
  }
  
  void right_rotate( node *x ) {
    node *y = x->left;
    x->left = y->right;
    if( y->right ) y->right->parent = x;
    y->parent = x->parent;
    if( !x->parent ) root = y;
    else if( x == x->parent->left ) x->parent->left = y;
    else x->parent->right = y;
    y->right = x;
    x->parent = y;
  }
  
  void splay( node *x ) {
    while( x->parent ) {
      if( !x->parent->parent ) {
        if( x->parent->left == x ) right_rotate( x->parent );
        else left_rotate( x->parent );
      } else if( x->parent->left == x && x->parent->parent->left == x->parent ) {
        right_rotate( x->parent->parent );
        right_rotate( x->parent );
      } else if( x->parent->right == x && x->parent->parent->right == x->parent ) {
        left_rotate( x->parent->parent );
        left_rotate( x->parent );
      } else if( x->parent->left == x && x->parent->parent->right == x->parent ) {
        right_rotate( x->parent );
        left_rotate( x->parent );
      } else {
        left_rotate( x->parent );
        right_rotate( x->parent );
      }
    }
  }
  
  void replace( node *u, node *v ) {
    if( !u->parent ) root = v;
    else if( u == u->parent->left ) u->parent->left = v;
    else u->parent->right = v;
    if( v ) v->parent = u->parent;
  }
  
  node* subtree_minimum( node *u ) {
    while( u->left ) u = u->left;
    return u;
  }
  
  node* subtree_maximum( node *u ) {
    while( u->right ) u = u->right;
    return u;
  }
public:
  splay_tree( ) : root( 0 ), p_size( 0 ) { }
  
  void insert( const T &key ) {
    node *z = root;
    node *p = 0;
    
    while( z ) {
      p = z;
      if( comp( z->key, key ) ) z = z->right;
      else z = z->left;
    }
    
    z = new node( key );
    z->parent = p;
    
    if( !p ) root = z;
    else if( comp( p->key, z->key ) ) p->right = z;
    else p->left = z;
    
    splay( z );
    p_size++;
  }
  
  node* find( const T &key ) {
    node *z = root;
    while( z ) {
      if( comp( z->key, key ) ) z = z->right;
      else if( comp( key, z->key ) ) z = z->left;
      else return z;
    }
    return 0;
  }
        
  void erase( const T &key ) {
    node *z = find( key );
    if( !z ) return;
    
    splay( z );
    
    if( !z->left ) replace( z, z->right );
    else if( !z->right ) replace( z, z->left );
    else {
      node *y = subtree_minimum( z->right );
      if( y->parent != z ) {
        replace( y, y->right );
        y->right = z->right;
        y->right->parent = y;
      }
      replace( z, y );
      y->left = z->left;
      y->left->parent = y;
    }
    
    delete z;
    p_size--;
  }
  
  const T& minimum( ) { return subtree_minimum( root )->key; }
  const T& maximum( ) { return subtree_maximum( root )->key; }
  
  bool empty( ) const { return root == 0; }
  unsigned long size( ) const { return p_size; }
};

#endif // SPLAY_TREE

AnalizaUredi

Jednostavna amortizovana analiza statičkih raširenih drva može se izvesti koristeći potencijalni metod. Pretpostavimo da je   broj čvorova poddrveta čiji je koren   (uključujući  ) i  . Tada je potencijalna funkcija   za rašireno drvo   suma svih redova svih čvorova u drvetu. Ova sume ima tendenciju da bude velika za loše balansirana drva, i niska za dobro balansirana drva. Možemo ograničiti amortizovan trošak bilo koje cik-cik ili cik-cak operacije pomoću

 

gde je   čvor koji treba pomeriti do korena i indeksi   i   znače pre i nakon operacije, redom. Kada se sumira čitava operacija širenja, teleskopskim metodom se dobija da je ta suma   što je u stvari  . Kako može postojati najviše jedna cik operacija, ovo dodaje samo konstantu.

Teoreme o performansamaUredi

Postoji nekoliko teorema i pretpostavki koje se tiču najgoreg slučaja za izvođenje niza   od   pristupa u raširenom drvetu koje sadrži   elemenata.

  • BALANS TEOREMA [2]

Trošak izvođenja niza operacija je  

  • TEOREMA STATIČKE OPTIMALNOSTI [2]

Neka   predstavlja broj pristupa elementu   u  . Trošak izvođenja   je  . Drugim rečima, raširena drva imaju performanse slične optimalnim statičkim binarnim drvima pretrage na nizovima od najmanje   pristupa.

  • STATIČKA PRST TEOREMA [2]

Neka   element kome je pristupljeno u  -om pristupu u nizu   i neka je   bilo koji fiksni element (prst). Trošak ivođenja   je  

  • TEOREMA RADNOG SKUPA [2]

Neka je   broj različitih elemenata kojima je pristupljeno između pristupa   i prethodnog puta kada je elementu   pristuplljeno. Trošak izvođenja   je  

  • DINAMIČKA TEOREMA PRSTA [3][4]

Trošak izvođenja    

  • TEOREMA SKENIRANjA [5]

Takođe poznata kao Teorema uzastopnog pristupa. Pristupanje   elemenata u raširenom drvu u simetrišnom redu staje   vremena, bez obzira na početnu strukturu raširenog drveta. Najbliža gornja granica koja je dokazana je  

Pretpostavka dinamičke optimalnostiUredi

Kao dodatak dokazanim garancijama za performanse za raširena drva, postoji i nedokazana pretpostavka velikog značaja koja potiče još od originalnih radova Sleatora i Tarjana. Ova pretpostavka je poznata kao pretpostavka dinamičke optimalnosti i u osnovi tvrdi da se raširena drva ponašaju podjednako dobro kao i sva druga binarna drva pretrage u smislu performansi do na konstantu.

Pretpostavka dinamičke optimalnosti: [2] Neka je A bilo koji algoritam binarnog drveta koji pristupa elementu   obilazeći putanju od korena do   u trošku   i da neka je moguće napraviti bilo koju rotaciju u drvetu u trošku od 1 po rotaciji. Neka je   trošak za algoritam A da izvrši niz od   pristupa. Onda je trošak raširenog drveta da izvrši iste pristupe  .

Postoji još nekoliko posledica pretpostavke dinamičke optimalnosti koje još nisu dokazane.

  • Pretpostavka obilaska: [2] Neka su   i   dva raširena drva koja sadrže iste elemente. Neka je   niz koji se dobija posećujući elemente u   u "preorder" (pretragom u dubinu) redosledu. Ukupan trošak izvođenja niza   pristupa u   je  .
  • Pretpostavka reda sa dva kraja: [5][6][7] Neka je   niz od   operacija koje se izvršavaju na redu sa dva kraja (push, pop, inject, eject). Onda je trošak izvođenja   na raširenom drvetu  
  • Pretpostavka podele: Neka je   bilo koja permutacija elemenata na raširenom drvetu. Onda je trošak brisanja elemenata u redu

  jednaka  .

ReferenceUredi

  1. ^ „Randomized Splay Trees: Theoretical and Experimental Results” (PDF). Pristupljeno 31. 5. 2011. 
  2. ^ a b v g d đ Sleator, Daniel D.; Tarjan, Robert E. (1985), „Self-Adjusting Binary Search Trees” (PDF), Journal of the ACM (Association for Computing Machinery), 32 (3): 652—686, doi:10.1145/3828.3835 
  3. ^ Cole, Richard; Mishra, Bud; Schmidt, Jeanette; and Siegel, Alan (2000), „On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences”, SIAM Journal on Computing, 30: 1—43 
  4. ^ Cole, Richard (2000), „On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof”, SIAM Journal on Computing, 30: 44—85, doi:10.1137/S009753979732699X 
  5. ^ a b Tarjan, Robert E. (1985), „Sequential access in splay trees takes linear time”, Combinatorica, 5 (4): 367—378, doi:10.1007/BF02579253 
  6. ^ Pettie, Seth (2008), „Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture”, Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, 0707: 1115—1124, Bibcode:2007arXiv0707.2160P, arXiv:0707.2160  
  7. ^ Sundar, Rajamani (1992), „On the Deque conjecture for the splay algorithm”, Combinatorica, 12 (1): 95—124, doi:10.1007/BF01191208 

Vidi jošUredi