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

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

## Operacije
### Širenje
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 levo ili desno dete svog oca, čvora o
** Da li je 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
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
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
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.


```cpp
#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
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
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 
	Trošak izvođenja niza operacija je O\left[m(1 + \log n) + n \log n\right]
* TEOREMA STATIČKE OPTIMALNOSTI 
	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 
	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 
	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 
	Trošak izvođenja S  O\left[m + n + \sum_{j=1}^{m} \log(|i_j+1 - i_j| + 1) \right] 
* TEOREMA SKENIRANjA 
	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
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: 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: 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: 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

## Povezano
* Binarno stablo
* AVL-stablo
* B-stablo