DRZEWA CZERWONO-CZARNE


CO trzeba umieć:




//////////////////////////////////////////////////////////////////


To kolejny typ drzew przeszukiwań binarnych(BST) i podobnie jak drzewa AVL jest drzewem samoorganizującym się. Oznacza to, że również będziemy dokonywać rotacji.

W drzewie czerwono-czarnym z każdym węzłem powiązany jest dodatkowy atrybut, kolor, który może być czerwony lub czarny. Oprócz podstawowych własności drzew poszukiwań binarnych, wprowadzone zostały kolejne wymagania, które trzeba spełniać:
  1. Każdy węzeł jest czerwony lub czarny.
  2. Korzeń jest czarny.
  3. Każdy liść jest czarny (Można traktować NULL jako liść).
  4. Jeśli węzeł jest czerwony, to jego synowie muszą być czarni.
  5. Każda ścieżka z ustalonego węzła do liścia liczy tyle samo czarnych węzłów.
Wymagania te gwarantują, że najdłuższa ścieżka od korzenia do liścia będzie co najwyżej dwukrotnie dłuższa, niż najkrótsza.
Ogólnie zasada działania drzew RB (Red-Black) jest bardzo prosta, gdyż jest taka sama, jak przy drzewach AVL. Dodajemy lub kasujemy element drzewa, a następnie sprawdzamy, czy nasze 5 własności zachodzi jeśli tak to jesteśmy happy i kontynuujemy. Natomiast jeśli jakaś własność się nie zgadza to musimy poczynić czynności, aby to naprawić. W ogólności sprowadza się to do rotacji elementów. Teraz mam nadzieję, że się ucieszysz, bo to są jakie same rotacje jak przy drzewach AVL (rotacja RR i LL). Tylko oczywiście warunki są inne, bo nie mamy współczynnika bf tylko kolor elementów. No, ale teraz wszystko na spokojnie i po pomalutku :D.


1.Dodawanie elementu
Samo dodawanie elementu jest proste, ponieważ tak dodajemy go tak samo jak do drzewa BST (tak samo również robiliśmy przy drzewach AVL). Następnie kolor naszego nowego elementu ustalamy na czerwony (R-red). Po dodaniu elementu musimy sprawdzić czy nasze drzewo spełnia własności drzewa RB.
Czyli jak dodajemy pierwszy element to on staje się korzeniem, a korzeń zawsze jest czarny (B-black). Więc zmieniamy kolor naszego elementu na czarny i kończymy. To jest ten przypadek najłatwiejszy. Ponieważ w następnych przypadkach musimy sprawdzać relacje między elementami.


Więc musimy rozpatrywać tylko 6 przypadków :P. Nie no nie bój się tak :). Bo w zasadzie tych przypadków jest 3 (bo pozostałe 3 to przypadki lustrzane), a tak naprawdę to nawet nie, bo te przypadki się łączą ze sobą, więc jest łatwo :D.

I przypadek:










Nasz nowy element X jest synem elementu czerwonego B oraz jego wujek (brat B, czyli drugi syn A) też jest czerwony.

W tej sytuacji zamieniamy kolory elementów B,C i A na przeciwne, a za X przyjmujemy element A (X=A) i rozpatrujemy przypadek jeszcze raz (wszystko od nowa).












Jeśli element A jest korzeniem naszego drzewa to w takim razie ponownie ustawiamy kolor elementu A na czarny i kończymy wstawianie.(Mamy sytuację w której elementy A,B,C są czarne ale to nie zakłóca własności drzewa RB).

II przypadek:












Element X jest prawym synem czerwonego węzła B, a jego wujek C jest czarny. W takim przypadku musimy dokonać tylko rotacji.

 








Czyli dokonujemy rotacji w lewo (jest to nasza rotacja RR której używaliśmy przy drzewach AVL) względem węzła B. Następnie przychodzimy do kolejnego przypadku.

III przypadek:













Teraz rozpatrujemy sytuację, w której nasz element X jest lewym synem czerwonego węzła X (może tak myć po dokonaniu rotacji z przypadku II lub z powodu takiego dodania elementu). Teraz musimy ponownie dokonać rotacji. 
 











Dokonujemy rotacji w prawo (nasza rotacja LL) względem węzła A. Następnie musimy zamienić kolory elementów A i B na przeciwny.

 












Po zamianie kolorów kończymy wstawianie i nasze drzewo spełnia warunki drzewa RB. Następnie musimy rozważyć przypadki lustrzane. Czyli ponownie 3 przypadki, ale praktycznie takie same, więc po zapoznaniu się z kodem, nie powinno być problemu :D.

