Раширено дрво

Из Википедије, слободне енциклопедије


Раширено дрво је самоподешавајуће бинарно дрво претраге са додатним својством да се недавно приступљеним елементима брзо приступа изнова. Ово дрво је у могућности да обавља операције као што су уметање, тражење и брисање у амортизованом времену О (log n). За многе низове неслучајних операција, раширена дрво имају боље перформансе него друга дрва за претрагу, чак и када је специфичан образац низа података непознат. Раширено дрво су осмислили Daniel Dominic Sleator и Robert Endre Tarjan 1985. године.

Све уобичајене операције над бинарним стаблом су комбиноване са једном основном операцијом која се зове ширење. Ширење дрвета за одређени елемент сређује дрво тако да је тај елемент смештен у корен дрвета. Један начин да се ово уради је да прво извршимо уобичајену претрагу бинарног стабла како бисмо пронашли елемент који је у питању и онда применимо ротације дрвета на одређени начин како бисмо довели елемент до врха. Алтернативно, алгоритам типа одоздо-нагоре може комбиновати претрагу и препознавање дрвата у једну фазу.

Предности[уреди]

Добре перофрмансе за раширено дрво зависе од чињенице да је самооптимизујуче, у смислу да се чворови којима се често приступа померају ближе корену, где им се може приступити брже. Висина стабла у најгорем случају --- иако невероватна --- је O(n), док је просечна O(log n). Чињеница да су често коришћени чворови близу корена је предност за готово све практичне апликације и посебно је корисна за имплементацију кешева и алгоритама за „скупљање ђубрета“ (рециклирање меморије која програму више није потребна).


Неке од предности су:

  • Једноставна имплементација --- једноставнија него друга самобалансирајућа бинарна стабла претраге, попут црвено-црних или АВЛ-стабала
  • Упредиве перформасе --- анализа средњег случаја даје исте резултате као за друга стабла
  • Мало заузеће меморије --- раширена стабла не морају да чувају никакве додатне податке како би се самобалансирала
  • Могућност креирања сталне структуре података од раширених стабала --- која омогућава да се приступи и претходној и новој верзији након ађурирања. Ово мође бити корисно у функционалном програмирању и треба амортизован O(log n) додатни меморијски простор по ажурирању
  • Добро ради са чворовима који садржие идентичке кључеве --- у супротности са другим типовима самобалансирајућих стабала. Чак и са идентичким кључевима, перформансе остају амортизовано O(log n). Све операције над дрветом одржавају редослед идентичких кључева у дрвету, што је својство слично стабилним алгоритмима сортирања. Добро осмишљена операција тражења може да врати чвор који је највише лево или чвор који је највише десно за дати кључ.


Мане[уреди]

Најзначајнија мана раширених дрвета је та што висина раширеног дрвета може бити линеарна. На пример, ово ће бити случај после приступања сваком од n елемената у неопадајућем редоследу. Како висина дрвета одговара времену приступа у најгорем случају, то знали да ће стварни трошак ове операције бити прилично висок. Међутим, амортизовани трошак најгорег случаја је логаритамски, O(log n). Такође, очекивани трошак приступа може бити смањен на O(log n) користећи насумичну варијанту раширеног дрвета.[1]

Раширено дрво може бити горе од статичког дрвета за највише константан фактор.

Операције[уреди]

Ширење[уреди]

Када се приступа чвору x, операција ширења се изршава над x како би га померила до корена. Како бисмо извршили операцију ширења, изводимо низ корака ширења, од чега сваки помера x ближе корену. Извођењем операције ширења над чвором који нас занима након сваког приступа, недавно приступљени чворови се држе ближе корену и дрво остаје балансирано, чиме смо постигли амортизовану временску сложеност у обећаним границама.

Сваки корак зависи од три фактора

  • Да ли је x лево или десно дете свог оца, чвора o
    • Да ли је o корен или не, и ако није
      • Да ли је o лево или десно дете свог оца, чвора d

