[WikiDyd] [TitleIndex] [WordIndex

Aisd/BST

Podstawowe definicje

Drzewa poszukiwań binarnych (Binary Search Trees - BST) to drzewa binarne, w których zdefiniowane są relacje pomiędzy rodzicami i dziećmi: jeżeli LD pozostaje w określonej relacji z R, to R pozostaje w identycznej relacji z PD. Na przykład LD < R < PD.

Najwygodniej jeśli relacje są ostre. Drzewo przechowujące wiele kopii identycznych (w sensie zdefiniowanej relacji) danych realizujemy przez utrzymywanie w kazdym węźle zbioru (np. listy, tablicy) danych indentycznych.

BST zapewnieją koszt operacji (wstawianie, wyszukiwanie, usuwanie) po koszcie proporcjonalnym do wysokości drzewa. Dogodne jest więc, aby drzewo miało możliwie małą wysokośc dla określonej liczby przechowywanych danych.

Nietrudno zauważyć, że pojemność kolejnych poziomów B-drzewa rośnie tak, jak kolejne potegi liczby 2. Tak więc drzewo o h poziomach może przechować do 2h-1 węzłów wewnętrznych, a drzewo o h+1 poziomach - ponad dwukrotnie więcej (2(h+1)-1 = 2 * 2h - 1 = 2h-1 + 2^h).

Innymi słowy drzewo przechowujące n danych (mające n węzłów wewnętrznych) może mieć tylko log2(n) poziomów, o ile jest upakowane. W praktyce trudno jest osiągnąć taki wynik, ale istnieją algorytmy konstrukcji drzew zapewniające, że wysokość drzewa jest proporcjonalna do log2(n) - a to w praktyce oznacza, że algorytmy wstawiania, wyszukiwania, czy usuwania mają złożoność logarytmiczną.

Technikę pozwalającą uzyskac drzewa o h ~ log2(n) nazywamy wyważaniem.

Drzewa wyważone

Def. 1 Drzewem sciśle wyważonym nazywamy takie drzewo, w którym liczby elementów w prawym i lewym poddrzewie rozpoczynającym się w dowolnym węźle róznią się co najwyżej o jeden.

Drzewo wyważone ma optymalną głębokość: dla drzewa przechowującego n elementów wynosi ona log2(n).

Ścisłe wyważenie drzewa jest trudne do osiągnięcia, a poza tym zależy nam na rzędzie złożoności algorytmu, a więc wystarczy ograniczyć wysokość drzewa do K*log2(n), aby nie pogarszać efektywności. Okazuje się, że takie ograniczenie można osiągnąć przy mniej ostrych warunkach nakładanych na drzewo.

Przykładem może być drzewo AVL zaproponowane przez Adel'son-Vel'skiego i Landisa w 1962 roku.

Def. 2 Drzewo AVL-wyważone to takie, w którym wysokości lewego i prawego poddrzewa zaczepionych w dowolnym węźle róznią się co najwyżej o jeden.

Łatwo pokazać, że wysokość drzewa AVL o n elementach to co najwyżej log2(n)+1.

Aby skonstruować drzewo AVL dodaje się do każdego węzła jedno pole (nazwiemy je w), określające AVL-wyważenie tego węzła:

Dopuszczalnymi (tolerowanym) wartościami w sa -1,0,1.

Jeżeli dodajemy do drzewa nowy węzeł, to może to spowodować zwiększenie głębokości jednego z poddrzew i w rezultacie naruszenie tolerancji na wartość w. Na przykład w drzewie

                       8
                     /   \
                    2     10
                  /  \      \
                 1    5      12

dodanie liczby 13 spowoduje przekroczenie dopuszczalnej wartości w w węźle 10:

                       8
                     /   \
                    2     10 (+2)
                  /  \      \
                 1    5      12
                               \
                                13

Aby przywrócić AVL wyważenie musimy dokonać tak zwanego "obrotu w lewo" tego węzła:

      10(+2)                                 12(0)
        \                                  /     \
         12(+1)                  =>      10(0)  13(0)
           \
            13(0)

W efekcie takiej operacji otrzymamy AVL-drzewo:

                       8
                     /   \
                    2      12
                  /  \    /   \
                 1    5  10    13

Oczywiscie zaburzenie wyważenia może mieć charakter bardziej "globalny", niż to pokazuje przykład. W ogólnym przypadku może zaistnieć kolejność wykonania większej liczby "obrotów" - tak w lewo, jak i w prawo.

Obroty działają następująco:

           Y                                           X
         /   \             --- w prawo -->           /   \
        X      c                                    a     Y
      /  \                 <-- w lewo ---               /   \
     a     b                                           b      c

Jak widac, nie zmieniają one uporządkowania INORDER w drzewie (jest to wazne, jeśli drzewo ma pozostać drzewem poszukiwań binarnych.

Wstawianie w drzewie AVL polega więc na wykonaniu zwykłej operacji wstawienia do drzewa, a następnie szeregu obrotów, w zależności od wyważenia przed wstawieniem.

Przykład pseudokodu:

Dodawanie:

tnode_t * AVLadd(tnode_t * t, data_t x, int *plus)
{
  if (t == NULL) {  /* doszlismy do konca drzewa - tworzymy nowy wezel */
    tnode_t        *tmp = malloc(sizeof *tmp);
    if (tmp == NULL) {
      fprintf(stderr, "AVLadd - OUT OF MEMORY");
      return NULL;
    }         /* nowy wezel z wart x */
    tmp->d= x;
    tmp->w = 0;
    tmp->l = tmp->p = NULL;
    *plus = 1;
    return tmp;
  }

  if ( t->d < x )) {  /* wstaw w prawe */
    t->p = AVLadd(t->p, x, plus);
    if (*plus) {    /* prawe drzewo uroslo */
      if (t->w == -1) {  /* przedtem lewe bylo glebsze => jest ok */
        t->w++;
        *plus = 0;
      } else if (t->w == 0) /* przedtem byly rowne => jest ok */
        t->w++;
      else {    /* przedtem prawe bylo glebsze => trzeba obr. w lewo */
        t->w++;
        t = rotl(t);
        *plus = 0;
      }
    }
  } else if ( t->d > x) { /* wstaw w lewe */
    t->l = AVLadd(t->l, x, plus);
    if (*plus) {    /* lewe uroslo */
      if (t->w == 1) { /* przedtem prawe bylo glebsze => jest ok */
        t->w--;
        *plus = 0;
      } else if (t->w == 0) /* przedtem byly rowne => jest ok */
        t->w--;
      else {    /* przedtem lewe bylo glebsze => trzeba obr. w prawo */
        t->w--;
        t = rotr(t);
        *plus = 0;
      }
    }
  }
  return t;
}

Rotacja w lewo:

tnode_t * rotl(tnode_t * t)
{  
  if (t->p != NULL) {
    int dwt = 0,
        dwtp = 0;  /* zmiana wywazenia dla t i jego ppd */
     tnode_t  *tp = t->p; /* ppd musi byc ! */
     if (tp->w == -1) {   /* lpd dla ppd jest glebsze => trzeba poprawic */
       t->p = rotr(t->p);
       tp = t->p;
     }
     /* teraz wyznaczamy zmiany wag dla t i tp, zalezy to od wywazenia poprzednio */
     if (tp->w > 0)
       dwt = -2;
     else
       dwt = -1;
     if (tp->w > 0 && tp->w - t->w >= 0 || t->w <= 0 && tp->w <=0)
       dwtp = -2;
     else
       dwtp = -1;

     /* nowe wywazenia */
     t->w += dwt;
     tp->w += dwtp;
     /* i sam obrot: */
     t->p = tp->l;
     tp->l = t;
     return tp;
  } else
    return t; /* nie mozna rotowac, o nie ma ppd */
}

Analiza zmian wag w powyzszym kodzie wymaga przeanalizowania możliwych topoligii drzewa. Zobaczmy to na przykładzie procedury rotr:

Idea:

          A              B
         / \            / \
        B   h3  =>    h1   A
       / \                / \
     h1   h2            h2   h3

Algorytm:

     t= &A;
     tp= t->left;        /* tp wskazuje B */
     t->left= tp->right; /* h2 staje sie lpd A */
     tp->right= t;       /* A staje sie ppd B */

Zmiana wag:

wA na pewno wzrośnie, bo jego lpd stanie się płytsze. Jeżeli h1 było wyższe, niż h2, to wA wzośnie o 2, w przeciwnym wypadku wzrośnie o 1. Różnicę głębokości h1 i h2 określa wB: wB= h2 - h1, a więc:

if wB < 0 
  wA += 2
else
  wA += 1

wB na pewno wzrośie, bo jego ppd urośnie. Jeżeli h3 było głębsze niż h2, to wB wzrośnie o 2, w przeciwnym razie o 1. Aby stwierdzić, czy h3 jest głębsze niż h2 trzeba zbadać wyważenie A:

Trzeba rozważyć dwa przypadki:

a) wB < 0 <=> max(h1,h2) = h1, h1 = h2-wB

