10

Metodyka i Techniki Programowania II
Binarne struktury drzewiaste (Binary Search Trees)
Piotr Pacyna, Jarosław Bułat

8.05.2010

Wstęp

Drzewo jest strukturą danych, w której każdy węzeł ma wskaźniki mogące wskazywać na inne

węzły (w przypadku węzła binarnego używa się określenia węzeł ‘lewy’ i ‘prawy’). Jeżeli któryś ze
wskaźników nie wskazuje na inny węzeł, wówczas przechowuje wartość null. Istotną cechą

drzewa jest brak pętli w strukturze drzewa.

Następujące określenia dotyczą drzew.

•

Korzeń

– węzeł położony najwyżej (pierwszy w strukturze) – dla drzewa na rysunku

powyżej jest to ten, dla którego wartość klucza wynosi 52.

•

Węzeł macierzysty

– dowolny węzeł, który wskazuje na jeden lub dwa węzły znajdujące się

niżej w strukturze.

•

Węzeł potomny

– węzeł, który jest wskazywany przez węzeł macierzysty. Węzeł potomny

może być również węzłem macierzystym dla innych węzłów.

•

Liść

– węzeł, który nie ma węzłów potomnych.

•

Poziom

– długość ścieżki od korzenia drzewa do danego węzła, mierzona liczbą ‘skoków’

przez węzły pośrednie. Np. węzeł 29 jest na poziomie 1, zaś 62 jest na poziomie 2.

•

Krawędź

– strukturalne powiązanie dwóch węzłów reprezentowane w implementacjach na

ogół za pośrednictwem „wskaźnika do węzła” (pointer).

Struktury drzewiaste łączą zalety znane z innych struktur: z uporządkowanej tablicy oraz z

uporządkowanej listy jednokierunkowej. Dzięki wielokrotnym powiązaniom (pomiędzy elementem
‘macierzystym’ a ‘potomnymi’) można te elementy wzajemnie uporządkować między sobą

(uporządkowanie względne) by potem np. efektywnie przeszukiwać strukturę drzewa w
poszukiwaniu elementu.

Struktura drzewiasta jest binarna, jeżeli węzeł może posiadać co najwyżej dwa węzły potomne.
Binarne drzewo przeszukiwań jest strukturą w której:

•

Węzły przechowują elementy (obiekty danych) indeksowane wartością klucza, który służy

do identyfikowania tych elementów,

•

dla każdego węzła “x” w drzewie wszystkie elementy przechowywane w lewym pod-drzewie
węzła “x” charakteryzują się mniejszymi lub równymi wartościami klucza niż elementy

przechowywane w węźle ”x”, oraz

•

wszystkie elementy przechowywane w prawym pod-drzewie węzła “x” mają wartości kluczy
większe od elementu przechowywanego w węźle ”x”.

Takie drzewo jest uporządkowanym drzewem binarnym.

Uporządkowane drzewa binarne (drzewa binarne przeszukiwań) mają ważną właściwość:

uporządkowane przeszukiwanie drzewa pozwala na odczytanie elementów w rosnącym porządku
odpowiadającej im wartości klucza.

.

Dla drzewa przedstawionego powyżej porządek ten wynosi: 13, 18, 23, 32, 36, 44, 54, 59, 64,

73, 81, 85, 92.

Warunkiem uzyskania takiego wyniku jest budowanie i powiększanie (pomniejszanie) drzewa w
sposób kontrolowany. Wówczas drzewa binarne umożliwiają także efektywne wyszukiwanie

elementów według wartości klucza.

Czas wykonania procedury poszukiwania elementu (lub wstawiania elementu w odpowiednie

miejsce) zależy od wysokości h drzewa, O(h). Wysokość drzewa binarnego jest w przedziale
log

2

n ≤ h ≤ n, gdzie n jest liczbą węzłów, tak więc wartość O(h) z pewnością leży w przedziale;

O(log n) - O(n). W najgorszym przypadku czas przeszukania wynosi O(n), jednak średnia wartość
czasu wykonania procedury (liczona dla różnych ‘przypadków’ kształtu drzewa) wynosi O(log n).

Kształt drzewa zależy od wartości kluczy, które pojawiają się wraz z elementami wstawianymi do
drzewa.

Ćwiczenie 1. Zakładanie drzewa

1. Przestudiuj kod w pliku nagłówkowym bintree.h, zwracając uwagę na deklaracje funkcji:

TBinTree MakeBinTreeNode( TBinTreeData data, int key );

void InsertLeftChild( TBinTree *parent, TBinTree node );

void InsertRightChild( TBinTree *parent, TBinTree node );

2. Przestudiuj uważnie implementacje wyżej wymienionych funkcji przeglądając kod zawarty

w pliku bintree.c .

3. Przestudiuj kod programu main_bintree.c i załóż strukturę drzewiastą składającą się z

węzłów identyfikowanych jako A, B, C, D, E, F, G, H z wartościami klucza odpowiednio a, b,
c, d, e, f, g, h. (do kompilacji użyj załączonego programu Makefile)

Ćwiczenie 2. Łączenie drzew
Wygeneruj drugie drzewo i połącz je ze sobą programowo (uzupełniając kod w main_bintree.c)
w dowolny sposób.

•

Czy powstałe w ten sposób drzewo jest drzewem binarnym ?

•

Czy jest drzewem uporządkowanym ?

Ćwiczenie 3. Liczba liści drzewa
Napisz funkcję, int leafCount( TBinTree tree ), która policzy elementy niemające potomków,

czyli liście drzewa.

Ćwiczenie 4. Wysokośc drzewa
Napisz funkcję int height( TBinTree tree ), która policzy wysokość drzewa.

Ćwiczenie 5. Pokolenie

Napisz funkcję int generation( TBinTree tree, int level ), która policzy ilość węzłów na
określonym poziomie drzewa.

Ćwiczenie 6. Koszt gałęzi

Napisz funkcję int maxPathSum(TBinTree tree) , która policzy największy koszt gałęzi spośród
wszystkich gałęzi występujących w drzewie. Jako koszt przyjmujemy sumę wartości kluczy od

korzenia drzewa do wszystkich liści, wliczając wartości elementów przechowywanych w korzeniu i
w liściu.

Ćwiczenie 7. Rekursywne przeszukiwanie drzewa binarnego (nadobowiązkowe)

Wykorzystując kod źródłowy dołączony do laboratorium skonstruuj strukturę drzewiastą binarną
uporządkowaną składającą się z węzłów identyfikowanych jako A, B, C, D, E, F, G, H z

wartościami klucza odpowiednio 1, 5, 10, 15, 20, 25, 30, 35. Następnie wykonaj przeszukiwanie
według wartości kluczy rekursywne oraz nierekursywne (uzupełnij brakujący kod). Porównaj

szybkość działania, łatwość implementacji oraz zwięzłość kodu źródłowego obu implementacji.