Binarne drzewo poszukiwań

Z Wikipedii

Ten artykuł wymaga dopracowania.
Należy w nim poprawić: poprawić usuwanie (styl, może dodać ilustracje), dodać rekurencyjne wyszukiwanie.
Więcej informacji co należy poprawić, być może znajdziesz na odpowiedniej stronie. W pracy nad artykułem należy korzystać z zaleceń edycyjnych. Po naprawieniu wszystkich błędów można usunąć tę wiadomość.
Możesz także przejrzeć pełną listę stron wymagających dopracowania.

Binarne drzewo poszukiwań o wielkości równej 9, a wysokości równej 3; wierzchołek '8' jest tu korzeniem, a wierzchołki '1', '4', '7' i '13', to liście.

Binarne drzewo poszukiwań (skrót BST, z ang. Binary Search Tree) - dynamiczna struktura danych w postaci drzewa binarnego stosowana do szybkiego wyszukiwania. Drzewa BST służą do realizacji bardziej abstrakcyjnych struktur danych, np. zbiorów, czy słowników.

W każdym z węzłów drzewa BST przechowywany jest klucz (klucze są unikatowe). Wartość klucza jest zawsze większa niż wartości wszystkich kluczy z lewego poddrzewa, a mniejsza niż wartości wszystkich kluczy z prawego poddrzewa (relacja może być odwrócona, to kwestia umowy); przechodząc drzewo metodą inorder uzyskuje się ciąg wartości posortowanych rosnąco.

Pesymistyczny koszt każdej z operacji na drzewie BST (o liczbie węzłow n), tj. wyszukiwania, dodania lub usunięcia klucza, zależy od wysokości drzewa i wynosi

• log₂n - dla drzewa zrównoważonego - najlepszy przypadek;
• n - dla drzewa zdegenerowane do listy, tj. takiego, w którym każdy z węzłów oprócz liścia ma tylko jednego syna - najgorszy przypadek.

Dlatego w praktyce często lepiej zastosować drzewa BST o dodatkowych właściwościach, np. AVL lub drzewa czerwono-czarne, które poprzez nakładanie pewnych dodatkowych warunków gwarantują, że drzewo będzie zrównoważone (na tyle, na ile to możliwe), dając tym samym logarytmiczny czas dostępu; dzieje się to kosztem większego skomplikowania procedur wstawiających i usuwających klucze.

[edytuj] Wyszukiwanie klucza

Parametrem wejściowym procedury wyszukującej jest żądana wartość klucza k oraz węzeł - korzeń drzewa. Algorytm iteracyjny przedstawia się następująco:

1. Jeśli klucz[węzeł] = k - znaleziono węzeł o podanej wartości klucza, przejdź do 5
2. Jeśli węzeł = nil (puste poddzewo) - w drzewie nie ma klucza k, przejdź do 5
3. Jeśli klucz[węzeł] < k - klucz, o ile istnieje w drzewie, zlokalizowany jest w lewym poddrzewie węzła:
   • węzeł := prawy_syn[węzeł]
   • przejdź do 1
4. Jeśli klucz[węzeł] > k - klucz, o ile istnieje w drzewie, zlokalizowany jest w prawym poddrzewie węzła:
   • węzeł := lewy_syn[węzeł]
   • przejdź do 1
5. Koniec wyszukiwania

[edytuj] Wyszukiwanie klucza o minimalnej wartości

1. x := korzeń drzewa
2. Dopóki x ma lewy następnik:
   • x := lewy_syn[x]

Po zakończeniu procedury x jest węzłem z kluczem o najmniejszej wartości.

[edytuj] Wyszukiwanie klucza o maksymalnej wartości

1. x := korzeń drzewa
2. Dopóki x ma prawy następnik:
   • x := prawy_syn[x]

Po zakończeniu procedury x jest węzłem z kluczem o największej wartości.

[edytuj] Wstawianie klucza

Algorytm jest bardzo podobny jak przy wyszukiwaniu: jeśli przy przechodzeniu drzewa należy przejść w lewo bądź prawo, a węzeł nie ma lewego bądź prawego syna (tj. lewy_syn[węzeł] = nil lub prawy_syn[węzeł] = nil), to lewym bądź prawym synem węzła staje się nowy węzeł, z kluczem o żądanej wartości. Natomiast jeśli przy przechodzeniu drzewa uda się zlokalizować klucz, to procedura wstawiania nic nie robi.

[edytuj] Usuwanie klucza

Dany jest węzeł x, którego klucz ma żądaną wartość. Przy usuwaniu węzła należy rozważyć trzy przypadki:

1. Jeśli x jest liściem (nie ma synów) - po prostu usunąć
2. Jeśli x ma tylko jednego syna - zastąpić go synem
3. Jeśli x ma dwóch synów:
   • Należy znaleźć jego następnik y (najbardziej lewy element w prawym poddrzewie x)
   • Zastąpić zawartość węzła x przez zawartość węzła y
   • Wyciąć węzeł y o którym wiemy, że może posiadać najwyżej jednego syna (ewentualny syn y stanie się synem swojego dziadka)