Drzewa to kolejna po listach struktura danych. Od list różnią się tym, że elementy w drzewa mają jednego lub brak poprzednika, a następników wiele. My zajmować się będziemy drzewami binarnymi, które mają maksymalnie dwa następniki.
DRZEWA BST
Drzewa BST (przeszukiwań binarnych) to taki specjalny rodzaj drzewa, w którym klucze po jednej stronie są większe niż po drugiej. Jeśli założymy, że klucze po lewej stronie są mniejsze niż po prawej, to gdy będziemy szli cały czas w lewo znajdziemy najmniejszy klucz. Natomiast jeśli pójdziemy na prawo do końca to znajdziemy największy klucz.
np.:
Zaletą drzew BST jest szybkość przeszukiwania, ponieważ jednym krokiem odrzucamy połowę obszaru do przeszukania, bo wiemy, że np. po prawej stronie drzewa na pewno nie ma naszego elementu.
Dzięki temu możemy szybko wyszukiwać elementy drzewa. Niestety nie wszystkie drzewa BST są takie ładnie (doskonałe/idealne) jak pierwszy przykład, czasami trafiają nam się takie jak ostatni przykład, który w praktyce jest listą wtedy przeszukiwanie takiego drzewa jest dużo dłuższe. Dlatego powstały jeszcze inne rodzaje drzew, które to dbają o to by nasze drzewka były piękne, ale o tym później.
Przykładowa struktura drzewa BST:
struct treeBST{
struct treeBST *left; // wskazanie na lewy element (następnik)
struct treeBST *right; // wskazanie na prawy element
struct treeBST *parent; // wskazanie na rodzica (poprzednik)
int key; // pole które będzie przechowywało nasz klucz
};
Tej struktury będę używał, gdy będę podawał przykłady kodów.
No to jak już wiemy co to są te drzewa to fajnie by było wiedzieć jak się nimi posługiwać.
1.Dodawanie elementu
Dodawanie elementu jest w zasadzie bardzo proste. Polega na znalezieniu odpowiedniego miejsca dla naszego elementu i utworzeniu go. Ale od początku.
Chcemy dodać element (5). Zawsze pierwszy element, który dodajemy do drzewa staje się naszym korzeniem.
Następnie dodajemy element (2). (2) jest mniejsze od (5) więc idziemy w lewo. Gdy pójdziemy w lewo natrafimy na NULL, czyli na wolne miejsce, więc tam dodajemy nasz element.
Teraz dodajemy (3). (3) jest mniejsze od (5) więc idziemy w lewo. Trafiamy na (2). (3) jest większe od (2) więc idziemy w prawo i znowu mamy NULL. Więc tam wstawiamy nasz element.
Teraz dodajmy element o kluczu (10). (10) jest większe od 5 więc idziemy w prawo mamy NULL i tam dodajemy nasz nowy element.
Jak widzimy dodawanie do drzewa nie jest takie trudne. Wystarczy znaleźć miejsce dla naszego nowego elementu, a potem go utworzyć. Samo tworzenie elementu jest podobne do tego listach.
Jeszcze jedna bardzo ważna rzecz:
Klucz elementu w drzewie BST jest unikatowy
Czyli nie ma dwóch elementów o kluczu np. (3)
KOD:
(Rekurencja)
void add_tree(struct tree **root, int key){
// funkcja za argument przyjmuje wskazanie na wskazanie korzenia oraz klucz
if(!(*root)){ // jeśli nasz korzeń jest NULL, czyli znaleźliśmy miejsce
(*root)=(struct tree*)malloc(sizeof(struct tree));
// tworzymy nowy element i ustalamy jego pola
(*root)->key=key;
(*root)->left=NULL;
(*root)->right=NULL;
(*root)->parent=NULL;
//
}else{ // gdy jeszcze nie znaleźliśmy miejsca
if((*root)->key>key){ // gdy nasz klucz jest mniejszy to idziemy w lewo
add_tree(&(*root)->left,key); // wywołanie funkcji
(*root)->left->parent=*root; // ustalenie pola parent
}
else if ((*root)->key<key){// nasz klucz jest większy to idziemy w prawo
add_tree(&(*root)->right,key); // wtwołanie funkcji
(*root)->right->parent=*root; // przypisanie pola parent
}
}
}
Dzięki zastosowaniu wskazania na wskazanie nie musimy nic zwracać, ale jako argumenty do funkcji musimy dać adres naszego korzenia. Na samym początku, gdy dodajemy pierwszy element to funkcja od razu natrafia na NULL, czyli zaczyna się tworzenie pierwszego elementu. Natomiast gdy w naszym drzewie są już jakieś elementy to funkcja musi znaleźć miejsca dla nowego elementu. Szukanie elementu polega na wywoływaniu kolejnych rekurencji dla argumentu lewego bądź prawego, aż funkcja natrafi na NULL. Wtedy to przestaną wywoływać się rekurencje element zostanie utworzony i zaczną się „powroty”. W trakcie powrotu będzie ustalone pole parent dla naszego nowego elementu, bo dopiero wtedy będziemy mieli dostęp do elementów zależnych od siebie. Pewnie zauważyłeś, że niektóre elementy będą miały kilka razy określane pole parent, ale nie stwarza to problemu, gdyż za każdym razem będą to takie same wartości.
KOD:
(iteracyjnie)
void add_it(struct tree **root, int key){
struct tree *tree_elem=(struct tree*)malloc(sizeof(struct tree));
// tworznie elementu
struct tree *d=*root,*p=NULL; // zmienne pomocnicze
// ustalenie początkowych wartości dla elementu
tree_elem->key=key;
tree_elem->left=tree_elem->right=NULL;
//
if(!d){ // gdy jest to pierwszy element drzewa
tree_elem->parent=NULL;
*root=tree_elem; // nasz nowy element staje się korzeniem
}
else{ // gdy jest to kolejny element drzewa
while(d!=NULL){ // pęlta szuka wolnego miejsca
if(d->key > key){
// gdy nasz klucz jest mniejszy to idziemy w lewo
p=d;
d=d->left;
}else if(d->key < key){
// gdy nasz klucz jest mniejszy to idziemy w prawo
p=d;
d=d->right;
}else break;
// gdy nasz klucz jest taki sam jak jeden z elementów drzewa
}
if(d==NULL){ // gdy pętla znalazła miejsce, a nie taki sam klucz
// ustalamy ostateczną relacje między elementami
if(p->key>key) p->left=tree_elem;
else p->right=tree_elem;
tree_elem->parent=p;
//
}
}
}
Jak widzimy ten kod równie polega na tym samym, na znalezieniu miejsca i wstawieniu do niego elementu. Na początku (tak jak to było w listach) tworzymy element i przypisujemy mu początkowe wartości. Następnie ustalamy miejsce naszego elementu w drzewie
i ustalamy ostatecznie relacje między elementami.
2.Usuwanie elementu
Usuwanie elementu z drzewa BST jest dość skomplikowane. Trudność tej operacji nie polega na samym usuwanie elementu, ale na tym by po usunięcie z drzewa klucza to drzewa nadal zachowało własności drzewa BST, czyli miało odpowiednio uporządkowane klucze. Ale to jeszcze nie koniec niespodzianek, bo trzeba pamiętać o kilku przypadkach, a mianowicie o 3. Pierwszy to taki, że usuwamy liścia, czyli kasujemy element z samego dołu i tyle to jest ten najłatwiejszy. Drugim przypadkiem jest ten, w którym nasz szukany element ma jednego następnika (z prawej lub lewej strony). Tutaj trzeba najpierw przestawić połączenie z poprzednika do naszego na z poprzednika do następnika naszego, a następnie skasować nasz element (to jest trochę trudniejszy przypadek). Ale jest jeszcze jeden czyli ten, w którym nasz element szukany ma dwóch następników. I tu robią się dopiero schody, bo na jedno połączenie mamy dwóch kandydatów. Rozwiązanie tego problemu jest dwojakie. Albo wchodzimy w lewe poddrzewo i szukamy największego elementu poddrzewa (idziemy cały czas w prawo) albo wchodzimy w prawe poddrzewo i idziemy cały czas w lewo, co daje nam najmniejszy element tego poddrzewa. Następnie musimy zamienić ze sobą elementy, czyli nasz element który mamy skasować z tym znalezionym. Ale zamieniamy tylko klucze. Dzięki temu nie tracimy połączeń między elementami. No dobrze, ale jak już zamienimy te elementy to jednak trzeba się tego naszego jakoś pozbyć, no to się pozbywamy. ALE przecież ten element mógł mieć jakiegoś następnika z lewej lub z prawej strony (zależy w którą stronę poszliśmy wcześniej). Więc musimy przestawić nasze połączenie. A dopiero potem będziemy mogli skasować nasz niechciany element. No to tak w skrócie na czym polega kasowanie z drzewa.
Ale pomalutku, więc zaczynamy pod początku.
Nasze drzewko:
Chcemy skasować element (3). Nic prostszego :D. Wystarczy znaleźć nasz element i sprawdzić co jest pod nim. Pod nim nie ma nic czyli nasz element (3) jest naszym liściem i nie ma potomków. Czyli nie musimy się martwić tym, że jak skasujemy go to coś popsujemy. Więc kasujemy go i ustawiamy tylko połączenie z elementu (2) na NULL.
//////////////////////////////////////////////////////////////////
Dobrze teraz wróćmy znowu do naszego drzewka.
Chcemy teraz skasować element (2). Więc znowu szukamy naszego elementu i sprawdzamy co jest pod nim. No tu nie jest tak miło, bo nasz element (2) ma potomka, ale dobrze że tylko jednego. Czyli musimy zrobić teraz tak, że element (5) (poprzedni od (2)) musimy mieć wskazanie (z lewej strony) na element (3) (potomek 2). Chodzi nam o taką sytuację, w której element (2) będzie pominięty, a drzewo zachowa swoją spójność. A następnie należy skasować nasz element.
//////////////////////////////////////////////////////////////////
Znowu wróćmy do naszego ulubionego drzewka, ale lekko go zmienimy:
Teraz chcemy skasować element (5). Więc standardowo szukamy naszego elementu i sprawdzamy czy jest coś po lewej stronie, no jest, a teraz sprawdzamy czy jest coś po prawej stronie, no też jest. Więc jednym słowem mamy przej****e, nie no żartuję :D. Nie jest tak źle, ale sprawa się lekko komplikuje. Ale wszystko po kolei. Przechodzimy do lewego poddrzewa i szukamy elementu maksymalnego, czyli przechodzimy cały czas w prawo. Następnie zamieniamy nasz element z tym elementem, którego znaleźliśmy.
Otrzymujemy takie drzewo.
Ale teraz mamy takie sobie to drzewko, bo ani To nie jest drzewo BST, bo źle są poukładane nasze elementy ani nie o to nam chodziło. No ale może nie jest tak źle. Teraz sprawdzamy czy nasz element ma jakiś potomków (bo teraz może mieć 1 lub 0 bo zamieniliśmy klucze z elementem najbardziej po prawej). No niestety ma jednego potomka. Ale w sumie to już nie jest tak źle, bo my już wiemy jak zrobić, aby usunąć element, który ma jednego potomka. Czyli po prostu ustalamy tak relacje, aby pominąć nasz element. W naszym przypadku musimy zrobić tak, aby (1)->right=(2) ale jeszcze (2)->parent=(1). Jak już mamy ustalone relacje z pominięciem naszego elementu (5), to możemy go bez problemu usunąć z pamięci bez obawy o popsucie naszego drzewka.
Tak wiem usuwanie elementów z drzewa jest dość trudne, ale mam nadzieję, że trochę rozjaśniłem i teraz jak podam kod wszystko stanie się dla Ciebie jasne.
KOD:
void delKey(struct tree **root, int key){
// funkcja przyjmuję za argumenty wskazania na wskazanie korzenia i klucz
if(*root!= NULL){ // gdy drzewo istnieje
// rekurencyjne szukanie naszego elementu
if((*root)->key > key) delKey(&(*root)->left,key);
else{
if ((*root)->key < key) delKey(&(*root)->right, key);
//
else{ // znaleziono element
struct tree *z=*root; // z-nasz element, zmienna pomocnicza
if(z->left==NULL){ // nasz element nie posiada lewego potomka
// czyli może mieć jednego albo dwóch potomków
if(z->right) z->right->parent=(*root)->parent;
*root=z->right; // obijanie elementu
free(z); // zwalnianie pamięci
z=NULL;
}else{ // nasz element ma lewego potomka
if (z->right==NULL){ // nasz element nie ma prawego potomka
// czyli znowu tak samo jak wcześniej
z->left->parent=(*root)->parent;
*root=z->left;
free(z);
z=NULL;
}else{ // nasz element posiada lewgo i prawego potomka
struct tree *p=z->left, *r=z; // zmienne pomocnicze
// p-korzeń lewego poddrzewa naszego elementu
while(p->right!=NULL){
// pętla szuka maksymalnego elementu w lewym poddrzewie
r=p;
p=p->right;
}
// po wykonaniu pętli p- jest naszym maksymalnym // elementem, a r-jego rodzicem
// zamieniamy klucze elementów „z” i „p”
int temp = p->key;
p->key=z->key;
z->key=temp;
// ustalamy ominięcie naszego elementu „p” -którego // będziemy kasować
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;
}
//
free(p); // zwolnienie pamięci
p=NULL;
}
}
}
}
}
}
KOD:
(bez komentarzy dla łatwiejszego rozumienia)
void delKey(struct tree **root, int key){
if(*root!= NULL){
if((*root)->key > key) delKey(&(*root)->left,key);
else{
if ((*root)->key < key) delKey(&(*root)->right, key);
else{
struct tree *z=*root;
if(z->left==NULL){
if(z->right) z->right->parent=(*root)->parent;
*root=z->right;
free(z);
z=NULL;
}else{
if (z->right==NULL){
z->left->parent=(*root)->parent;
*root=z->left;
free(z);
z=NULL;
}else{
struct tree *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;
}
free(p);
p=NULL;
}
}
}
}
}
}
Jak widzimy najpierw jest szukanie naszego elementu. Gdy już go znaleźliśmy to sprawdzamy ilu ma potomków (1 czy 2). Możemy zauważyć, że gdy element nie ma potomków to jego dziećmi są NULL i NULL. W tej sytuacji możemy potraktować jeden NULL jak potomek, ale taki pusty, bo i tak dalej nie będziemy szli. Dzięki temu nie musimy rozpatrywać kolejnego przypadku. Gdy nasz element ma dwóch potomków to wchodzimy do jego lewego poddrzewa, a następnie pętlą while szukamy jego największego elementu. Po wyjściu z pętli zamieniamy klucze miejscami. Następnie kasujemy element.
No to najtrudniejszą rzecz w drzewach BST mamy już załatwioną teraz już będzie z górki :D.
3. przechodzenie drzewa
Przechodzenie drzewa jest bardzo potrzebną funkcją. Dzięki niej będziemy mogli przejść całe drzewo, żeby albo coś znaleźć albo po prostu go wypisać.
Nasze drzewo:
Przechodzenie drzewa od lewej do prawej:
void write_left(struct tree *root){
if(root){
if(root->left)write_left(root->left); // jeśli możemy to idziemy w lewo
printf("%d ", root->key); // wypisujemy element
if(root->right)write_left(root->right); // jeśli możemy idziemy w prawo
}
}
Na ekranie:
1 2 3 5 10
Przechodzenie drzewa od prawej do lewej:
void write_right(struct tree*root){
if(root){
if(root->right)write_right(root->right); // jeśli możemy to idziemy w prawo
printf("%d ", root->key); // wypisujemy element
if(root->left)write_right(root->left); // jeśli możemy to idziemy w lewo
}
}
Na ekranie:
10 5 3 2 1
Do operacji na drzewach wygodnie używa się rekurencji, ale jeśli się postarać można zrobić to też za pomocą iteracji.
Brak komentarzy:
Prześlij komentarz