Rekurencyjne struktury danych
Short Description
Download Rekurencyjne struktury danych...
Description
Rekurencyjne struktury danych Andrzej Jastrz¦bski
Akademia ETI
Politechnika Gda«ska
Rekurencyjne struktury danych
Dynamiczny przydziaª pami¦ci Pami¦¢, która jest przydzielana na pocz¡tku dziaªania procesu to: pami¦¢ programu czyli instrukcje programu pami¦¢ statyczna zwi¡zana ze zmiennymi globalnymi i zmiennymi statycznymi pami¦¢ stosu na stosie tworzone s¡ zmienne lokalne oraz ±lad wywoªania procedury Najcz¦±ciej podczas uruchamiania programu nie wiadomo ile pami¦ci b¦dzie potrzebowaª. Na przykªad, je±li chcemy napisa¢ program sortuj¡cy ci¡g liczb, to na pocz¡tku nie wiemy ile liczb b¦dziemy musieli posortowa¢. Aby rozwi¡za¢ ten problem trzeba wprowadzi¢ poj¦cie dynamicznego przydziaªu pami¦ci. Dynamiczny przydziaª pami¦ci pozwala na uzyskanie dodatkowej pami¦ci nie zwi¡zanej z pami¦ci¡ przyznan¡ na pocz¡tku dziaªania procesu. W j¦zykach programowania dynamiczny przydziaª pami¦ci jest realizowany przez operator new. Politechnika Gda«ska
Rekurencyjne struktury danych
Przykªad
int main() { int n, *tab; cin>>n; tab = new int[n]; //pro±ba o przyznanie pami¦ci //na n elementow¡ tablic¦ intów for(int i=0; i>tab[i]; delete [] tab; //zwolnienie przydzielonej pami¦ci return 0; }
Politechnika Gda«ska
Rekurencyjne struktury danych
Dealokacja pami¦ci Je±li nie potrzebujemy przydzielonej pami¦ci, nale»y wywoªa¢ funkcj¦/operator dealokacji. Automatyczna dealokacja pami¦ci W j¦zykach C oraz C++ nie ma wbudowanej automatycznej dealokacji pami¦ci. J¦zyki Java, Python, PHP itp. zaopatrzono w automatyczn¡ dealokacj¦, czyli tak zwany garbage collector.
Politechnika Gda«ska
Rekurencyjne struktury danych
Dynamiczna alokacja pami¦ci int *pam; pam = (int*) malloc(sizeof(int)); //alokacja pojedynczej liczby, j¦zyk C pam = new int; //alokacja pojedynczej liczby, j¦zyk C++ pam = (int*) malloc(sizeof(int)*n); //alokacja n-elementowej tablicy liczb, j¦zyk C pam = new int[n]; //alokacja n-elementowej tablicy liczb, j¦zyk C++
Dealokacja pami¦ci free(pam); //dealokacja pojedynczej liczby lub tablicy, j¦zyk C delete pam; //dealokacja pojeddynczej liczby, j¦zyk C++ delete [] pam; //dealokacja tablicy liczb, j¦zyk C++ Politechnika Gda«ska
Rekurencyjne struktury danych
Lista Lista jest struktur¡ zªo»on¡ z sekwencji rekordów. Ka»dy rekord ma odniesienie do innego rekordu.
Politechnika Gda«ska
Rekurencyjne struktury danych
Lista jednokierunkowa
struct ElListy1 { int val; //cz¦±¢ danych struct ElListy *next; }; Lista dwukierunkowa
struct ElListy2 { int val; //cz¦±¢ danych struct ElListy *next, *prev; };
Politechnika Gda«ska
Rekurencyjne struktury danych
Gªowa, ogon Ogonem nazywamy element x taki, »e x.next==NULL. Element x jest gªow¡ je±li nie istnieje »aden element y taki, »e y.next==x.
Politechnika Gda«ska
Rekurencyjne struktury danych
NULL
NULL
NULL
Politechnika Gda«ska
Rekurencyjne struktury danych
void newElem1(struct ElListy1 **firstEl, int v) { struct ElListy1 *tmpEl; tmpEl = (struct ElListy1*) malloc(sizeof(*tmpEl)); tmpEl->val = v; tmpEl->next = *firstEl; *firstEl = tmpEl; } void delFirst1(struct ElListy1 **firstEl) { struct ElListy1 *next = (*firstEl)->next; free(*firstEl); *firstEl = next; }
Politechnika Gda«ska
Rekurencyjne struktury danych
Wytªumaczenie napisu ** rstEl W powy»szym przykªadzie i w kolejnych procedury maj¡ deklaracj¦:
void nazwaProc(struct ElListy **firstEl, ....) Funkcje te wywoªuje si¦ nast¦puj¡co:
struct ElListy *pierwszyEl; . . . nazwaProc(&prierwszyEl);
Jest to spowodowane tym, »e w procedurach tych nale»y zmieni¢ wska¹nik na pierwszy element.
Politechnika Gda«ska
Rekurencyjne struktury danych
Wytªumaczenie napisu ** rstEl cd Mo»na porówna¢ z procedurami: void add2(int x) { x = x + 2;} void add2P(int *y) {*y = *y + 2;} int main() { int a=0; add2(a);//po tej operacji a jest nadal równe 0 add2P(&a);//po tej operacji a jest równe 2 return 0; } add2 zmienna x jest lokalna, a jej warto±¢ jest kopi¡ a. W procedurze add2P zmienna y jest tak»e lokalna. Ró»nica polega na tym, »e y co do warto±ci jest równa adresowi w pami¦ci, w której przechowywana jest zmienna a. Odniesienie *y = *y + 2; dziaªa na dokªadnie tych samych komórkach pami¦ci, w których znajduje si¦ a. Powy»sze instrukcje zmieniaj¡ wi¦c warto±¢ zmiennej a.
W procedurze
warto±ci zmiennej
Politechnika Gda«ska
Rekurencyjne struktury danych
void delLast1(struct ElListy1 **firstEl) { struct ElListy1 *curr = *firstEl; //curr=*firstEl; struct ElListy1 *prev = NULL; //prev=NULL; while(curr->next!=NULL) { prev = curr; next = curr->next; } free(curr); //zwalniamy pami¦¢, któr¡ zajmowaª ostatni ele if(prev==NULL) //byª jeden element w li±cie *firstEl = NULL; else //byªo kilka elementów w li±cie prev->next = NULL; }
Politechnika Gda«ska
Rekurencyjne struktury danych
void newElem2(struct ElListy2 **firstEl, int v) { struct ElListy2 *tmpEl; tmpEl = (struct ElListy2*) malloc(sizeof(*tmpEl)); tmpEl->val = v; tmpEl->next = *firstEl; tmpEl->prev = NULL; if(*firstEl!=NULL) //na li±cie nie ma elementów (*firstEl)->prev = tmpEl; *firstEl = tmpEl; } void delFirst2(struct ElListy2 **firstEl) { struct ElListy2 *next = firstEl->next; free(*firstEl); if(next!=NULL) next->prev = NULL; *firstEl = next; } Politechnika Gda«ska
Rekurencyjne struktury danych
void delLast2(struct ElListy2 **firstEl) { struct ElListy2 *curr = *firstEl; while(curr->next!=NULL) curr = curr->next; if(curr->prev==NULL) {//jest jeden element w li±cie free(curr); *firstEl = NULL; return; } curr = curr->prev; //cofamy si¦ do przedostatniego elementu free(curr->next); //zwalniamy pami¦¢, któr¡ zajmowaª ostatni element curr->next = NULL; }
Politechnika Gda«ska
Rekurencyjne struktury danych
Zaªo»enia - listy jednokierunkowe Niech x, y, curr b¦d¡ wska¹nikami na struktur¦ ElListy1. Dla list jednokierunkowych mamy zaªo»enie: p¦tla
while(curr) curr = curr->next; nie jest niesko«czona dla ka»dego pocz¡tkowego curr nale»¡cego do listy. Nie istniej¡ dwa elementy listy, które wskazuj¡ na ten sam element, czyli x->next!=y->next.
Politechnika Gda«ska
Rekurencyjne struktury danych
Zaªo»enia - listy dwukierunkowe Niech curr b¦dzie wska¹nikiem na struktur¦ ElListy2. Dla list dwukierunkowych mamy zaªo»enie: p¦tle
while(curr) curr = curr->next; while(curr) curr = curr->prev; nie s¡ niesko«czone dla ka»dego pocz¡tkowego curr nale»¡cego do listy. Je±li curr->next!=NULL, wtedy zachodzi curr->next->prev==curr. Nie istniej¡ dwa elementy listy, które wskazuj¡ na ten sam element, czyli x->next!=y->next.
Politechnika Gda«ska
Rekurencyjne struktury danych
Zªo»ono±ci obliczeniowe Dla n elementowej listy mamy nast¦puj¡ce zªo»ono±ci obliczeniowe: dodawanie O(1) usuwanie pierwszego elementu O(1) usuwanie ostatniego elementu O(n) (je±li istnieje wska¹nik na ostatni element w li±cie dwukierunkowej wtedy O(1)) sortowanie O(n log n) (mergesort) dost¦p do elementu O(n) szukanie elementu O(n)
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodatki Inne rodzaje list: listy jednokierunkowe cykliczne listy dwukierunkowe cykliczne listy cykliczne z wartownikiem Mo»na zaimplementowa¢ list¦ na tablicy struktur.
Politechnika Gda«ska
Rekurencyjne struktury danych
Je±li tablica ma n elementów to wiemy, »e dla tablicy zªo»ono±ci obliczeniowe s¡ nast¦puj¡ce: dodawanie O(n) usuwanie O(n) sortowanie O(n log n) dost¦p do elementu O(1) szukanie w tablicy nieposortowanej O(n) szukanie w tablicy posortowanej O(log n)
Politechnika Gda«ska
Rekurencyjne struktury danych
Struktura drzewa binarnego wyszukiwa« mo»e by¢ podana przez zaªo»enia podanych poni»ej. Drzewo zbudowane jest z w¦zªów, które: niepuste drzewo ma w¦zeª wyró»nony korze« ka»dy w¦zeª oprócz korzenia posiada jednego ojca (w¦zeª poprzedzaj¡cy) ka»dy w¦zeª posiada conajwy»ej dwóch synów (binarno±¢ drzewa) syn w¦zªa X ma ojca X warunek drzewa wszystkie warto±ci lewego poddrzewa w¦zªa X maj¡ mniejsze warto±ci od warto±ci w¦zªa X (drzewo wyszukiwa«) wszystkie warto±ci prawego poddrzewa w¦zªa X maj¡ wi¦ksze warto±ci od warto±ci w¦zªa X (drzewo wyszukiwa«)
Politechnika Gda«ska
Rekurencyjne struktury danych
Element drzewa w¦zeª
struct Node { int val; //cz¦±¢ na dane struct Node *left, *right, *parent; }
Politechnika Gda«ska
Rekurencyjne struktury danych
Zaªo»enia dla drzewa Niech root, curr s¡ wska¹nikami na struktur¦ Node. Je±li root jest wska¹nikiem na korze«, wtedy root->parent==NULL. Je±li curr jest dowolnym wska¹nikiem na w¦zeª drzewa, to: je±li curr->left!=NULL, to curr->left->parent==curr; je±li curr->right!=NULL, to curr->right->parent==curr.
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodawanie elementu do drzewa Dodaj¡c element do drzewa nale»y korzystaj¡c z algorytmu szukania elementu w drzewie znale¹¢ ostatni w¦zeª (X ) w algorytmie. je±li jest to w¦zeª z tak¡ sam¡ warto±ci¡ jak¡ chcemy doda¢ wtedy jej nie dodajemy (bo ju» jest w drzewie) je±li warto±¢ w¦zªa, który dodajemy, jest wi¦kszy od warto±ci w¦zªa X , wtedy w¦zeª X nie posiada prawego syna (z algorytmu szukania) i mo»emy w to miejsce doda¢ nowy w¦zeª je±li warto±¢ w¦zªa, który dodajemy, jest mniejszy od warto±ci w¦zªa X , wtedy w¦zeª X nie posiada lewego syna (z algorytmu szukania) i mo»emy w to miejsce doda¢ nowy w¦zeª
Politechnika Gda«ska
Rekurencyjne struktury danych
void add(struct Node **root, int v) { struct Node *curr, *prev; if(*root==NULL) { //brak w¦zªów w drzewie *root = (struct Node*) malloc(sizeof(*curr)); (*root)->parent = (*root)->left = (*root)->right = NULL; (*root)->val = v; return; } prev = NULL; curr = *root; //pocz¡tkowe dane do wyszukiwania while(curr!=NULL&&curr->val!=v) { prev = curr; if(curr->val>v) curr = curr->left; else curr = curr->right; } if(curr!=NULL) return; //oznacza to, »e curr->val==v curr = (struct Node*) malloc(sizeof(*curr)); curr->parent = prev; curr->left = curr->right = NULL; curr->val = v; if(prev->val>v) prev->left = curr; else prev->right = curr; } Politechnika Gda«ska
Rekurencyjne struktury danych
root =nul tmp
Politechnika Gda«ska
n_wez
Rekurencyjne struktury danych
Dodajemy 8 root =nul tmp
Politechnika Gda«ska
n_wez
Rekurencyjne struktury danych
Dodajemy 8 root =nul tmp
n_wez
8
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 8 root
tmp
n_wez
8
Politechnika Gda«ska
Rekurencyjne struktury danych
root
tmp
n_wez
8
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 13 root
tmp
n_wez
8
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 13 root
tmp
n_wez
8
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 13 root
tmp
n_wez
8
13
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 13 root
tmp
n_wez
8
13
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 13 root
tmp
n_wez
8
13
Politechnika Gda«ska
Rekurencyjne struktury danych
root
tmp
n_wez
8
13
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 18 root
tmp
n_wez
8
13
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 18 root
tmp
n_wez
8
13
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 18 root
tmp
n_wez
8
13
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 18 root
n_wez
tmp
8
13
18
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 18 root
n_wez
tmp
8
13
18
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 18 root
n_wez
tmp
8
13
18
Politechnika Gda«ska
Rekurencyjne struktury danych
root
n_wez
tmp
8
13
18
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 15 root
n_wez
tmp
8
13
18
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 15 root
n_wez
tmp
8
13
18
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 15 root
n_wez
tmp
8
13
18
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 15 root
n_wez
tmp
8
13
18
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 15 root
n_wez
tmp
8
13
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 15 root
n_wez
tmp
8
13
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 15 root
n_wez
tmp
8
13
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
root
n_wez
tmp
8
13
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 11 root
n_wez
tmp
8
13
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 11 root
n_wez
tmp
8
13
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 11 root
n_wez
tmp
8
13
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 11 n_wez
tmp
root 8
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 11 n_wez
tmp
root 8
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 11 n_wez
tmp
root 8
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
n_wez
tmp
root 8
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 5 n_wez
tmp
root 8
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 5 n_wez
tmp
root 8
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 5 n_wez
tmp
root 8
5
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 5 n_wez
tmp
root 8
5
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 5 n_wez
tmp
root 8
5
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
n_wez
tmp
root 8
5
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 12 n_wez
tmp
root 8
5
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 12 n_wez
tmp
root 8
5
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 12 n_wez
tmp
root 8
5
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 12 n_wez
tmp
root 8
5
13
11
18
15
Politechnika Gda«ska
Rekurencyjne struktury danych
Dodajemy 12 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
Rekurencyjne struktury danych
Dodajemy 12 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
Rekurencyjne struktury danych
Dodajemy 12 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
Rekurencyjne struktury danych
n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
Rekurencyjne struktury danych
Dodajemy 22 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
Rekurencyjne struktury danych
Dodajemy 22 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
Rekurencyjne struktury danych
Dodajemy 22 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
Rekurencyjne struktury danych
Dodajemy 22 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
Rekurencyjne struktury danych
Dodajemy 22 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Dodajemy 22 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Dodajemy 22 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Dodajemy 2 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Dodajemy 2 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Dodajemy 2 n_wez
tmp
root 8
5
13
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Dodajemy 2 n_wez
tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Dodajemy 2 n_wez
tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Dodajemy 2 n_wez
tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
n_wez
tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
root 8
5
2
13
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukanie elementu w drzewie Aby znale¹¢ element o zadanej warto±ci korzystamy z operacji: je±li warto±¢ szukana jest wi¦ksza od warto±ci w¦zªa aktualnego, wtedy przechodzimy do prawego syna; je±li w¦zeª nie posiada prawego syna, wtedy elementu nie ma w drzewie; je±li warto±¢ szukana jest mniejsza od warto±ci w¦zªa aktualnego, wtedy przechodzimy do lewego syna; je±li w¦zeª nie posiada lewego syna, wtedy elementu nie ma w drzewie; je±li warto±¢ szukana jest równa warto±ci w¦zªa aktualnego, wtedy znale¹li±my w¦zeª. Operacje t¡ zaczynamy od korzenia.
Politechnika Gda«ska
Rekurencyjne struktury danych
tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 9 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 9 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 9 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 9 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Nie znaleziona 9 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 2 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 2 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 2 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 2 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Znaleziona 2 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 15 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 15 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 15 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 15 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Szukamy liczby 15 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Znaleziona 15 tmp
root 8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Usuwanie elementu z drzewa Usuwanie elementu z zadan¡ warto±ci¡, tak»e u»ywa algorytmu szukania jako pomocniczego. Szukamy w¦zªa o zadanej warto±ci. je±li w¦zeª jest li±ciem (nie ma lewego ani prawego syna), wtedy usuwamy je±li w¦zeª nie posiada lewego syna, wtedy zast¦pujemy usuwany w¦zeª przez caªe prawe poddrzewo je±li w¦zeª nie posiada prawego syna, wtedy zast¦pujemy usuwany w¦zeª przez caªe lewe poddrzewo je±li w¦zeª posiada lewego i prawego syna, wtedy z lewego poddrzewa szukamy maksymalnego (albo z prawego poddrzewa szukamy minimalnego) w¦zªa i usuwamy go, a jego warto±¢ zamieniamy z wyszukanym w¦zªem Je±li usuwamy korze«, wtedy musimy zmieni¢ wska¹nik, aby wskazywaª na nowy korze«. Politechnika Gda«ska
Rekurencyjne struktury danych
tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 2 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 2 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 2 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 2 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 2 tmp
root
kas
8
5
13
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 11 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 11 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 11 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 11 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 11 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 11 root
tmp
kas
8
5
13
2
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 11 tmp
root
kas
8
5
13
2
12
18
15
Politechnika Gda«ska
22
Rekurencyjne struktury danych
tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 8 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 8 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 8 tmp
root
kas
8
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 8 tmp
root
kas
11
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 8 tmp
root
kas
11
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 8 tmp
root
kas
11
5
13
2
11
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 8 root
tmp
kas
11
5
13
2
18
12
Politechnika Gda«ska
15
22
Rekurencyjne struktury danych
Kasujemy 8 tmp
root
kas
11
5
13
2
12
18
15
Politechnika Gda«ska
22
Rekurencyjne struktury danych
Zªo»ono±¢ obliczeniowa Je±li drzewo ma n elementów i wysoko±¢ h wtedy: dodawanie O(h) (O(n)) usuwanie O(h) (O(n)) szukanie O(h) (O(n))
Politechnika Gda«ska
Rekurencyjne struktury danych
Samo drzewo posiada gorsze zªo»ono±ci pesymistyczne ni» tablica. Mo»na jednak stworzy¢ drzewa, dla których h = O(log n). S¡ to: drzewa czerwono czarne drzewa AVL Drzewa te korzystaj¡ z obrotów drzewa wzgl¦dem w¦zªów.
Politechnika Gda«ska
Rekurencyjne struktury danych
View more...
Comments
