Drzewo BST
Drzewo BST to interaktywny eksperyment z aplikacji Struktury danych – darmowej symulacji ze StudyFi Lab, która działa bezpośrednio w przeglądarce.
W każdym węźle mniejsze wartości są po lewej, a większe po prawej. Dlatego wyszukiwanie i wstawianie idą jedną ścieżką od korzenia i trwają O(h), gdzie h to wysokość drzewa — w drzewie zrównoważonym h ≈ log₂ n. Usuwanie ma trzy przypadki: liść po prostu znika, węzeł z jednym dzieckiem zastępuje to dziecko, a węzeł z dwojgiem dzieci przejmuje wartość następnika w porządku in-order. Przejście in-order wypisuje wartości posortowane; podobne drzewa napędzają indeksy baz danych.
Spróbuj: Usuń korzeń — ma dwoje dzieci, więc zobaczysz szukanie następnika. Potem spróbuj „Wstaw posortowane wartości”: drzewo zamienia się w listę, a wysokość rośnie do n.
Najczęstsze pytania
Co pokazuje eksperyment „Drzewo BST”?
W każdym węźle mniejsze wartości są po lewej, a większe po prawej. Dlatego wyszukiwanie i wstawianie idą jedną ścieżką od korzenia i trwają O(h), gdzie h to wysokość drzewa — w drzewie zrównoważonym h ≈ log₂ n. Usuwanie ma trzy przypadki: liść po prostu znika, węzeł z jednym dzieckiem zastępuje to dziecko, a węzeł z dwojgiem dzieci przejmuje wartość następnika w porządku in-order. Przejście in-order wypisuje wartości posortowane; podobne drzewa napędzają indeksy baz danych.
Jak wypróbować „Drzewo BST”?
Usuń korzeń — ma dwoje dzieci, więc zobaczysz szukanie następnika. Potem spróbuj „Wstaw posortowane wartości”: drzewo zamienia się w listę, a wysokość rośnie do n.
Uczysz się do sprawdzianu?
Wgraj swoje notatki, a StudyFi zrobi z nich fiszki, testy i podcasty.