Studia Licencjackie / Inżynierskie

Algorytmy i struktury danych

Wykład 05, część II

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

Poniżej poprawne drzewo BST

5

8

4

3

7

9

5

8

3

1

4

9

Pojęcia

−

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

, …, v

k

taki, że v

i

jest dzieckiem v

i-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);

}

Wstawianie nowego elementu

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

}

}

Usuwanie elementu

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.