Dawno się nie widzieliśmy! Właśnie z tego powodu przygotowałem dla Was kolejny wpis. Tym razem, nie podejmiemy się jednak tematu algorytmów sortowania, a kontynuować będziemy serię dotyczącą struktur danych. Zanim rozpoczniecie czytanie poniższego wpisu, zachęcam was do zapoznania się z poprzednimi częściami tej serii. Znajdziecie w nich opis stosu, listy jednokierunkowej oraz dwukierunkowej. W tych wpisach poznacie zagadnienia powiązane z podstawami struktur danych, które warto znać jako przyszły programista. Przejdźmy jednak do właściwej części tekstu, w której odpowiemy sobie na najważniejsze pytanie.
Czym jest drzewo?
Drzewo jako struktura danych, to grupa węzłów połączonych krawędziami. Węzeł początkowy, nazywany jest powszechnie korzeniem (root), a wierzchołki z których nie wychodzą żadne krawędzie, liśćmi (leafs). Każdy węzeł połączony z węzłem wyżej jest jego dzieckiem.
Jeżeli w drzewie każdy z węzłów ma maksymalnie dwoje dzieci, jest to drzewo binarne. W tym tekście omówimy sobie dokładniej BST (binary search tree) – podstawowy rodzaj drzewa binarnego.
BST, czyli binarne drzewo poszukiwań posiada jedną cechę charakterystyczną – po lewej stronie każdego poddrzewa znajdują się elementy mniejsze od wartości korzenia tego poddrzewa, a po prawej większe bądź równe. Może wydawać się to dość skomplikowane, lecz łatwo zrozumieć zasadę jego działania dzięki przykładowi.
BST – zasada działania
Weźmy drzewo, które posiada na początku tylko jeden węzeł (korzeń) o wartości 12. Chcąc dodać do tego drzewa nowy węzeł o wartości 5, przyrównujemy wartość nowego węzła do węzła początkowego. Jeśli będzie większa bądź równa idziemy na prawo, w przeciwnym wypadku idziemy na lewo. 5 jest mniejsze od 12, a co za tym idzie poruszamy się na lewo. Ze względu na to, że korzeń nie ma żadnych dzieci, lewa strona jest pusta. Oznacza to, że możemy wstawić w tym miejscu węzeł. Następnie wstawmy węzeł o wartości 33. Analogicznie poruszamy się w prawo, gdzie znajdziemy wolne miejsce na węzeł. Co należy jednak zrobić, gdy zechcemy w tym momencie wstawić do drzewa węzeł o wartości 7?
W pierwszym kroku przyrównujemy wartość nowego węzła do wartości korzenia. Ze względu na to, że wartość 7 jest mniejsza od 12, przechodzimy w lewo. Następnie przyrównujemy wartość 7 do wartości lewego dziecka korzenia, czyli 5. Wartość tego węzła jest mniejsza od wartości nowego, tak więc przechodzimy w prawo. Tam nie znajdziemy żadnego węzła, więc możemy wstawić w tym miejscu węzeł o wartości 7. Poniższa animacja pomoże wam zobrazować sobie ten przykład.
Podsumowując – gdy chcemy dodać jakikolwiek nowy węzeł staramy się znaleźć wolne miejsce, przechodząc w prawo, jeśli wartość nowego węzła jest większa bądź równa od aktualnie wskazywanego, lub w lewo, gdy jest mniejsza.
Drzewo BST – implementacja w C++
Nim zaprezentuję wam kod, należy poruszyć ważną kwestię. Według zasad drzewa BST, każdy z węzłów musi przechowywać przynajmniej: zmienną wartości węzła, wskaźnik na rodzica, wskaźnik na lewe dziecko i wskaźnik na prawe dziecko. Jeśli dany węzeł nie ma dziecka, po danej stronie, wskaźnik należy ustawić na wartość NULL. Dzięki temu, jesteśmy w stanie zweryfikować w prosty sposób czy dany wskaźnik wskazuje na dziecko, czy na pustą przestrzeń.
Poniższa implementacja posiada funkcje pozwalające na dodanie węzła, usunięcie węzła oraz znalezienie maksymalnej i minimalnej wartości w drzewie.
//program do obslugi BST
//Jan Żwirek
#include <iostream>
#include <fstream>
#include <Windows.h>
#include <string>
using namespace std;
struct node {
int key;
struct node *left;
struct node *right;
struct node *parent;
};
//Wskaznik na korzen
struct node *root = NULL;
/*
Funkcja dodawania wezla - funkcja ta przechodzi przez drzewo
w poszukiwaniu wolnego miejsca na wezel. Jesli wartosc nowego wezla
jest mniejsza od aktualnego, przechodzi w lewo, w przeciwnym przypadku
przechodzimy w prawo. Gdy natkniemy sie na wartosc null wstawiamy tam
nowy wezel pamietajac o przypisaniu wskaznikow.
*/
void add_node(int val) {
//tworzymy wskazniki wskazujace na aktualnie rozpatrywany wezel i nowy wezel
struct node *now = root;
struct node *addedNode = new node;
//Przypisujemy wartosci do wezla
addedNode->key = val;
addedNode->left = NULL;
addedNode->right = NULL;
//Jesli korzen ma wartosc null, nowy wezel staje sie korzeniem
if (root == NULL) {
addedNode->parent = NULL;
root = addedNode;
return;
}
else {
while (now!= NULL) {
//wartosc nowego wezla jest wieksza badz rowna od wskazywanego
if (now->key <= addedNode->key) {
//jesli po prawej jest wolne miejsce dodajemy w nie wezel
if (now->right == NULL) {
addedNode->parent = now;
now->right = addedNode;
return;
}
//w innym przypadku przechodzimy w glab drzewa
else {
now = now->right;
}
}
//wartosc nowego wezla jest mniejsza od wskazywanego
if (now->key > addedNode->key) {
//jesli po lewej jest wolne miejsce dodajemy w nie wezel
if (now->left == NULL) {
addedNode->parent = now;
now->left = addedNode;
return;
}
//w innym przypadku przechodzimy w glab drzewa
else {
now = now->left;
}
}
}
}
}
/*
Funkcja usuwania wezla - funkcja przechodzi po drzewie w poszukiwaniu
wezla o zadanej wartosci. Jesli szukana wartosc jest mniejsza od wartosci
aktualnie wskazywanego wezla, przechodzi w lewo, w przeciwnym przypadku
przechodzimy w prawo. Jesli znajdziemy wezel o zadanej wartosci, usuwamy go.
W przypadku gdy posiadal jakiekolwiek dzieci, wstawiamy je w wolne miejsce.
Jesli zadana wartosc nie znajduje sie w drzewie, zwracamy NULL.
*/
struct node* del_node_key(struct node* node, int find) {
if (node == NULL)
return node;
if (find < node->key) {
return node->left = del_node_key(node->left, find); //Rekurencyjne przejście do szukanej wartości
}
else if (find > node->key) {
return node->right = del_node_key(node->right, find);
}
if (find == node->key) {
//Jeśli drzewo składa sie z samego korzenia
if (root->left == NULL && root->right == NULL) {
delete(root);
root = NULL;
return NULL;
}
//Wsunięcie prawego syna na miejsce aktualnie wskazywanego
if (node->left == NULL) {
struct node *tmp = node->right;
delete(node);
return tmp;
}
//Wsunięcie lewego syna na miejsce aktualnie wskazywanego
else if (node->right == NULL) {
struct node *tmp = node->left;
delete(node);
return tmp;
}
//Przypadek gdy wskazywany węzeł ma dwóch synów
struct node* tmp = node->right;
node->key = tmp->key;
while (tmp->left != NULL) {
tmp = tmp->left;
}
//Znalezienie następcy
node->right = del_node_key(node->right, tmp->key);
}
return node;
}
//Szukanie najwiekszej wartosci w drzewie - skrajny prawy wezel
int find_max() {
struct node *now = root;
//przejście do ostatniego elementu po prawej
while (now->right != NULL) {
now = now->right;
}
return now->key;
}
//Szukanie najmniejszej wartosci w drzewie - skrajny lewy wezel
int find_min() {
struct node *now = root;
//przejście do ostatniego elementu po lewej
while (now->left != NULL) {
now = now->left;
}
return now->key;
}
int main()
{
bool isRunning = true;
int answ, inpu;
while (isRunning) {
system("cls");
cout << endl;
cout << "###########MENU###########" << endl;
cout << "[1] Dodaj wezel" << endl;
cout << "[2] Usun wezel" << endl;
cout << "[3] Znajdz najmniejsza wartosc" << endl;
cout << "[4] Znajdz najwieksza wartosc" << endl;
cout << "[5] Wyjdz" << endl;
cout << "##########################" << endl;
cin >> answ;
cout << endl;
switch (answ) {
case 1: {
cout << "Wporwadz wartosc wezla: ";
cin >> inpu;
add_node(inpu);
break;
}
case 2: {
cout << "Wprowadz wartosc do usuniecia: ";
cin >> inpu;
if (root == NULL) {
cout << "Brak korzenia - drzewo jest puste" << endl;
}
system("PAUSE");
break;
}
case 3: {
cout << "Najmniejsza wartosc = " << find_min() << endl;
system("PAUSE");
break;
}
case 4: {
cout << "Najwieksza wartosc = " << find_max() << endl;
system("PAUSE");
break;
}
case 5: {
isRunning = false;
break;
}
default: {
cout << "Zly wybor!" << endl;
system("PAUSE");
break;
}
}
}
return 0;
}Podsumowanie
Drzewa (a zwłaszcza te binarne) to niezwykle popularny rodzaj struktury danych w informatyce. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych. Warto więc znać zasadę ich działania.
