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.

Prednosti[uredi | uredi izvor]

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č.

Mane[uredi | uredi izvor]

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.

Operacije[uredi | uredi izvor]

Širenje[uredi | uredi izvor]

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 $x$ $x$ levo ili desno dete svog oca, čvora $o$ $o$
- Da li je $o$ $o$ koren ili ne, i ako nije
  - Da li je $o$ levo ili desno dete svog oca, čvora $d$

Takođe, važno je ne zaboraviti da podesimo da $dd$ ("pradeda“ čvora $x$ ) sada pokazuje na x nakon svake operacije širenja. Ako $dd$ ne postoji, onda je $x$ 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 $o$ koren. Drvo se rotira u odnosu na granu između $x$ i $o$ . 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 $x$ ima dubinu koja je neparan broj na početku operacije.

Cik-cik korak: Ovaj korak se vrši kada $o$ nije koren i $x$ i $o$ su oba desni sinovi ili su oba levi sinovi. Slika iskod ilustruje slučaj kada su $x$ i $o$ oba levi sinovi. Drvo se rotira u odnosu na granu koja spaja $o$ sa svojim ocem $d$ , i potom se rotira u odnosu na granu koja spaja $x$ i $o$ . 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 $o$ nije koren i kada je $x$ desno dete i $o$ je levo dete svog oca ili obratno. Drvo se rotira u odnosu na granu koja je između $o$ i $x$ , i onda se rotira u odnosu na rezultujuču granu između $x$ i $g$ . (slika).

Umetanje[uredi | uredi izvor]

Kako bismo umetnuli čvor $x$ u rašireno drvo:

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

Brisanje[uredi | uredi izvor]

Kako bismo obrisali čvor $x$ , koristimo isti metod kao u slučaju binarnog stabla pretrage: ako $x$ 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 $x$ ). 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.

Implementacija[uredi | uredi izvor]

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

Analiza[uredi | uredi izvor]

Jednostavna amortizovana analiza statičkih raširenih drva može se izvesti koristeći potencijalni metod. Pretpostavimo da je $\mathbf {vel} (k)$ broj čvorova poddrveta čiji je koren $k$ (uključujući $k$ ) i $\mathbf {red} (k)=\log _{2}(\mathbf {vel} (k))$ . Tada je potencijalna funkcija $P(t)$ za rašireno drvo $d$ 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

${\text{amortizovan trosak}}={\text{trosak}}+P(d_{p})-P(d_{n})\leq 3(red_{p}(x)-red_{n}(x))$

gde je $x$ čvor koji treba pomeriti do korena i indeksi $p$ i $n$ znače pre i nakon operacije, redom. Kada se sumira čitava operacija širenja, teleskopskim metodom se dobija da je ta suma $3(\mathbf {red} (k))$ što je u stvari $O(\log n)$ . Kako može postojati najviše jedna cik operacija, ovo dodaje samo konstantu.

Teoreme o performansama[uredi | uredi izvor]

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

BALANS TEOREMA ^[2]

Trošak izvođenja niza operacija je $O\left[m(1+\log n)+n\log n\right]$

TEOREMA STATIČKE OPTIMALNOSTI ^[2]

Neka $q_{i}$ predstavlja broj pristupa elementu $i$ u $S$ . Trošak izvođenja $S$ je $O\left[m+\sum _{i=1}^{n}q_{i}\log {\frac {m}{q_{i}}}\right]$ . Drugim rečima, raširena drva imaju performanse slične optimalnim statičkim binarnim drvima pretrage na nizovima od najmanje $n$ pristupa.

STATIČKA PRST TEOREMA ^[2]

Neka $i_{j}$ element kome je pristupljeno u $j$ -om pristupu u nizu $S$ i neka je $f$ bilo koji fiksni element (prst). Trošak ivođenja $S$ je $O\left[m+n\log n+\sum _{j=1}^{m}\log(|i_{j}-f|+1)\right]$

TEOREMA RADNOG SKUPA ^[2]

Neka je $t(j)$ broj različitih elemenata kojima je pristupljeno između pristupa $j$ i prethodnog puta kada je elementu $i_{j}$ pristuplljeno. Trošak izvođenja $S$ je $O\left[m+n\log n+\sum _{j=1}^{m}\log(t(j)+1)\right]$

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

Trošak izvođenja $S$ $O\left[m+n+\sum _{j=1}^{m}\log(|i_{j}+1-i_{j}|+1)\right]$

TEOREMA SKENIRANjA ^[5]

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

Pretpostavka dinamičke optimalnosti[uredi | uredi izvor]

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 $x$ obilazeći putanju od korena do $x$ u trošku $d(x)+1$ i da neka je moguće napraviti bilo koju rotaciju u drvetu u trošku od 1 po rotaciji. Neka je $A(S)$ trošak za algoritam A da izvrši niz od $S$ pristupa. Onda je trošak raširenog drveta da izvrši iste pristupe $O\left[n+A(S)\right]$ .

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

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

$S$ jednaka $O(n)$ .

Reference[uredi | uredi izvor]

^ „Randomized Splay Trees: Theoretical and Experimental Results” (PDF). Pristupljeno 31. 5. 2011.
^ ^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
^ 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
^ 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
^ ^a ^b Tarjan, Robert E. (1985), „Sequential access in splay trees takes linear time”, Combinatorica, 5 (4): 367—378, doi:10.1007/BF02579253
^ 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 
^ Sundar, Rajamani (1992), „On the Deque conjecture for the splay algorithm”, Combinatorica, 12 (1): 95—124, doi:10.1007/BF01191208

Vidi još[uredi | uredi izvor]

[1] „Randomized Splay Trees: Theoretical and Experimental Results” (PDF). Pristupljeno 31. 5. 2011.

[SleatorTarjan-2] 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

[ColeEtAl-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

[Cole-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

[Tarjan-5] Tarjan, Robert E. (1985), „Sequential access in splay trees takes linear time”, Combinatorica, 5 (4): 367—378, doi:10.1007/BF02579253

[Pettie-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 

[Sundar-7] Sundar, Rajamani (1992), „On the Deque conjecture for the splay algorithm”, Combinatorica, 12 (1): 95—124, doi:10.1007/BF01191208

[1]

[2]

[3]

[4]

[5]

[6]

[7]