Struktura drzewa RB:

struct treeRB{
     int key; // klucz
     char color; // kolor
     struct treeRB *left, *right, *parent; // powiązania
};

KOD:
// rotacje //
void RR(struct treeRB **root, struct treeRB *A){

     struct treeRB *B=A->right, *p=A->parent;

     A->right = B->left;
     if(A->right) A->right->parent = A;

     B->left=A;
     B->parent=p;
     A->parent=B;

    if(p){
        if(p->left == A) p->left=B;
        else p->right=B;
    }
    else *root=B;
}

void LL(struct treeRB ** root, struct treeRB *A){

    struct treeRB *B=A->left, *p=A->parent;

    A->left=B->right;
    if(A->left) A->left->parent=A;

    B->right=A;
    B->parent=p;
    A->parent=B;

    if(p){
        if(p->left==A) p->left=B;
        else p->right = B;
    }
     else *root = B;
}

//

To są takie same rotacje, jak przy drzewach AVL. Jedyną różnicą jest fakt że nazwa struktury jest inna, no bo przecież tworzymy drzewo czerwono-czarne, a nie AVL.



void addRB(struct treeRB **root, int key){
// funkcja główna naszego dodawania
   struct treeRB *nowy_element,*p=NULL,*d,*x,*y;
   // dodawanie elementu tak jak do BST
    nowy_element = (struct treeRB *)malloc(sizeof(struct treeRB));
    nowy_element->left = nowy_element->right = nowy_element->parent = NULL;
    nowy_element->key = key;
    nowy_element->color = 'R';
    d=*root;
   if(!d){
         nowy_element->parent=NULL;
         nowy_element->color='B';
         *root=nowy_element;
       }
      else{
         while(d){
             if(d->key > key){
                   p=d;
                   d=d->left;
             }else if(d->key < key){
                    p=d;
                    d=d->right;
             }else break;
         }
         if(!d){
             if(p->key>key) p->left=nowy_element;
             else p->right=nowy_element;
             nowy_element->parent=p;
         }
         //

         if(p && p->color=='R'){
      // jeżeli dodało element, a rodzic tego elementu jest czerwony
              
             x=nowy_element;
             while(x){
        // pętla ponieważ pierwszy przypadek dopuszcza przejście na wyższy poziom drzewa

                   p=x->parent; // p-rodzic naszego x

                   if(p->parent){
             // ustalamy który przypadek lustrzany zachodzi
                          if(p->parent->left==p) y=p->parent->right;
                          else if(p->parent->right==p) y=p->parent->left;
                   }else y=NULL;

                   if(y && y->color=='R' && p->color=='R'){ // I przypadek
                          p->color=y->color='B';
                          if(p->parent==*root) break;

                          p->parent->color='R';
                          if(p)x=p->parent;
                    }else{
                         if(p->parent && y==p->parent->right){
                 // I przypadek lustrzany
                                 if(p->color=='R'){
                                         if(p->right==x) RR(root,p); // II przypadek

                                         LL(root,p->parent); // III przypadek
                                         x->parent->color='B';
                                         x->parent->right->color='R';
                                 }

                          }else if(p->parent && y==p->parent->left){
                          // II przypadek lustrzany
                                  if(p->color=='R'){
                                         if(p->left==x) LL(root,p); // II przypadek

                                         RR(root,p->parent); // III przypadek
                                         x->parent->color='B';
                                         x->parent->left->color='R';
                                   }
                           }
                           break; // wyjście z pętli
                   }
               }
          }
      }
}


Jak widzisz to wcale nie jest skomplikowane tym bardziej że 70% z tego już umiesz, prawda :D ? No bo tak, rotacje już były omawiane, dodawanie elementu do drzewa BST to jest już pikuś. Jedyną nową rzeczą jest ustalenie jaki przypadek zachodzi i dokonanie rotacji. Te przypadki również już omawiałem, a tu jest jedynie zastosowanie tego w praktyce. Tylko należało pamiętać aby pilnować tych elementów i rozpatrzeć takie sytuacje, w których któryś z elementów nie istnieje, bo przecież wtedy nie możemy się do niego odwołać. Dlatego w kodzie jest tyle if-ów i są w nich dość złożone warunki. Myślę, że jak popatrzysz na rysunki powyżej, a potem na kod to już wszystko będzie jasne :).

2.usuwanie elementu