b) wB >= 0 <=> max(h1,h2) = h2

Podsumowując: h3 > h2 if wB < 0 && ( wA - wB ) >= 0 || wB >= 0 && wA >= 0

czyli:

if wB < 0 && ( wA - wB ) >= 0 || wB >= 0 && wA >= 0
  wB += 2
else
  wB += 1

Z tego, że wB wzrośnie wynika konieczność sprawdzenia wyważenia drzewa B i ewentualne wyważenie go tak, aby wB bylo < 1.

Osiągamy to przez rotację w lewo drzewa B i dlatego rotr jest funkcja pośrednio rekurencyjną: wywołuje rotl, a to z kolei może wywoływać rotr, itd aż do zejścia na sam dół drzewa. Dlatego czasem przywrócenie równowagi może wymagać log(n) rotacji (po pojedynczym wstawieniu/usunięciu).

Z powyższego względu przewagę nad AVL-drzewami mają drzewa czerwono-czarne.

Def. 3

Drzewem czerwono-czarnym (DCC, Red-Black Tree RBT) nazywamy takie drzewo poszukiwań binarnych, w którym:

DCC musi w każdym wezle przechowywac informację o kolorze (wystarczy 1 bit).

W DCC definiujemy czarna głebokość: liczbę czarnych węzłów na prostej ścieżce z danego węzła x do liścia (bez tego węzła). Jak wynika z własności d), możemy wybrać dowolną ścieżkę. czarną głębokość oznaczymy dalej przez b(x).

