Drzewa binarne - podstawy

1. Czym jest drzewo?

Drzewo to hierarchiczna struktura danych składająca się z węzłów (nodes) połączonych krawędziami (edges).

Kluczowe właściwości:

  • Jeden węzeł korzeń (root) na szczycie
  • Każdy węzeł może mieć dzieci (children)
  • Węzły bez dzieci to liście (leaves)
  • Brak cykli – nie można wrócić do tego samego węzła

Wizualizacja:

        A  ← Korzeń (root)
       / \
      B   C  ← Dzieci A
     / \   \
    D   E   F  ← Liście (leaves)

2. Czym jest drzewo binarne?

Drzewo binarne to drzewo, w którym każdy węzeł ma maksymalnie 2 dzieci: - Lewe dziecko (left child) - Prawe dziecko (right child)

Przykład:

        10
       /  \
      5    15
     / \   / \
    3   7 12  20

3. Terminologia drzew

Podstawowe pojęcia:

           1  ← Korzeń (root), poziom 0, wysokość 3
          / \
         2   3  ← Poziom 1
        / \   \
       4   5   6  ← Poziom 2
      /
     7  ← Liść, poziom 3

Węzeł (Node): - Przechowuje wartość (data) - Wskaźniki do dzieci (left, right) - Opcjonalnie: wskaźnik do rodzica (parent)

Korzeń (Root): Węzeł na szczycie (bez rodzica)

Liść (Leaf): Węzeł bez dzieci

Rodzic (Parent): Węzeł z dziećmi

Dzieci (Children): Węzły poniżej rodzica

Rodzeństwo (Siblings): Węzły z tym samym rodzicem

Przodek (Ancestor): Dowolny węzeł na ścieżce do korzenia

Potomek (Descendant): Dowolny węzeł w poddrzewie

Wysokość (Height): Najdłuższa ścieżka od węzła do liścia - Wysokość drzewa = wysokość korzenia

Głębokość (Depth): Długość ścieżki od korzenia do węzła

Poziom (Level): Głębokość + 1 (korzeń na poziomie 0)

4. Implementacja węzła

Wizualizacja utworzonego drzewa:

      10
     /  \
    5    15
   / \
  3   7

5. Typy drzew binarnych

5.1. Pełne drzewo binarne (Full Binary Tree)

Każdy węzeł ma 0 lub 2 dzieci (nigdy 1).

        1
       / \
      2   3
     / \
    4   5

5.2. Zupełne drzewo binarne (Complete Binary Tree)

Wszystkie poziomy wypełnione oprócz ostatniego (wypełniany od lewej).

        1
       / \
      2   3
     / \  /
    4  5 6

Użycie: Kopce (heaps)

5.3. Doskonałe drzewo binarne (Perfect Binary Tree)

Wszystkie poziomy całkowicie wypełnione.

        1
       / \
      2   3
     / \ / \
    4  5 6  7

Właściwości: - Liczba węzłów: 2^(h+1) - 1 - Wysokość h → 2^(h+1) - 1 węzłów

5.4. Zdegenerowane drzewo (Degenerate Tree)

Każdy węzeł ma tylko 1 dziecko (jak lista).

    1
     \
      2
       \
        3
         \
          4

Najgorszy przypadek – jak linked list!

6. Podstawowe operacje

6.1. Obliczanie wysokości

6.2. Liczenie węzłów

6.3. Liczenie liści

7. Wyszukiwanie w drzewie

7.1. Wyszukiwanie wartości (DFS)

7.2. Wyszukiwanie węzła

8. Minimum i maksimum

9. Wizualizacja drzewa

Wynik:

`-- 10
    |-- 5
    |   |-- 3
    |   |   |-- None
    |   |   `-- None
    |   `-- 7
    |       |-- None
    |       `-- None
    `-- 15
        |-- None
        `-- None

10. Sprawdzanie właściwości drzewa

10.1. Czy drzewo jest pełne?

10.2. Czy drzewo jest zupełne?

11. Porównywanie drzew

12. Tworzenie lustrzanego odbicia

13. Suma wartości w drzewie

14. Najdłuższa ścieżka (średnica)

15. Zastosowania drzew binarnych

15.1. Drzewo wyrażeń

15.2. Drzewo decyzyjne

16. Złożoność operacji

Operacja Złożoność czasowa Uwagi
Wyszukiwanie O(n) Najgorszy: wszystkie węzły
Wstawianie O(n) Zależy od struktury
Usuwanie O(n) Najgorszy: wszystkie węzły
Wysokość O(n) Odwiedź wszystkie węzły
Liczenie węzłów O(n) Odwiedź wszystkie węzły

Uwaga: Dla BST (drzewo binarne wyszukiwań) operacje mogą być O(log n)!

17. Podsumowanie

Drzewo binarne:

  • Hierarchiczna struktura danych
  • Każdy węzeł ma maksymalnie 2 dzieci
  • Kluczowe pojęcia: korzeń, liść, wysokość, głębokość
  • Operacje rekurencyjne: wysokość, liczenie, wyszukiwanie

Typy drzew: - Pełne: 0 lub 2 dzieci - Zupełne: Wypełnione od lewej - Doskonałe: Wszystkie poziomy pełne - Zdegenerowane: Jak lista

Podstawowe operacje: - Wysokość: O(n) - Liczenie węzłów: O(n) - Wyszukiwanie: O(n) - Minimum/maksimum: O(n)

Zastosowania: - Drzewa wyrażeń (matematyka) - Drzewa decyzyjne (AI) - Hierarchie (systemy plików) - Drzewa wyszukiwań (BST)

Zalety: - Naturalna hierarchia - Efektywne operacje (dla zbalansowanych) - Elastyczna struktura

Wady: - Może degenerować do listy O(n) - Wymaga balansowania dla efektywności - Bardziej złożone niż tablice/listy

Co dalej warto poznać:

  • BST (Binary Search Tree) – O(log n) dla zbalansowanych
  • Przechodzenie drzew (in-order, pre-order, post-order)
  • Drzewa AVL – automatyczne balansowanie
  • Kopce (heaps) – struktura priorytetowa
  • B-drzewa – dla baz danych
Wróć do spisu lekcji