Drzewa i sterty

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

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

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

Drzewo binarne z porządkiem: klucze w lewym poddrzewie ≤ klucz węzła ≤ klucze w prawym poddrzewie, co umożliwia wyszukiwanie.

Samobalansujące się drzewo wyszukiwań, w którym wysokości poddrzew każdego węzła różnią się o co najwyżej 1.

Samobalansujące się drzewo wyszukiwań z kolorowaniem węzłów, w którym niezmienniki kolorów gwarantują logarytmiczną wysokość.

Drzewo wyszukiwań utrzymujące wysokość rzędu logarytmu liczby węzłów, co gwarantuje logarytmiczny koszt operacji.

Węzeł drzewa nieposiadający dzieci, kończący ścieżkę od korzenia.

Fragment drzewa złożony z wybranego węzła i wszystkich jego potomków, sam będący drzewem ukorzenionym.

Drzewo binarne, w którym każdy węzeł ma zero lub dwoje dzieci, a wszystkie liście są na tym samym poziomie.

Drzewo binarne, którego wszystkie poziomy poza ostatnim są pełne, a liście ostatniego poziomu wypełniają je od lewej.

Systematyczne odwiedzanie każdego węzła drzewa, w porządku in-order, pre-order, post-order lub wszerz.

Lokalna operacja restrukturyzująca drzewo wyszukiwań, zmieniająca układ trzech węzłów z zachowaniem porządku, używana do balansowania.

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

Liczba krawędzi na ścieżce od korzenia do danego węzła; korzeń ma głębokość zero.

Długość najdłuższej ścieżki od korzenia do liścia, mierzona liczbą krawędzi; determinuje koszt operacji.

Niemal pełne drzewo binarne spełniające własność kopca, zwykle reprezentowane w tablicy, używane do implementacji kolejki priorytetowej.

Niezmiennik porządkujący: klucz każdego węzła jest nie mniejszy (kopiec max) lub nie większy (kopiec min) od kluczy jego dzieci.

Sterta zbudowana z kolekcji drzew dwumianowych, wspierająca efektywne łączenie dwóch stert.

Sterta złączalna o zamortyzowanym stałym koszcie wstawiania i zmniejszania klucza, zbudowana z lasu drzew o luźnej strukturze.