Studia Licencjackie / InŜynierskie
Algorytmy i struktury danych
Wykład 05
Słownik
Słownik – struktura danych przechowująca elementy ze zbioru uporządkowanego, umoŜliwiająca wykonywanie operacji:
− Dodaj nowy element
− Usuń element
− Znajdź element (sprawdź czy występuje w zbiorze; jeśli tak, znajdź informacje o nim)
− Wypisz elementy w porządku
[ ta operacja nie jest wymaga w standardowym słowniku; dodamy ją w celach dydaktycznych ... ]
Drzewa binarnych poszukiwań (BST)
Definicja struktur danych:
typedef struct node *pnode;
typedef struct node{
int key;
pnode left; pnode right;} snode;
Własność drzewa BST:
Dla kaŜdego węzła v:
• Klucze znajdujące się w jego lewym poddrzewie są mniejsze (lub równe) od klucza w węźle v,
• Klucze znajdujące się w jego prawym poddrzewie są większe (lub równe) od klucza w węźle v.
Przykłady:
to nie jest drzewo BST
5
4
8
3
7
9
PoniŜej poprawne drzewo BST
5
3
8
1
4
9
− Dziecko, rodzic, rodzeństwo
− Korzeń – węzeł, który nie ma rodzica
− Liść – węzeł, którego lewe i prawe poddrzewo są puste (nie ma dzieci)
− ŚcieŜka – ciąg węzłów v 1, v 2, …, vk taki, Ŝe vi jest dzieckiem vi-1 dla i=2,3,…, k
− Wysokość drzewa – długość (liczba elementów) najdłuŜszej ścieŜki w drzewie Podstawowe funkcje
Wyszukiwanie klucza
Pseudokod:
Szukaj( d, w) [ d – drzewo; w – szukana wartość ]
1. Jeśli d puste lub d.klucz równy w: zwróć d;
2. Jeśli (w < d.klucz): zwróć Szukaj (d.lewe, w)
wpp zwróć Szukaj(d.prawe, w)
Implementacja
Specyfikacja
Dane: root – korzeń drzewa, skey – szukana wartość
Wynik:
Jeśli skey występuje w drzewie o korzeniu root: wskaźnik na węzeł zawierający skey.
Jeśli skey występuje w drzewie o korzeniu root: wskaźnik pusty NULL.
pnode search( pnode root, int skey)
{
if (root==NULL || root->key == skey) return root; if (root->key > skey)
return search(root->left, skey);
else return search(root->right, skey);
}
Pseudokod:
Wstaw( d, w) [ d – drzewo; w – wstawiana wartość ]
1. Jeśli d puste: utwórz węzeł z kluczem w i pustymi dziećmi;
2. Jeśli (w < d.klucz): wstaw( d.lewe, w)
3. Jeśli (w>d.klucz): wstaw(d.prawe, w)
Implementacja
Specyfikacja
Dane: root – korzeń drzewa, nkey – wstawiana wartość
Wynik:
Jeśli w root nie ma węzła z kluczem nkey: wskaźnik na korzeń drzewa uzyskanego z root po wstawieniu węzła z kluczem nkey.
Jeśli w root jest węzeł z kluczem nkey: oryginalna wartość root (drzewo się nie zmienia).
pnode insert( pnode root, int nkey)
//jeśli w drzewie BST na które wskazuje root
//nie ma elementu o wartosci klucza rownej nkey,
//taki element jest wstawiany
{
pnode pom;
if (root==NULL){ // tworzenie nowej struktury
pom = (pnode) malloc(sizeof(snode));
pom->left = pom->right = NULL;
pom->key = nkey;
return pom;
}
if (nkey < root->key)
root->left = insert(root->left, nkey);
else
if (nkey > root->key)
root->right = insert(root->right, nkey);
return root;
}
Wypisanie elementów w kolejności niemalejącej (porządek inorder).
Pseudokod:
wypisz( d ) [ d – drzewo ]
Jeśli d niepuste
1. Wypisz(d.lewe)
2. Wypisz d.klucz
3. Wypisz(d.prawe)
Implementacja
Specyfikacja
Dane: root – korzeń drzewa
Wynik: wypisanie na wyjściu elementów z drzewa root w kolejności niemalejącej void write( pnode root )
{
if (root!=NULL){
write( root->left); // wypisz mniejsze
printf("%d\n", root->key); // wypisz dany element
write( root->right); //wypisz wieksze
}
}
Pseudokod:
usun( d, w ) [ d – drzewo, w – usuwana wartość ]
Jeśli d niepuste:
1. Jeśli (w < d.klucz): usun(d.lewe, w)
2. Jeśli (w > d.klucz): usun(d.prawe, w)
3. wpp [ czyli dla w = d.klucz ]
a. Jeśli d.lewe jest puste: d ← d.prawe
b. Jeśli d.prawe jest puste: d ← d.lewe
c. wpp [ gdy d.lewe i d.prawe niepuste ]
i. znajdź w’ – najmniejszy element d.prawe
ii. wstaw wartość w’ do korzenia d
iii. usuń „stary” węzeł zawierający w’ [ ten węzeł nie ma lewego poddrzewa ]
Implementacja
Specyfikacja
Dane: root – korzeń drzewa, dkey – klucz do usunięcia
Wynik:
Korzeń drzewa uzyskane z root po usunięciu węzła zawierającego dkey.
pnode deletekey( pnode root, int dkey)
{ // usuwa element o kluczu dkey z drzewa, na które wskazuje root pnode pom;
if (root!=NULL)
if (dkey < root->key) // szukany element w lewym poddrzewie root->left = deletekey(root->left, dkey);
else
if (dkey > root->key) // szukany element w prawym poddrzewie root->right = deletekey(root->right, dkey);
else // root wskazuje na element do usuniecia
if (root->left == NULL){ // brak lewego poddrzewa
pom=root->right; // "podczepiamy" prawe poddrzewo free(root);
root=pom;
} else
if (root->right == NULL){ //brak prawego poddrzewa
pom=root->left; //"podczepiamy" lewe poddrzewo free(root);
root = pom;
} else
delhlp(root, root->right); // ma oba poddrzewa
return root;
}
Specyfikacja funkcji pomocniczej delhlp
Dane: root, akt – korzenie drzew; [ akt jest poddrzewem root ]
Wynik: drzewo uzyskane po usunięciu najmniejszej wartości z akt i wstawieniu jej do węzła root pnode delhlp(pnode root, pnode akt) //FUNKCJA POMOCNICZA!
{
pnode pom;
// najmniejszy element prawego poddrzewa wezla root
// usuwamy, a jego klucz umieszczamy w wezle root
// UWAGA: element najmniejszy NA PEWNO nie ma lewego poddrzewa
if (akt->left!=NULL) { // akt nie jest najmniejszy
akt->left = delhlp(root, akt->left);
return akt;
} else // akt wskazuje na najmniejszy element w poddrzewie root
{ root->key = akt->key;
pom=akt->right;
free(akt);
return pom;
}
}
ZłoŜoność czasowa operacji słownikowych na BST
Fakt.
ZłoŜoność najgorszego przypadku operacji:
− dodaj nowy element
− usuń element
− znajdź element (sprawdź czy występuje w zbiorze; jeśli tak, znajdź informacje o nim) jest proporcjonalna do wysokości drzewa.
Fakt. Wypisanie elementów w porządku dla drzewa o n węzłach wymaga czasu O( n).
Wysokość drzewa o n węzłach:
− najmniejsza: log n
− największa: n.