Temat : Drzewa przeszukiwań binarnych BST.

Opracował :

chodek

1. Cel ćwiczenia.

Ćwiczenie ma na celu zapoznanie studentów z drzewami przeszukiwań binarnych - BST (ang. Binary Search Tree) . W szczególności podstawowe operacje możliwe do wykonania na wyżej wymienionych strukturach tj. przeszukiwanie, szukanie minimum oraz maksimum, wstawianie oraz usuwanie elementów w drzewie.

2. Wstęp teoretyczny.

W informatyce Drzewo binarne to drzewiasta struktura danych, w której liczba synów każdego wierzchołka wynosi nie więcej niż dwa. Wyróżnia się wtedy lewego syna i prawego syna danego wierzchołka.

Drzewo poszukiwań binarnych (skrót BST, z ang. Binary Search Tree) jest dynamiczną strukturą danych w postaci drzewa binarnego.

W każdym z węzłów drzewa przechowywana jest pewna wartość przy czym: wartość przechowywana w węźle jest większa od wartości przechowywanej w lewym synu i mniejsza od wartości przechowywanej w prawym synu. (Relacja może być odwrócona, to kwestia umowy.) Przechodząc drzewo metodą inorder uzyskuje się ciąg wartości posortowanych rosnąco.

Z reguły w węźle przechowuje się więcej informacji, a wartość węzła ma jedynie posłużyć do ich wyszukiwania - dlatego bywa nazywana kluczem.

Aby znaleźć węzeł drzewa w którym jest wartość x, porównujemy x z wartością k w korzeniu i w zależności od wyniku porównania:

x = k - cieszymy się, że znaleźliśmy

x < k - szukamy w lewym poddrzewie

x > k - szukamy w prawym poddrzewie

Jeśli dojdziemy w ten sposób do pustego drzewa - to znaczy że elementu nie ma w drzewie. Nowe elementy wstawiamy w liściach - postępując podobnie jak przy wyszukiwaniu.

Nieco gorzej jest z usuwaniem - po znalezieniu węzła x, który chcemy usunąć należy rozpatrzyć różne przypadki:

jeśli x nie ma synów - po prostu usunąć

jeśli x ma tylko jednego syna - zastąpić go synem

jeśli x ma dwóch synów:

znaleźć jego następnik y, (najbardziej lewy element w prawym poddrzewie x)

zastąpić zawartość węzła x przez zawartość węzła y

wyciąć węzeł y (syn y stanie się synem swojego dziadka)

Pesymistyczny koszt każdej z tych operacji na drzewie BST o n węzłach zależy od wysokości drzewa i wynosi:

log₂(n) - dla drzewa zrównoważonego, oraz O(n) - dla przypadku pesymistycznego.

Dlatego w praktyce często lepiej zastosować drzewo poszukiwań binarnych o dodatkowych właściwościach - np. drzewo czerwono-czarne - które pozwala wykonywać operacje wstawiania i usuwania węzłów z zachowaniem zrównoważenia. [2]

3 . Przykładowa implementacji.

Dla zaprezentowania możliwości drzewa BST stworzono klasę o nazwie BSTTree, opartą o system wzorców języka C++, dzięki czemu możemy wykorzystywać dowolny klucz według którego będziemy wyszukiwać dane. Podana klasa znajduje się w pliku nagłówkowym „BSTTree.h”. Niestety funkcjonalność podanej klasy jest żadna ponieważ nie posiada ona żadnego „pola” w którym mogła by przechowywać wartość skojarzoną z kluczem, tak więc należało by dodać odpowiednią implementacje.

#ifndef _BSTTREE_H_

#define _BSTTREE_H_ 1

#include <cassert>

template<typename T>

