Drzewa BST, AVL i kopiec minimalny — jak przechowywac dane, aby wyszukiwanie, wstawianie i usuwanie bylo szybkie? Zbadaj to interaktywnie z wizualizacja krok po kroku.
Drzewo binarne z wlasciwoscia: lewe poddrzewo < wezel < prawe poddrzewo. Wyszukiwanie, wstawianie i usuwanie w O(h).
Samobalansujace BST — roznica wysokosci poddrzew kazdego wezla wynosi co najwyzej 1. Gwarantuje O(log n).
Drzewo binarne pelne z wlasciwoscia kopca: rodzic <= dzieci. Reprezentacja tablicowa, ekstrakcja minimum w O(log n).
Drzewo BST (Binary Search Tree) to struktura danych, w ktorej kazdy wezel ma co najwyzej dwoch potomkow, a wartosc lewego potomka jest mniejsza od rodzica, a prawego — wieksza. Dzieki temu wyszukiwanie dziala podobnie do wyszukiwania binarnego: w kazdym kroku odrzucamy polowe drzewa.
Problem pojawia sie, gdy dane sa wstawiane w kolejnosci posortowanej — drzewo degeneruje sie do listy jednokierunkowej i operacje staja sie liniowe O(n) zamiast O(log n). Dlatego stosuje sie drzewa samobalansujace jak AVL, ktore po kazdym wstawieniu i usunieciu wykonuja rotacje, aby utrzymac roznice wysokosci poddrzew w granicach 1.
Algorytm DSW (Day-Stout-Warren) pozwala zbalansowac dowolne BST w czasie O(n) — najpierw prostuje drzewo do listy (vine), a nastepnie wykonuje serie rotacji tworzac drzewo idealne zbalansowane.
Kopiec minimalny (Min-Heap) to pelne drzewo binarne, w ktorym wartosc kazdego wezla jest mniejsza lub rowna wartosciom jego dzieci. Minimum zawsze znajduje sie w korzeniu — dostep do niego to O(1).
Kopiec przechowujemy w tablicy jednowymiarowej: korzen pod indeksem 0, dzieci wezla i pod indeksami 2i+1 (lewe) i 2i+2 (prawe), rodzic pod indeksem (i-1)/2. Ta reprezentacja eliminuje potrzebe wskaznikow i zapewnia doskonala lojalnosc cache.
Wstawianie i usuwanie z kopca dzialaja w O(log n) dzieki operacjom sift-up (naprawianie w gore po wstawieniu) i sift-down (naprawianie w dol po ekstrakcji korzenia).
| Operacja | BST (worst) | AVL | Min-Heap |
|---|---|---|---|
| Wstawianie | O(h) | O(log n) | O(log n) |
| Wyszukiwanie | O(h) | O(log n) | O(n) |
| Znajdowanie min | O(h) | O(log n) | O(1) |
| Znajdowanie max | O(h) | O(log n) | O(n/2) |
| Usuwanie | O(h) | O(log n) | O(log n) |
| Balansowanie (DSW) | O(n) | — | — |
h = wysokosc drzewa. Dla BST h moze byc O(n) w najgorszym przypadku, dla AVL zawsze O(log n).
Interaktywna wizualizacja drzew SVG — wstawianie, wyszukiwanie, balansowanie DSW, wyswietlanie poziomow i pre-order.
Pomiary czasu tworzenia, wyszukiwania i balansowania struktur na roznych rozmiarach danych. Wykresy z Recharts.
Pelny raport z tabelami wynikow, 5 wykresami, analiza zalet i wad kazdej struktury oraz eksport do PDF.