PL 
EnglishDomyślny
Українська🌳 Drzewo BST — wstawianie, wyszukiwanie i równoważenie
Animowane operacje na BST: wstawianie, wyszukiwanie, usuwanie i przechodzenie in-order. Przełącz w tryb AVL, by zobaczyć automatyczne rotacje równoważące. Złożoność Big-O i wysokość drzewa na żywo.
O drzewie BST (binarnym drzewie poszukiwań)
Binarne drzewo poszukiwań (BST) to fundamentalna struktura danych w informatyce, w której każdy węzeł przechowuje wartość i ma co najwyżej dwoje dzieci: każda wartość w lewym poddrzewie jest mniejsza od węzła, a każda wartość w prawym poddrzewie jest większa. Ta własność porządkowa oznacza, że wyszukiwanie, wstawianie i usuwanie elementów zajmuje średnio O(log n) czasu — taką samą asymptotyczną wydajność jak wyszukiwanie binarne w posortowanej tablicy, ale z elastycznością dynamicznie łączonej struktury. BST są podstawą indeksów baz danych, tabel symboli w kompilatorach oraz kontenera std::map w C++.
Ten symulator pozwala wstawiać, wyszukiwać i usuwać wartości, przeglądać przejścia inorder/preorder/postorder z animacją krok po kroku oraz stosować balansowanie AVL, by przekształcić zdegenerowane drzewo (przypominające listę wiązaną) w drzewo o zbalansowanej wysokości. Panel statystyk pokazuje liczbę węzłów, wysokość drzewa oraz to, czy drzewo spełnia kryterium balansu AVL (|h_L − h_R| ≤ 1 w każdym węźle).
Najczęściej zadawane pytania
Jaka jest złożoność czasowa wyszukiwania w BST?
W zbalansowanym BST wyszukiwanie zajmuje O(log n) czasu, ponieważ każde porównanie zmniejsza o połowę pozostałych kandydatów, podobnie jak wyszukiwanie binarne. W najgorszym przypadku — gdy wartości są wstawiane w kolejności posortowanej, tworząc łańcuch liniowy — drzewo degeneruje się, a wyszukiwanie spada do O(n). Dlatego wynaleziono samobalansujące warianty, takie jak drzewa AVL i drzewa czerwono-czarne.
Czym jest drzewo AVL i jak działa balansowanie?
Drzewo AVL (nazwane od Adelson-Velsky'ego i Landisa, 1962) to samobalansujące BST utrzymujące niezmiennik, że różnica wysokości między lewym a prawym poddrzewem (współczynnik balansu) wynosi co najwyżej 1 w każdym węźle. Gdy wstawienie lub usunięcie narusza to, rotacja — pojedyncza (lewa lub prawa) lub podwójna (lewo-prawa lub prawo-lewa) — przywraca balans w czasie O(log n) bez zmiany własności porządkowej BST.
Co daje przejście inorder?
Przejście inorder (lewo → korzeń → prawo) odwiedza każdy węzeł w kolejności posortowanej rosnąco. Jest to jedna z najbardziej użytecznych własności BST: pojedyncze przejście O(n) daje posortowaną listę. Dla porównania, preorder (korzeń → lewo → prawo) jest przydatne do serializacji drzewa, a postorder (lewo → prawo → korzeń) jest używane, gdy trzeba przetworzyć dzieci przed rodzicami, na przykład przy usuwaniu całego drzewa.
Czym jest współczynnik balansu i jak jest obliczany?
Współczynnik balansu (bf) węzła definiuje się jako wysokość jego lewego poddrzewa minus wysokość jego prawego poddrzewa. W drzewie AVL bf musi wynosić −1, 0 lub +1 dla każdego węzła. Symulator wyświetla „bf:x” pod każdym węzłem. Węzeł z bf = +2 ma niezbalansowanie w stronę lewą i wymaga rotacji w prawo (lub podwójnej rotacji lewo-prawo, jeśli dziecko jest niezbalansowane w stronę prawą).
Kiedy BST staje się drzewem zdegenerowanym (najgorszy przypadek)?
Jeśli elementy są wstawiane w ściśle rosnącej lub malejącej kolejności — na przykład 1, 2, 3, 4, 5 — BST staje się prawym (lub lewym) łańcuchem o wysokości n−1, identycznym strukturalnie z listą wiązaną. Każde wyszukiwanie wymaga wtedy odwiedzenia wszystkich n węzłów, dając czas O(n). Spróbuj wstawić posortowane wartości w tym symulatorze i porównaj wysokość z losowo uporządkowanym wstawieniem tych samych wartości.
Jak zaimplementowane jest usuwanie w BST?
Usuwanie węzła w BST ma trzy przypadki: (1) węzeł jest liściem — po prostu go usuń; (2) węzeł ma jedno dziecko — wstaw dziecko na jego miejsce; (3) węzeł ma dwoje dzieci — zastąp wartość węzła najmniejszą wartością w jego prawym poddrzewie (następnikiem in-order), a następnie usuń ten węzeł następnika, który gwarantowanie wpada w przypadek 1 lub 2. Ten symulator implementuje wszystkie trzy przypadki.
Jakie są rzeczywiste zastosowania BST?
Systemy zarządzania bazami danych używają B-drzew (uogólnienia BST z wieloma kluczami na węzeł) dla swoich indeksów dyskowych, umożliwiając wyszukiwanie wierszy O(log n) wśród milionów rekordów. Jądro Linuksa używa drzew czerwono-czarnych (kolejnego samobalansującego BST) do planowania zadań i zarządzania obszarami pamięci wirtualnej. std::map i std::set w C++ są zwykle implementowane jako drzewa czerwono-czarne, gwarantując operacje O(log n) w najgorszym przypadku.
Jaka jest różnica między BST a kopcem?
Obie są strukturami drzewiastymi, ale z różnymi własnościami porządkowymi. BST wymusza porządek lewe-dziecko-mniejsze-od-rodzica w całym drzewie, czyniąc wyszukiwanie efektywnym. Kopiec wymusza własność kopca jedynie między rodzicem a jego bezpośrednimi dziećmi (kopiec max: rodzic ≥ dzieci), czyniąc znajdowanie minimum lub maksimum O(1), ale dowolne wyszukiwanie O(n). Kopce są optymalne dla kolejek priorytetowych; BST są optymalne dla posortowanych słowników.
Jak wysokość zbalansowanego BST wiąże się z liczbą węzłów?
Dla idealnie zbalansowanego BST z n węzłami wysokość h = ⌊log₂ n⌋. Drzewo AVL gwarantuje wysokość co najwyżej 1,44 × log₂(n+2), co nadal jest O(log n). Drzewo czerwono-czarne gwarantuje wysokość co najwyżej 2 × log₂(n+1). Te granice sprawiają, że wszystkie operacje są O(log n) nawet przy adwersaryjnej kolejności wstawiania.
Czy BST może przechowywać zduplikowane wartości?
Standardowe definicje BST wykluczają duplikaty, ale rzeczywiste implementacje obsługują je na jeden z trzech sposobów: (1) ignorowanie duplikatów (jak w tym symulatorze); (2) dopuszczenie duplikatów w prawym poddrzewie (wartość ≤ rodzic idzie w prawo); (3) przechowywanie licznika przy każdej wartości węzła. Wybór wpływa na logikę usuwania i semantykę przejść, więc jest zwykle ustalany na etapie projektowania, by dopasować się do wymagań aplikacji.
O tej symulacji
Ta symulacja buduje na żywo w Twojej przeglądarce binarne drzewo poszukiwań, dzięki czemu możesz wstawiać, wyszukiwać i usuwać wartości całkowite oraz obserwować każde porównanie podświetlone krok po kroku. Zwykłe BST bierze swój kształt wyłącznie z kolejności wstawiania, więc może zdegenerować się do wolnego, łańcuchowego drzewa; przycisk Balansuj AVL przepisuje te same wartości w drzewo o zbalansowanej wysokości za pomocą rotacji, dzięki czemu możesz porównać zachowanie wyszukiwania przed i po. Trzy przyciski przejść ujawniają klasyczne kolejności odwiedzania inorder, preorder i postorder, a panel statystyk pokazuje liczbę węzłów, wysokość drzewa oraz to, czy aktualnie spełniony jest warunek balansu AVL.
🔬 Co pokazuje
Każda wstawiona wartość staje się węzłem umieszczonym na lewo lub prawo od swojego rodzica zgodnie z regułą BST: mniejsze wartości idą w lewo, większe w prawo. Wyszukiwanie podświetla ścieżkę porównań na żółto, zmieniając kolor na zielony, gdy wartość zostanie znaleziona, lub na czerwony, gdy jej brak, dzięki czemu widać, ile porównań faktycznie wymaga wyszukanie — średnio O(log n) dla zbalansowanego drzewa, ale O(n) dla mocno przekrzywionego.
🎮 Jak korzystać
Wpisz wartość i naciśnij Wstaw, Szukaj lub Usuń; użyj Losowe 10, by szybko wypełnić drzewo, lub Wyczyść, by zacząć od nowa. Naciśnij Balansuj AVL, by przekształcić bieżące wartości w zbalansowane drzewo za pomocą rotacji, a następnie porównaj podaną wysokość przed i po. Przyciski Inorder, Preorder i Postorder animują każdą kolejność przejścia w polu wyników, a panel statystyk śledzi liczbę węzłów, wysokość, status balansu oraz ostatnią wykonaną operację.
💡 Czy wiesz, że?
Przejście inorder dowolnego binarnego drzewa poszukiwań zawsze odwiedza wartości w ściśle rosnącej kolejności — ta jedna własność sprawia, że BST utrzymują posortowane dane efektywnie przeszukiwalne, wstawialne i usuwalne bez potrzeby oddzielnego kroku sortowania. Praktyczni potomkowie modelowanego tu drzewa AVL, tacy jak drzewa czerwono-czarne, stanowią podstawę std::map w C++ i TreeMap w Javie.
Najczęściej zadawane pytania
Co dokładnie się dzieje, gdy wstawiam wartość?
Symulator porównuje nową wartość z korzeniem: mniejsza idzie w lewo, większa w prawo, powtarzając to rekurencyjnie, aż dotrze do pustego miejsca, gdzie tworzony jest nowy węzeł. Zachowuje to własność porządkową BST — każdy lewy potomek jest mniejszy, a każdy prawy potomek większy od swojego przodka — bez żadnego rebalansowania.
Co przycisk Balansuj AVL robi z drzewem?
Odczytuje wszystkie wartości przejściem inorder, opróżnia drzewo, a następnie wstawia te same wartości ponownie, używając wstawiania w stylu AVL, które stosuje rotacje lewe i prawe, ilekroć wysokości lewego i prawego poddrzewa węzła różnią się o więcej niż jeden. Wartości pozostają niezmienione, ale wynikowy kształt jest zbalansowany wysokościowo, zwykle znacznie zmniejszając wysokość drzewa.
Jaka jest różnica między trzema przyciskami przejść?
Inorder odwiedza lewe poddrzewo, potem węzeł, potem prawe poddrzewo, dając wartości w kolejności posortowanej rosnąco. Preorder odwiedza najpierw węzeł, potem lewo, potem prawo, co jest przydatne do kopiowania lub serializacji drzewa. Postorder odwiedza oba poddrzewa przed samym węzłem — kolejność potrzebna przy bezpiecznym usuwaniu całego drzewa.
Dlaczego wyszukiwanie może zająć O(n) czasu zamiast O(log n)?
Jeśli wartości są wstawiane w już posortowanej kolejności, zwykłe BST rośnie w jednostronny łańcuch niczym niezróżnicowany od listy wiązanej, więc wyszukanie może wymagać sprawdzenia każdego węzła. Spróbuj wstawić liczby w rosnącej kolejności, zanotuj podaną wysokość, a następnie naciśnij Balansuj AVL, by zobaczyć, jak wysokość i najgorszy przypadek kosztu wyszukiwania gwałtownie się zmniejszają.
Co oznacza mała liczba „bf” pod każdym węzłem?
To współczynnik balansu węzła: wysokość jego lewego poddrzewa minus wysokość jego prawego poddrzewa. Drzewo AVL utrzymuje tę wartość na poziomie −1, 0 lub +1 dla każdego węzła; większa wartość bezwzględna sygnalizuje niezbalansowanie, które rotacja musiałaby skorygować.