Z usuwaniem elementu jest w zasadzie prosta sprawa. Najpierw kasujemy element tak samo, jak przy zwykłem BST. Następnie sprawdzamy, czy nie popsuliśmy drzewka. Więc musimy rozpatrzeć te nasze przypadki tak samo jak przy dodawaniu. Więc nowości tutaj praktycznie nie ma.


KOD:

struct treeRB* delKey(struct treeRB **root, int key){
   if(*root!= NULL){
              if((*root)->key > key) return delKey(&(*root)->left,key);
              else{
                   if ((*root)->key < key) return delKey(&(*root)->right, key);
                   else{
                            struct treeRB *z=*root, *p=z, *r=z,*y;
                            if(z->left==NULL){
                                        if(z->right) z->right->parent=(*root)->parent;
                                        *root=z->right;
                                        y=z->parent;
                                        free(z);
                                        z=NULL;
                                        return y;
                             }else{
                                        if (z->right==NULL){
                                                  z->left->parent=(*root)->parent;
                                                  *root=z->left;
                                                  y=z->parent;
                                                  free(z);
                                                  z=NULL;
                                                  return y;
                                        }else{
                                                  p=z->left;
                                                  r=z;
                                                  while(p->right!=NULL) {
                                                                   r=p;
                                                                   p=p->right;
                                                  }

                                                  int temp = p->key;
                                                  p->key=z->key;
                                                  z->key=temp;

                                                  if(r->key!=z->key){
                                                      r->right=p->left;
                                                      if(r->right!=NULL)
                                                                r->right->parent=p->parent;
                                                  }
                                                  else{
                                                      r->left=p->left;
                                                      if(r->left!=NULL)
                                                                r->left->parent=p->parent;
                                                   }
                                                   y=p->parent;
                                                   free(p);
                                                   p=NULL;
                                                   return y;
                                         }
                             }
                   }
             }
      }
}

Jest to zwykła funkcja usuwająca element z drzewa BST, ponieważ pierwsza faza usuwania elementu z drzewa RB jest identyczna,
tylko zwraca rodzica usuniętego elementu (rzeczywistego).Tak samo było przy drzewach AVL.

void removeRB(struct treeRB **root, int key){

     if(*root){ // gdy drzewo istnieje
     
       struct treeRB *q=NULL,*x=NULL,*p=NULL,*y=NULL; // zmienne pomocnicze
              q=delKey(root,key); // wywołanie funkcji kasującej

              if(*root && q){
 
       // gdy po skasowaniu elementu nadal drzewo istnieje możemy mieć taki przypadek,
       // że dziecko i rodzic usuniętego elementu są czerwonego koloru,
       // więc musimy się cofnąć do tego dziecka

             if(q->color=='R' && q->left && q->left->color=='R') q=q->left;
             else if (q->color=='R' && q->right && q->right->color=='R') q=q->right;

             // Dalej rozpatrujemy przypadki tak samo jak przy dodawaniu elementu
             x=q;
             p=x->parent;
             if(p && p->color=='R'){

                       while(x){
                                p=x->parent;

                                if(p->parent){
                                              if(p->parent->left==p)y=p->parent->right;
                                              else if(p->parent->right==p)y=p->parent->left;
                                }else y=NULL;

                                if(y && y->color=='R' && p->color=='R'){
                                               p->color=y->color='B';
                                              if(p->parent==*root) break;

                                              p->parent->color='R';
                                              if(p)x=p->parent;
                                }else{
                                              if(p->parent && y==p->parent->right){
                                                           if(p->color=='R'){
                                                                        if(p->right==x)          
                                                                                                RR(root,p);

                                                                        LL(root,p->parent);
                                                                        x->parent->color='B';
                                                              x->parent->right->color='R';
                                                            }
                                               }else if(p->parent && y==p->parent->left){
                                                           if(p->color=='R'){
                                                                         if(p->left==x)    
                                                                                                LL(root,p);

                                                                         RR(root,p->parent);
                                                                         x->parent->color='B';
                                                               x->parent->left->color='R';
                                                            }
                                               }
                                               break;
                                 }
                      }
           }
           }
    }
}


Jak widzisz usuwanie elementu jest bardzo proste, jak już się rozumie rzeczy, które już były. Z nowości to praktycznie nie ma nic, no może te dwie linijki, ale to przecież dużym problemem nie jest. Pozostałe funkcje, które nie zmieniają drzewa, są takie same dla wszystkich rodzajów drzew.

Brak komentarzy:

Prześlij komentarz

Subskrybuj: Komentarze (Atom)