Nr 01 · Słownik · Teoria informatyki · Algorytmy i struktury danych

Drzewa i sterty

20 pojęć w 12 podgrupach, z prostymi definicjami i źródłami.

Drzewa binarne · 1

  • 01drzewo binarneDrzewo, w którym każdy węzeł ma co najwyżej dwoje dzieci, oznaczane jako lewe i prawe.

Drzewa prefiksowe · 1

  • 01drzewo trietrieDrzewo prefiksowe, w którym ścieżka od korzenia koduje kolejne symbole klucza, a wspólne prefiksy współdzielą gałęzie.

Drzewa wielodrozne · 1

  • 01drzewo BZrównoważone drzewo wyszukiwań o wielu kluczach w węźle, zaprojektowane do efektywnego dostępu blokowego na pamięci zewnętrznej.

Drzewa wyszukiwan · 1

  • 01drzewo BSTBST = binary search treeDrzewo binarne z porządkiem: klucze w lewym poddrzewie ≤ klucz węzła ≤ klucze w prawym poddrzewie, co umożliwia wyszukiwanie.

Drzewa zrownowazone · 3

  • 01drzewo AVLSamobalansujące się drzewo wyszukiwań, w którym wysokości poddrzew każdego węzła różnią się o co najwyżej 1.
  • 02drzewo czerwono-czarneSamobalansujące się drzewo wyszukiwań z kolorowaniem węzłów, w którym niezmienniki kolorów gwarantują logarytmiczną wysokość.
  • 03drzewo zrównoważoneDrzewo wyszukiwań utrzymujące wysokość rzędu logarytmu liczby węzłów, co gwarantuje logarytmiczny koszt operacji.

Elementy drzewa · 2

  • 01liśćwęzeł zewnętrznyWęzeł drzewa nieposiadający dzieci, kończący ścieżkę od korzenia.
  • 02poddrzewoFragment drzewa złożony z wybranego węzła i wszystkich jego potomków, sam będący drzewem ukorzenionym.

Ksztalty drzew · 2

  • 01drzewo pełnedrzewo doskonałeDrzewo binarne, w którym każdy węzeł ma zero lub dwoje dzieci, a wszystkie liście są na tym samym poziomie.
  • 02drzewo zupełneDrzewo binarne, którego wszystkie poziomy poza ostatnim są pełne, a liście ostatniego poziomu wypełniają je od lewej.

Operacje na drzewach · 2

  • 01przechodzenie drzewaSystematyczne odwiedzanie każdego węzła drzewa, w porządku in-order, pre-order, post-order lub wszerz.
  • 02rotacjaLokalna operacja restrukturyzująca drzewo wyszukiwań, zmieniająca układ trzech węzłów z zachowaniem porządku, używana do balansowania.

Operacje na stercie · 1

  • 01kopcowanieheapifyOperacja przywracania własności kopca przez przesuwanie węzła w dół lub w górę, podstawowy krok budowy i aktualizacji sterty.

Parametry drzew · 2

  • 01głębokość węzłaLiczba krawędzi na ścieżce od korzenia do danego węzła; korzeń ma głębokość zero.
  • 02wysokość drzewaDługość najdłuższej ścieżki od korzenia do liścia, mierzona liczbą krawędzi; determinuje koszt operacji.

Sterty · 2

  • 01kopiec binarnyNiemal pełne drzewo binarne spełniające własność kopca, zwykle reprezentowane w tablicy, używane do implementacji kolejki priorytetowej.
  • 02własność kopcaNiezmiennik porządkujący: klucz każdego węzła jest nie mniejszy (kopiec max) lub nie większy (kopiec min) od kluczy jego dzieci.

Sterty zlaczalne · 2

  • 01kopiec dwumianowySterta zbudowana z kolekcji drzew dwumianowych, wspierająca efektywne łączenie dwóch stert.
  • 02kopiec FibonacciegoSterta złączalna o zamortyzowanym stałym koszcie wstawiania i zmniejszania klucza, zbudowana z lasu drzew o luźnej strukturze.

Pozostałe grupy — Algorytmy i struktury danych

Grupa pojęć · Algorytmy i struktury danych20 haseł