Такође, важно је не заборавити да подесимо да dd ("прадеда“ чвора x) сада показује на x након сваке операције ширења. Ако dd не постоји, онда је x очигледно корен, и као такав на корен мора бити постављен.

Постоји три врсте операција ширења, од којих свака има „леви“ и „десни“ случај. Како би овај текст био сажетији, само један од случајева је приказан за сваку врсту. Те врсте су:

Цик корак: Овај корак се вржи када је o корен. Дрво се ротира у односу на грану између x и o. Цик кораци постоје како би се обрадили изузети случајеви парности и биће рађени само као последњи корак у операцији ширења и само кад x има дубину која је непаран број на почетку операције.

Цик-цик корак: Овај корак се врши када o није корен и x и o су оба десни синови или су оба леви синови. Слика искод илуструје случај када су x и o оба леви синови. Дрво се ротира у односу на грану која спаја o са својим оцем d, и потом се ротира у односу на грану која спаја x и o. Приметите да су цик-цик кораци једино што одваја раширена дрвета од методе ротирај до корена коју су представили Ален и Мунро пре него што су раширена дрва предтавњена.

Цик-цак корак: Овај корак се врши када o није корен и када је x десно дете и o је лево дете свог оца или обратно. Дрво се ротира у односу на грану која је између o и x, и онда се ротира у односу на резултујучу грану између x и g. (слика).

Уметање[уреди]

Како бисмо уметнули чвор x у раширено дрво:

  1. Прво вршимо уметање као да је у питању уобичајено бинарно дрво претраге.
  2. Потом „ширимо“ уметнути чвор x до врха дрвета.

Брисање[уреди]

Како бисмо обрисали чвор x, користимо исти метод као у случају бинарног стабла претраге: ако x има два сина, заменимо његову вредност било са највећим чвором у левом подстаблу или са најмањим чвором у десном подстаблу. Онда бришемо тај чвор (чија је вредност сада у чвору x). На овај начин, брисање је поједностављено на проблем брисања чвора без синова или са једним сином.

За разлику од бинарног дрва претраге, у раширеном дрву, ширимо оца обрисаног чвора до врха дрвета ИЛИ чвор који треба да буде обрисан је прво раширен, тј. постављен да буде корен дрвета и онда се брише. Ова операција дели почетно дрво на два поддрвета. Сада се једноставно највећи елемент левог поддрвета шири до врха (МЕТОДА 1) или се најмањи елемент десног поддрвета (МЕТОДА 2) шири до врха. Десно поддрво постаје десно дете резултујећег левог поддрвета (за МЕТОДУ 1). Корен левог поддрвета је корен спојеног дрвета.

Имплементација[уреди]

Испод је имплементација раширених дрва у програмском језику C++, која користи показиваче да представи сваки чвор дрвета. Ова имплеметнација је базирана на другој методи брисања у раширено дрву. Такође, супротно претходним дефиницијама, ова C++ верзија НЕ шири дрво после операција претраге - дрво се шири само на уметањима и брисањима.

#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


Анализа[уреди]

Једноставна амортизована анализа статичких раширених дрва може се извести користећи потенцијални метод. Претпоставимо да је \mathbf{vel}(k) број чворова поддрвета чији је корен k (укључујући k) и \mathbf{red}(k) = \log_2(\mathbf{vel}(k)). Тада је потенцијална функција P(t) за раширено дрво d сума свих редова свих чворова у дрвету. Ова суме има тенденцију да буде велика за лоше балансирана дрва, и ниска за добро балансирана дрва. Можемо ограничити амортизован трошак било које цик-цик или цик-цак операције помоћу

\text{amortizovan trosak} = \text{trosak} + P(d_p) - P(d_n) \leq 3(red_p(x) - red_n(x))

где је x чвор који треба померити до корена и индекси p и n значе пре и након операције, редом. Када се сумира читава операција ширења, телескопским методом се добија да је та сума 3(\mathbf{red}(k)) што је у ствари O(\log n). Како може постојати највише једна цик операција, ово додаје само константу.

Теореме о перформансама[уреди]

Постоји неколико теорема и претпоставки које се тичу најгорег случаја за извођење низа N од m приступа у раширеном дрвету које садржи n елемената.

  • БАЛАНС ТЕОРЕМА [2]

Трошак извођења низа операција је O\left[m(1 + \log n) + n \log n\right]

  • ТЕОРЕМА СТАТИЧКЕ ОПТИМАЛНОСТИ [2]

Нека q_i представља број приступа елементу i у S. Трошак извођења S је O\left[m + \sum_{i=1}^{n} q_{i} \log \frac{m}{q_i}\right]. Другим речима, раширена дрва имају перформансе сличне оптималним статичким бинарним дрвима претраге на низовима од најмање n приступа.

  • СТАТИЧКА ПРСТ ТЕОРЕМА [2]

Нека i_j елемент коме је приступљено у j-ом приступу у низу S и нека је f било који фиксни елемент (прст). Трошак ивођења S је  O\left[m + n \log n + \sum_{j=1}^{m} \log(|i_j - f| + 1) \right]

  • ТЕОРЕМА РАДНОГ СКУПА [2]

Нека је t(j) број различитих елемената којима је приступљено између приступа j и претходног пута када је елементу i_j приступлљено. Трошак извођења S је  O\left[m + n \log n + \sum_{j=1}^{m} \log(t(j)+ 1) \right]

  • ДИНАМИЧКА ТЕОРЕМА ПРСТА [3][4]

Трошак извођења S  O\left[m + n + \sum_{j=1}^{m} \log(|i_j+1 - i_j| + 1) \right]

  • ТЕОРЕМА СКЕНИРАЊА [5]

Такође позната као Теорема узастопног приступа. Приступање n елемената у раширеном дрву у симетришном реду стаје O(n) времена, без обзира на почетну структуру раширеног дрвета. Најближа горња граница која је доказана је 4.5n


Претпоставка динамичке оптималности[уреди]

Као додатак доказаним гаранцијама за перформансе за раширена дрва, постоји и недоказана претпоставка великог значаја која потиче још од оригиналних радова Слеатора и Тарјана. Ова претпоставка је позната као претпоставка динамичке оптималности и у основи тврди да се раширена дрва понашају подједнако добро као и сва друга бинарна дрва претраге у смислу перформанси до на константу.

Претпоставка динамичке оптималности: [2] Нека је А било који алгоритам бинарног дрвета који приступа елементу x обилазећи путању од корена до x у трошку d(x) + 1 и да нека је могуће направити било коју ротацију у дрвету у трошку од 1 по ротацији. Нека је A(S) трошак за алгоритам А да изврши низ од S приступа. Онда је трошак раширеног дрвета да изврши исте приступе O\left[n + A(S)\right].

Постоји још неколико последица претпоставке динамичке оптималности које још нису доказане.

  • Претпоставка обиласка: [2] Нека су D_1 и D_2 два раширена дрва која садрже исте елементе. Нека је S низ који се добија посећујући елементе у D_2 у "preorder" (претрагом у дубину) редоследу. Укупан трошак извођења низа S приступа у D_1 је O(n).
  • Претпоставка реда са два краја: [5][6][7] Нека је S низ од m операција које се извршавају на реду са два краја (push, pop, inject, eject). Онда је трошак извођења S на раширеном дрвету O(m+n)
  • Претпоставка поделе: Нека је S било која пермутација елемената на раширеном дрвету. Онда је трошак брисања елемената у реду

S једнака O(n).

Референце[уреди]

  1. ^ „Randomized Splay Trees: Theoretical and Experimental Results“ Приступљено 31. 5. 2011.. 
  2. ^ а б в г д ђ Sleator, Daniel D.; Tarjan, Robert E. (1985), „Self-Adjusting Binary Search Trees“, 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. ^ а б 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, arXiv:0707.2160, Bibcode 2007arXiv0707.2160P 
  7. ^ Sundar, Rajamani (1992), „On the Deque conjecture for the splay algorithm“, Combinatorica 12 (1): 95-124, DOI:10.1007/BF01191208 

Види још[уреди]