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
  1. i = pobierz element z listy
  2. node = korzeń drzewa
  3. Jeśli node nie istnieje, podstaw i pod ten węzeł i wróć do punktu 1
  4. W przeciwnym razie:
    1. Jeśli i <= node, niech node = lewy potomek,
    2. Jeśli i > node, niech node = prawy potomek
  5. 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
  1. i = szukana liczba
  2. node = korzeń drzewa
  3. Jeśli node nie istnieje, odpowiedź brzmi NIE
  4. W przeciwnym razie:
    1. Jeśli node == i, odpowiedź brzmi TAK
    2. Jeśli i < node, niech node = lewy potomek
    3. Jeśli i > node, niech node = prawy potomek
  5. 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
  1. i = szukana liczba
  2. node = korzeń drzewa
  3. Jeśli node nie istnieje, zakończ działanie
  4. W przeciwnym razie:
    1. Jeśli node == i, usuń węzeł i zakończ działanie
    2. Jeśli i < node, niech node = lewy potomek
    3. Jeśli i > node, niech node = prawy potomek
  5. 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
  1. i = pobierz element z listy
  2. Wstaw i do drzewa (by zachować warunek pełności)
  3. Jeśli i > rodzic(i), zamień je miejscami i wykonaj ten sam punkt ponownie
  4. 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
  1. Wstaw w miejsce korzenia ostatni element kopca i niech node = korzeń
  2. Jeśli node jest większy od obu potomków, zakończ działanie
  3. W przeciwnym razie, zamień miejscami node z potomkiem o większej wartości. Dla nowej pozycji node powróć do poprzedniego punktu
  • Przykład. Krok 1
  • Krok 2:
  • Krok 3:
  • Krok 4:

Wskaźniki

  • Deklaracja: (zarówno wskaznik i tablica to zmienne typu wskaźnikowego)
    typ* wskaznik;
    typ tablica[rozmiar];
    [$[Get Code]]
  • Przypisanie adresu do wskaźnika:
    wskaznik = inny_wskaznik;
    wskaznik = &zmienna;
    [$[Get Code]]
  • Odczyt wartości z adresu:
    zmienna = *wskaznik;
    printf("%d\n", *wskaznik);
    [$[Get Code]]
  • Zapis pod wskazany adres:
    *wskaznik = wartosc;
    [$[Get Code]]
  • Działania na wskaźnikach:
    wskaznik++;
    wskaznik--;
    [$[Get Code]]

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]);
    [$[Get Code]]

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;
}
[$[Get Code]]