Rašireno drvo
<s>Rašireno drvo je samopodešavajuće binarno drvo pretrage sa dodatnim svojstvom da se nedavno pristupljenim elementima brzo pristupa iznova.</s><s>Ovo drvo je u mogućnosti da obavlja operacije kao što su umetanje, traženje i brisanje u amortizovanom vremenu O (log n).</s><s>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.</s><s>Rašireno drvo su osmislili Daniel Dominic Sleator i Robert Endre Tarjan 1985. godine.</s>

<s>Sve uobičajene operacije nad binarnim stablom su kombinovane sa jednom osnovnom operacijom koja se zove širenje.</s><s>Širenje drveta za određeni element sređuje drvo tako da je taj element smešten u koren drveta.</s><s>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.</s><s>Alternativno, algoritam tipa odozdo-nagore može kombinovati pretragu i prepoznavanje drvata u jednu fazu.</s>

<s>Prednosti 
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.</s><s>Visina stabla u najgorem slučaju --- iako neverovatna --- je O(n), dok je prosečna O(log n).</s><s>Č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).</s>

<s>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.</s><s>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.</s><s>Čak i sa identičkim ključevima, performanse ostaju amortizovano O(log n).</s><s>Sve operacije nad drvetom održavaju redosled identičkih ključeva u drvetu, što je svojstvo slično stabilnim algoritmima sortiranja.</s><s>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č.</s>

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

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

<s>Operacije</s>

<s>Širenje 
Kada se pristupa čvoru x, operacija širenja se izršava nad x kako bi ga pomerila do korena.</s><s>Kako bismo izvršili operaciju širenja, izvodimo niz koraka širenja, od čega svaki pomera x bliže korenu.</s><s>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.</s>

<s>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</s>

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

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

<s>Cik korak: Ovaj korak se vrži kada je  koren.</s><s>Drvo se rotira u odnosu na granu između  i .</s><s>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.</s>

<s>Cik-cik korak: Ovaj korak se vrši kada  nije koren i  i  su oba desni sinovi ili su oba levi sinovi.</s><s>Slika iskod ilustruje slučaj kada su  i  oba levi sinovi.</s><s>Drvo se rotira u odnosu na granu koja spaja  sa svojim ocem , i potom se rotira u odnosu na granu koja spaja  i .</s><s>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.</s>

<s>Cik-cak korak: Ovaj korak se vrši kada  nije koren i kada je  desno dete i  je levo dete svog oca ili obratno.</s><s>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).</s>

<s>Umetanje 
Kako bismo umetnuli čvor  u rašireno drvo:
 Prvo vršimo umetanje kao da je u pitanju uobičajeno binarno drvo pretrage.</s><s>Potom „širimo“ umetnuti čvor  do vrha drveta.</s>

<s>Brisanje 
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.</s><s>Onda brišemo taj čvor (čija je vrednost sada u čvoru ).</s><s>Na ovaj način, brisanje je pojednostavljeno na problem brisanja čvora bez sinova ili sa jednim sinom.</s>

<s>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.</s><s>Ova operacija deli početno drvo na dva poddrveta.</s><s>Sada se jednostavno najveći element levog poddrveta širi do vrha (METODA 1) ili se najmanji element desnog poddrveta (METODA 2) širi do vrha.</s><s>Desno poddrvo postaje desno dete rezultujećeg levog poddrveta (za METODU 1).</s><s>Koren levog poddrveta je koren spojenog drveta.</s>

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

<s>#include <functional></s>

<s>#ifndef SPLAY_TREE
#define SPLAY_TREE</s>

<s>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; }
};</s>

<s>#endif // SPLAY_TREE</s>

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

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

<s>Teoreme o performansama 
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.</s><s>BALANS TEOREMA 
	Trošak izvođenja niza operacija je 
 TEOREMA STATIČKE OPTIMALNOSTI 
	Neka  predstavlja broj pristupa elementu  u .</s><s>Trošak izvođenja  je 
	.</s><s>Drugim rečima, raširena drva imaju performanse slične optimalnim statičkim 		binarnim drvima pretrage na nizovima od najmanje  pristupa.</s><s>STATIČKA PRST TEOREMA 
	Neka  element kome je pristupljeno u -om pristupu u nizu  i neka je  bilo koji fiksni element (prst).</s><s>Trošak 		ivođenja  je 
 TEOREMA RADNOG SKUPA 
	Neka je  broj različitih elemenata kojima je pristupljeno između pristupa  i prethodnog puta kada je elementu  		pristuplljeno.</s><s>Trošak izvođenja  je 
 DINAMIČKA TEOREMA PRSTA 
	Trošak izvođenja  
 TEOREMA SKENIRANjA 
	Takođe poznata kao Teorema uzastopnog pristupa.</s><s>Pristupanje  elemenata u raširenom drvu u simetrišnom redu staje 
	vremena, bez obzira na početnu strukturu raširenog drveta.</s><s>Najbliža gornja granica koja je dokazana je</s>

<s>Pretpostavka dinamičke optimalnosti 
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.</s><s>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.</s>

<s>Pretpostavka dinamičke optimalnosti:  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.</s><s>Neka je  trošak za algoritam A da izvrši niz od  pristupa.</s><s>Onda je trošak raširenog drveta da izvrši iste 		pristupe .</s>

<s>Postoji još nekoliko posledica pretpostavke dinamičke optimalnosti koje još nisu dokazane.</s><s>Pretpostavka obilaska:  Neka su  i  dva raširena drva koja sadrže iste elemente.</s><s>Neka je  niz koji se dobija 		posećujući elemente u  u "preorder" (pretragom u dubinu) redosledu.</s><s>Ukupan trošak izvođenja niza  pristupa u  je .</s><s>Pretpostavka reda sa dva kraja:  Neka je  niz od  operacija koje se izvršavaju na redu sa dva kraja (push, pop, inject, 		eject).</s><s>Onda je trošak izvođenja  na raširenom drvetu 
 Pretpostavka podele: Neka je  bilo koja permutacija elemenata na raširenom drvetu.</s><s>Onda je trošak brisanja elemenata u redu
	 jednaka .</s>

<s>Reference</s>

<s>Vidi još 
 Binarno stablo
 AVL-stablo
 B-stablo</s>

<s>Binarna stabla</s>

