Drzewo BST – notatki

Drzewo BST

Struktura danych, w której każdy węzeł ma maksymalnie dwóch potomków: lewego mniejszego i prawego większego.

Węzeł

Podstawowy element drzewa, składający się z wartości oraz wskaźników do lewego i prawego potomka.

Korzeń

Najwyższy węzeł drzewa, z którego wychodzą wszystkie inne węzły.

Głębokość węzła

Odległość od korzenia do danego węzła, mierzona w liczbie krawędzi.

Wysokość drzewa

Najdłuższa ścieżka od korzenia do najniższego liścia.

Liść

Węzeł, który nie ma żadnych potomków.

Balans drzew BST

Stan, w którym głębokość lewego i prawego poddrzewa dla każdego węzła różni się co najwyżej o jeden.

In-order traversal

Metoda przeszukiwania, w której odwiedza się węzły w kolejności: lewe, obecne, prawe.

Pre-order traversal

Metoda przeszukiwania, w której odwiedza się węzły w kolejności: obecne, lewe, prawe.

Post-order traversal

Metoda przeszukiwania, w której odwiedza się węzły w kolejności: lewe, prawe, obecne.

Wstawianie do BST

Polega na dodaniu nowego węzła w odpowiednim miejscu, zachowując zasady BST.

Usuwanie węzła

Proces, w którym węzeł jest usuwany, a struktura drzewna jest odpowiednio reorganizowana.

Złożoność czasowa operacji

W najlepszym przypadku O(log n), w najgorszym przypadku O(n), gdzie n to liczba węzłów.

Zastosowania drzew BST

Wyszukiwanie, sortowanie, przechowywanie danych w sposób umożliwiający szybki dostęp.

Różnica między BST a drzewem zrównoważonym

BST może nie być zrównoważone, co wpływa na wydajność operacji, podczas gdy drzewo zrównoważone utrzymuje równą głębokość.

Wyszukiwanie w BST

Zaczyna od korzenia, porównując wartość, przechodząc w lewo lub prawo na podstawie porównania.

Fałsz czy prawda: BST zawsze jest zrównoważone

Fałsz, ponieważ nie ma wymogu równowagi w tradycyjnych drzewach BST.

Jakie są metody przeszukiwania?

In-order, pre-order, post-order oraz level-order.

Uzupełnij zdanie: W BST, każdy węzeł ma ___ potomków.

maksymalnie dwóch potomków.

Co to jest AVL?

Typ drzewa binarnego, które jest zrównoważone, co oznacza, że różnica wysokości poddrzew nie przekracza 1.

Zastosowanie BST w bazach danych

Umożliwia szybkie wyszukiwanie i sortowanie danych, co jest kluczowe dla wydajnych operacji.

Jakie są zalety drzew BST?

Szybkie wyszukiwanie, dodawanie i usuwanie danych w średnim przypadku O(log n).

Kiedy BST może stać się nieefektywne?

Gdy dane są dodawane w uporządkowanej kolejności, co prowadzi do degeneracji drzewa.

Co to jest drzewo czerwono-czarne?

Typ zrównoważonego drzewa binarnego, które przestrzega określonych zasad kolorowania węzłów.

Jakie operacje można wykonywać na BST?

Wstawianie, usuwanie, wyszukiwanie, przeszukiwanie oraz przechodzenie przez drzewo.

Złożoność czasowa usuwania węzła

Złożoność czasowa wynosi O(h), gdzie h to wysokość drzewa.

Fałsz czy prawda: BST zapewnia zawsze O(1) czas dostępu.

Fałsz, ponieważ czas dostępu zależy od struktury drzewa.

Rola balansu w BST

Utrzymanie równowagi zapewnia optymalne czasy operacji, unikając degeneracji do listy.