class BSTTree {

public:

//definicja strukutry pojedynczego elementu drzewa

typedef struct TNode {

TNode *parent;

TNode *left;

TNode *right;

T item;

} TNode;

typedef TNode* TNodePtr;

BSTTree(): root(NULL) {};

~BSTTree() {

//usuniecie wszystkiego co zostało

while(root!= NULL) DelNode(root);

}

//dodanie iteracyjne klucza do drzewa

bool AddItem(T &item) {

TNodePtr tparent = NULL;

TNodePtr tchild = root;

while(tchild != NULL) {

tparent = tchild;

if( tchild->item < item) tchild = tchild->right;

else tchild = tchild->left;

}

return PutItem(tparent , item);

}

//dodanie rekurencyjne elementu

bool AddItemRec(T &item) {

return PutItem(AddRec(item , root) , item);

}

//wykasowanie odpowiedniego elementu drzewa

void DelNode(TNodePtr node) {

assert(node != NULL);

TNodePtr tmp, stmp = NULL;

if(node->left == NULL || node->right == NULL) tmp = node;

else tmp = GetSucc(node); //przypadke gdy dwie jedynki

if (tmp->left != NULL) stmp = tmp->left;

else stmp = tmp->right;

if(stmp != NULL) { //gdy podmieniamy rodziców czyli 2 i 3 przypadek

stmp->parent = tmp->parent;

}//tutaj w innym przypadku parent NULL

if (tmp->parent == NULL) { //to znaczy ze jest korzeniem

root = stmp;

}

else if (tmp == tmp->parent->left) tmp->parent->left = stmp;

else tmp->parent->right = stmp;

if(node != tmp) { //prepisanie

node->item = tmp->item;

}

delete tmp; //zwolnienie pamieci

}

//usuniecie elementu o danym kluczu

bool DelItem(const T &item) {

TNodePtr node = FindItem(item);

if(node) { //jezeli istnieje to usuwamy

DelNode(node);

return true;

}

else return false;

}

//znalezienie minimalnej wartosci klucza w drzewie

static TNodePtr GetMin(TNodePtr node) {

assert(node != NULL);

TNodePtr tmp = node;

while(tmp->left != NULL) tmp = tmp->left;

return tmp;

}

//znalezienie maksymalnej wartosci klucza w drzewie

static TNodePtr GetMax(TNodePtr node) {

assert(node != NULL);

TNodePtr tmp = node;

while(tmp->right != NULL) tmp = tmp->right;

return tmp;

}

//znalezeinie nastepnika

TNodePtr GetSucc(const TNodePtr node) {

assert(node != NULL);

if(node->right != NULL) return GetMin(node->right);

else {

TNodePtr tmp = node->parent;

while(tmp != NULL && tmp->right != NULL) tmp = tmp->parent;

return tmp;

}

}

//znalezienie poprzednika

TNodePtr GetPred(const TNodePtr node) {

assert(node != NULL);

if(node->left != NULL) return GetMax(node->left);

else {

TNodePtr tmp = node->parent;

while(tmp != NULL && tmp->left != NULL) tmp = tmp->parent;

return tmp;

}

}

//znalezienie klucza o danej wartosci

TNodePtr FindItem(const T &item) {

TNodePtr tmp = root;

while(tmp != NULL && item != tmp->item) {

if(tmp->item < item) tmp = tmp->right;

else tmp = tmp->left;

}

return tmp;

}

//znalezienie klucza o maxymalnej wartosci

const T* GetMaxVal() {

if(root == NULL) return NULL;

TNodePtr tmp = GetMax(root);

return (const T*)&tmp->item;

}

//znalezienie klucza o minimalnej wartosci

const T* GetMinVal() {

if (root == NULL) return NULL;

TNodePtr tmp = GetMin(root);

return (const T*)&tmp->item;

}

protected:

private:

//dodanie elementu gdzie rodzicem jest parent i item wartosc klucza dziecka

bool PutItem(TNodePtr parent, T &item) {

TNodePtr node = new TNode;

if (node == NULL) return false;

node->left = NULL;

node->right = NULL;

node->item = item;

if (parent == NULL) {

root = node;

root->parent = NULL;

}

else if (parent->item < item) {

parent->right = node;

node->parent = parent;

}

else {

parent->left = node;

node->parent = parent;

}

return true;

}

//znalezienie miejsca do wstawienia w drzewie rekurencyjnie

TNodePtr AddRec(T &item, TNodePtr node) {

if(node->item < item && node->right != NULL)

return AddRec(item , node->right);

else if (node->left != NULL)

return AddRec(item , node->left);

else return node;

}

TNodePtr root;

};

#endif //_BSTTREE_H_

4. Wyniki przeprowadzonych doświadczeń.

Wszystkie badania zostały przeprowadzone na komputerze o następujących parametrach technicznych:

Procesor AMD Duron 1400@2000Mhz

Płyta główna EPOX 8RDA3

Pamięci Kingston DDR400 512MB

Powyższy komputer pracuje pod kontrolą systemu Windows XP.

Na danej strukturze ciężko dokonać testów wydajnościowych, ponieważ przy losowym wypełnianiu drzewa nigdy ostatecznie nie wiemy jakich wartości możemy się spodziewać. Ostatecznie w ekstremalnych przypadkach dojdziemy do ostatnich liści drzewa lub tylko korzenia. Test wstawienia elementu do drzewa, dodanie elementu do drzewa, wyszukanie wartości maksymalnej oraz minimalnej. Operacja usuwania została pominięta ponieważ składa się ona z operacji wyszukania, operacja znalezienia następnika oraz poprzednika składają się z operacji wyszukania maksimum lub minimum w danym drzewie. Prób dokonano na drzewie wypełnionym losowymi wartościami typu int(stałopozycyjny) z zakresu 0 - 64999 o 100 000 elementów.

