BST (Binary Search Tree)
- Struktura drzewa skierowanego
- Graf składający z wierzchołków i łuków
- Łuk (u, v), czyli z wierzchołka u do v, mówi o relacji między nimi; u nazywany jest rodzicem, v potomkiem
- Istnieje jeden wyróżniony wierzchołek nazywany korzeniem, dla którego żaden inny nie jest rodzicem
- Każdy inny wierzchołek posiada dokładnie jednego rodzica i zero, jednego lub dwóch potomków
- Węzły bez potomków nazywane są liśćmi
- Węzły zawierają wartości liczbowe
- Potomkowie węzłów są nazywani lewymi lub prawymi; lewy węzeł jest w relacji mniejszy lub równy względem rodzica; prawy węzeł w relacji większy
- Przy dobrze zrównoważonym drzewie BST, do wyszukania elementu na nim potrzeba wykonać średnio logarytymiczną liczbę kroków (na liście elementów należy wykonać liniową liczbę kroków). Jak wielka to różnica, czyli dlaczego warto wiedzieć i zajmować się BST pokazuje ten przykład:
- 16 elementów, liczba sprawdzeń dla BST = 4, dla listy = 8
- 1024 elementy, dla BST = 10, dla listy = 512
- 65536 elementów, dla BST = 16, dla listy = 32768
Operacja dodawania elementów (tworzenie drzewa)
- Wejście: lista elementów do dodania np. 100, 50, 150, 25, 125, 200, 175, 225
- Wyjście: drzewo BST
i= pobierz element z listynode= korzeń drzewa- Jeśli
nodenie istnieje, podstawipod ten węzeł i wróć do punktu 1 - W przeciwnym razie:
- Jeśli
i<=node, niechnode= lewy potomek, - Jeśli
i>node, niechnode= prawy potomek
- Jeśli
- Wróć do punktu 3
- UWAGA: Algorytm jest zależny od porządku liczb w wejściowej liście. Dla przykładowych danych w zadaniu powstanie drzewo BST takie jak na początku tej sekcji. Gdyby jednak dane uporządkować rosnąco i zbudować nowe drzewo, powstanie zdegenerowana struktura danych:
Operacja wyszukiwania elementu
- Wejście: liczba oraz zbudowane drzewo BST
- Wyjście: TAK, jeśli liczba jest elementem drzewa, NIE w przeciwnym razie
i= szukana liczbanode= korzeń drzewa- Jeśli
nodenie istnieje, odpowiedź brzmi NIE - W przeciwnym razie:
- Jeśli
node==i, odpowiedź brzmi TAK - Jeśli
i<node, niechnode= lewy potomek - Jeśli
i>node, niechnode= prawy potomek
- Jeśli
- Wróć do punktu 3
Operacja usuwania elementu
- Wejście: liczba oraz zbudowane drzewo BST
- Wyjście: drzewo BST bez elementu określonego na wejściu
i= szukana liczbanode= korzeń drzewa- Jeśli
nodenie istnieje, zakończ działanie - W przeciwnym razie:
- Jeśli
node==i, usuń węzeł i zakończ działanie - Jeśli
i<node, niechnode= lewy potomek - Jeśli
i>node, niechnode= prawy potomek
- Jeśli
- Wróć do punktu 3
- UWAGA: Samo usuwanie węzła ma trzy postaci w zależności od liczby potomków:
- Jeśli węzeł jest liściem (ma zero potomków), usunięcie go wystarczy (nie potrzeba reorganizować drzewa). Przykład dla liczby 225:
- Jeśli węzeł ma jednego potomka, należy nim zastąpić miejsce usuniętego elementu. Przykład dla liczby 50:
- Jeśli węzeł ma dwóch potomków, należy zastąpić go największym elementem lewego poddrzewa lub najmniejszym elementem prawego poddrzewa. Przykład dla liczby 150 (zarówno drugie i trzecie drzewo BST są prawidłowo zreorganizowane)
Kopiec / stóg (ang. heap)
- Struktura drzewa binarnego podobna jak przy BST z następującymi różnicami:
- Obaj potomkowie mają mniejszą wartość niż bieżący węzeł (nie ma rozróżnienia na lewego i prawego potomka)
- Drzewo ma zawsze zachowany warunek pełności: (UWAGA: W trzech kolejnych rysunkach wyjątkowo numery wewnątrz węzłów nie są wartościami, a jedynie INDEKSAMI w drzewie. W drzewie pełnym indeksowanie takie jest zawsze możliwe [numerowanie węzłów od korzenia po liście] i gdy chcemy dodać nowy element, dopisujemy go na pierwszym wolnym indeksie, a gdy chcemy usunąć to znajdujemy ostatni zajęty indeks)
- Drzewo pełne (wysokość 3):
- Jest 10 elementów, pierwszy wolny indeks to 11 (użyteczne przy tworzeniu kopca, patrz też niżej):
- Jest 6 elementów, ostatni zajęty indeks to 6 (użyteczne przy usuwaniu korzenia, patrz też niżej):
- Motywacja wykorzystania kopca jest taka, że w korzeniu przechowuje on maksimum ze zbioru danych. Jest to wartość łatwo dostępna, a charakterystyka kopca sprawia, że dodawanie nowych elementów lub zdejmowanie korzenia wymaga jedynie logarytmicznej liczby kroków by odbudować strukturę danych (o zaletach logarytmicznej złożoności względem liniowej można przeczytać w punkcie o drzewie BST)
Operacja dodawania elementów (tworzenie kopca)
- Wejście: lista elementów do dodania np. 100, 50, 150, 25, 125, 200, 175, 225
- Wyjście: kopiec
i= pobierz element z listy- Wstaw
ido drzewa (by zachować warunek pełności) - Jeśli
i>rodzic(i), zamień je miejscami i wykonaj ten sam punkt ponownie - W przeciwnym razie, wróć do punktu 1
- Przykładowe tworzenie drzewa dla danych powyżej. Krok 1:
- Krok 2:
- Krok 3:
- Krok 4:
- Krok 5:
- Krok 6:
- Krok 7:
- Krok 8:
Operacja usuwania korzenia
- Wejście: kopiec
- Wyjście: odbudowany kopiec po usunięciu korzenia
- Wstaw w miejsce korzenia ostatni element kopca i niech
node= korzeń - Jeśli
nodejest większy od obu potomków, zakończ działanie - W przeciwnym razie, zamień miejscami
nodez potomkiem o większej wartości. Dla nowej pozycjinodepowróć do poprzedniego punktu
- Przykład. Krok 1
- Krok 2:
- Krok 3:
- Krok 4:
Wskaźniki
- Deklaracja: (zarówno
wskaznikitablicato zmienne typu wskaźnikowego)typ* wskaznik;
typ tablica[rozmiar]; - Przypisanie adresu do wskaźnika:
wskaznik = inny_wskaznik;
wskaznik = &zmienna; - Odczyt wartości z adresu:
zmienna = *wskaznik;
printf("%d\n", *wskaznik); - Zapis pod wskazany adres:
*wskaznik = wartosc;
- Działania na wskaźnikach:
wskaznik++;
wskaznik--;
Napisy w C
- Napisy to zmienne typu
char* - Każdy napis kończy się wartością 0
- Każda litera to liczba w kodzie ASCII np. cyfra 7 ma kod
0x37 = 55 - Wczytywanie napisów i znaków:
char tablica[10];
char *wskaznik;
char znak;
// wczytaj napis do tablicy (BEZ AMPERSANDA PRZY ZMIENNEJ!)
scanf("%s", tablica);
// oba zapisy sa tozsame
wskaznik = tablica;
wskaznik = &tablica[0];
// wczytaj napis pod wskaznik (BEZ AMPERSANDA PRZY ZMIENNEJ!)
scanf("%s", wskaznik);
// wczytaj litere (Z AMPERSANDEM PRZY ZMIENNEJ!)
scanf("%c", &znak);
scanf("%c"m &tablica[2]);
Kod zadania z laboratoriów
#include <stdio.h>
/******************************************************************************
* Wyznacz dlugosc napisu `s`.
*
* Przyklad:
* wejscie: s = "TEST"
* wyjscie: 4
*****************************************************************************/
int strlen(char* s) {
int n = 0;
// petla ma sie wykonywac dopoki nie napotkamy zera (konca napisu)
while (*s != 0) {
n++; // zwieksz licznik dlugosci napisu
s++; // przesun sie do nastepnego znaku w napisie
}
return n;
}
/******************************************************************************
* Sprawdz czy w napisie `s` znajduje sie litera `c`.
*
* Przyklad:
* wejscie: s = "TEST", c = 'P'
* wyjscie: 0
*
* wejscie: s = "TEST", c = 'E'
* wyjscie: 1
*****************************************************************************/
int contains(char* s, char c) {
// wykonuj dopoki nie napotkasz zera (konca napisu)
while (*s != 0) {
// jesli znajdziesz szukany znak `c`, zakoncz z wynikiem 1
if (*s == c) {
return 1;
}
// w przeciwnym razie, przesun sie do kolejnego znaku w napisie
s++;
}
return 0;
}
/******************************************************************************
* Wypisz napis `s` w odwrotnej kolejnosci.
*
* Przyklad:
* wejscie: s = "ABCD"
* na ekranie: DCBA
*****************************************************************************/
void print_rev(char *s) {
char *ps = s;
// przesun sie na koniec napisu
while (*ps != 0) {
ps++;
}
do {
ps--; // wycofaj sie o jedna pozycje w napisie
printf("%c", *ps); // wypisz znak
} while (ps != s); // zakoncz petle jesli wrociles do poczatku napisu
}
int main() {
char s[10];
scanf("%s", s);
int n = strlen(s);
printf("Dlugosc napisu: %d\n", n);
char c = 's';
int flag = contains(s, c);
printf("Czy napis zawiera litere %c: %s\n", c, flag ? "TAK" : "NIE");
printf("Napis odwrocony: ");
print_rev(s);
printf("\n");
return 0;
}
/******************************************************************************
* Wyznacz dlugosc napisu `s`.
*
* Przyklad:
* wejscie: s = "TEST"
* wyjscie: 4
*****************************************************************************/
int strlen(char* s) {
int n = 0;
// petla ma sie wykonywac dopoki nie napotkamy zera (konca napisu)
while (*s != 0) {
n++; // zwieksz licznik dlugosci napisu
s++; // przesun sie do nastepnego znaku w napisie
}
return n;
}
/******************************************************************************
* Sprawdz czy w napisie `s` znajduje sie litera `c`.
*
* Przyklad:
* wejscie: s = "TEST", c = 'P'
* wyjscie: 0
*
* wejscie: s = "TEST", c = 'E'
* wyjscie: 1
*****************************************************************************/
int contains(char* s, char c) {
// wykonuj dopoki nie napotkasz zera (konca napisu)
while (*s != 0) {
// jesli znajdziesz szukany znak `c`, zakoncz z wynikiem 1
if (*s == c) {
return 1;
}
// w przeciwnym razie, przesun sie do kolejnego znaku w napisie
s++;
}
return 0;
}
/******************************************************************************
* Wypisz napis `s` w odwrotnej kolejnosci.
*
* Przyklad:
* wejscie: s = "ABCD"
* na ekranie: DCBA
*****************************************************************************/
void print_rev(char *s) {
char *ps = s;
// przesun sie na koniec napisu
while (*ps != 0) {
ps++;
}
do {
ps--; // wycofaj sie o jedna pozycje w napisie
printf("%c", *ps); // wypisz znak
} while (ps != s); // zakoncz petle jesli wrociles do poczatku napisu
}
int main() {
char s[10];
scanf("%s", s);
int n = strlen(s);
printf("Dlugosc napisu: %d\n", n);
char c = 's';
int flag = contains(s, c);
printf("Czy napis zawiera litere %c: %s\n", c, flag ? "TAK" : "NIE");
printf("Napis odwrocony: ");
print_rev(s);
printf("\n");
return 0;
}