Pokażemy indukcyjnie, że poddrzewo z węzła x ma co najmniej 2^{b(x)}-1 węzłów wewnętrznych. Będzie to potrzebne do znalezienia ograniczenia na głębokość DCC o n węzłach.

Dowód indukcyjny: Krok 0: dla b(x) == 0 mamy x - liść a więc takie poddrzewo zawiera 2^{0} - 1 = 0 wezłów wewnętrznych.

Krok 1: x ma dwa poddrzewa: xl i xp, liczby węzłów w tych poddrzewach to nie mniej niż

Liczba węzłów w drzewie x to suma powyższych plus 1 (węzeł x)

co było do okazania.

Jeżeli przez h oznaczymy głębokość DCC to z własności c) wynika, że b >= h/2

Ponieważ drzewo ma co najmniej 2^b-1 węzłów, a więc

co znaczy, ze wysokość DCC o n elementach jest nie większa, niż 2*log(n+1) (a więc rzędu log(n)). Operacje na takim drzewie będą też miały złożoność O(log(n)).

Przewaga DCC nad AVL-drzewami polega na tym, że przywrócenie własności CC po wstawieniu/usunięciu węzła wymagają co najwyżej dwóch rotacji. Nie będziemy zajmować sie tutaj dokładnie analizą wszystkich możliwych sytuacji, wnikliwi mogą znaleźć to w ksiażce Cormena i spółki na stronach 310-315.


2015-09-23 06:32