Wykonane doświadczenia pokazują iż niestety funkcja zliczająca czas jest za mało dokładna dlatego też wyniki pomiarów nie są miarodajne(mimo powtarzalności i sumowania czasów).

Wykres przedstawia czas wykonania wyszukania, dodania , znalezienia maksymalnej i minimalnej wartości w drzewie BST.

Wyszukanie	Wstawianie	Maksymalna wartość	Minimalna wartość
16	0	0	0
0	16	0	0
0	15	0	0
0	0	0	15
0	16	0	0
0	16	0	0
0	15	0	0
0	0	0	0
0	16	0	0
0	15	0	0
0	0	0	0
15	16	0	0

Okazuje się iż operacje wykonywane na wskaźnikach są bardzo szybkie. Nie mniej jednak można zauważyć, że funkcja dodania wykonuje się niemal w stałym czasie. Dzieje się tak ponieważ następuje wywołanie funkcji systemowych do alokacji pamięci(podobnie funkcja usunięcia elementu z drzewa) i to ich wykonanie pochłania większość czasu. Niemniej jednak należy pamiętać, iż przy inaczej rozłożonym(np. posortowanym) drzewie binarnym czasy wyszukania, wstawienia elementu będą się znacznie różnić.

5.Wnioski.

Drzewa BST wykorzystywane są szczególnie jako słowniki oraz kolejki pryjorytetowe (np. biblioteka STL struktura <map> lub <multimap>). Należy pamiętać iż każda operacja na drzewie jest obarczona „kosztem” wykonania(inaczej niż np. w tablicy gdzie wstawiamy element i nie wykonujemy dodatkowych czynności), tak więc jeżeli ważne jest dla nas szybkie wstawianie elementów, struktury te mogą okazać się za wolne. Należy przy tym pamiętać iż dane w drzewach są „względnie posortowane” dlatego też czas wykonania operacji jest szybki.

Niestety dla danych posortowanych i odwrotnie posortowanych dochodzimy do sytuacji gdy z drzewa tworzy się lista, co strasznie wydłuża nam czas przeszukania drzewa, dodania elementu itp. W takiej sytuacji wysokość drzewa równa się wysokości drzewa.

Operacje wstawiania, wyszukiwania, usuwania, szukania maksymalnej oraz minimalnej wartości, następnika, poprzednika w pesymistycznym przypadku działają w czasie O(n), a w przypadku drzewa zrównoważonego log₂(n), gdzie n - ilość węzłów w drzewie.[2]

Przy dodawaniu większej ilości danych znaczną część czasu zajmuje alokacja pamięci. W przypadku wstawiania większej ilości danych należało by jednorazowo zaalokować większy obszar pamięci, co pozwoliło by przyspieszyć działanie algorytmu wstawiania danych.

Dla jednakowych kluczy w drzewie powstaje problem rozłożenia tych elementów, możemy np. zastosować listę w której będziemy przechowywać wartości o danym kluczu.

Drzewa BST przy nierównomiernym rozłożeniu danych tracą coraz bardziej swoją funkcjonalność. Rozwiązaniem może okazać się zastosowanie drzewa Czerwono-Czarnego, aczkolwiek wprowadzanie elementów wiązało będzie się z jeszcze większymi kosztami, ponieważ dojdą funkcje odpowiedzialne za równoważenie drzewa.

Należy zwrócić szczególną uwagę na narzut pamięciowy jaki jest wymagany, minimalna ilość informacji o jednym liściu to 3 * wskaźniki(rodzic, dwóch synów) + klucz +wartość danych dla klucza, w przypadku przechowywania małego elementu może okazać się, że sama struktura jest np. 4x większa od samego elementu.

Podsumowując podana struktura może mieć zastosowanie wszędzie tam gdzie istotne jest szybkie wyszukiwanie informacji, czyli różnego rodzaju bazy danych, słowniki itp. Należy przy tym pamiętać, iż dodanie pojedynczego elementu wiąże się ze stałym nakładem „kosztów”. Nie mniej jednak większość operacji jakie są dokonywane w bazach to operacje wyszukania danych.

Literatura

[1] „Wprowadzenie do algorytmów” Thomas. H. Cormen , Charles E. Leiserson , Ronald L. Rivest

[2] http://pl.wikipedia.org/

[3] http://prioris.mini.pw.edu.pl

[4] instrukcja do ćwiczenia

---