 |
Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: poprawić usuwanie (styl, może dodać ilustracje). Po wyeliminowaniu wskazanych powyżej niedoskonałości prosimy usunąć szablon {{Dopracować}} z kodu tego artykułu. |
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 nie mniejsza niż wartości wszystkich kluczy z lewego poddrzewa, a nie większa niż wartości wszystkich kluczy z prawego poddrzewa (relacja może być odwrócona, to kwestia umowy). Relacje niemniejszości i niewiększości można zamienić odpowiednio na relacje większości i mniejszości, ale ograniczamy się wówczas do przypadku unikalności kluczy (wykluczamy klucze, które mogą się powtarzać). Przechodząc drzewo metodą inorder, uzyskuje się ciąg wartości posortowanych niemalejąco (lub rosnąco w przypadku unikatowych kluczy).
Pesymistyczny koszt każdej z operacji na drzewie BST (o liczbie węzłów n), tj. wyszukiwania, dodania lub usunięcia klucza, zależy od wysokości drzewa i wynosi
- log2n – dla drzewa zrównoważonego – najlepszy przypadek;
- n – dla drzewa zdegenerowanego 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.
Spis treści |
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:
- Jeśli węzeł = nil (puste poddrzewo) – w drzewie nie ma klucza k, przejdź do 5
- Jeśli kluczwęzeł = k – znaleziono węzeł o podanej wartości klucza, przejdź do 5
- Jeśli kluczwęzeł < k – klucz, o ile istnieje w drzewie, zlokalizowany jest w prawym poddrzewie węzła:
- węzeł := prawy_synwęzeł
- przejdź do 1
- Jeśli kluczwęzeł > k – klucz, o ile istnieje w drzewie, zlokalizowany jest w lewym poddrzewie węzła:
- węzeł := lewy_synwęzeł
- przejdź do 1
- Koniec wyszukiwania
Wyszukiwanie klucza w drzewie poszukiwań binarnych można też zaimplementować za pomocą rekurencji:
Szukaj(węzeł):
- Jeśli węzeł = nil (puste poddrzewo) – w drzewie nie ma klucza k: return false;
- Jeśli kluczwęzeł = k – znaleziono węzeł o podanej wartości klucza: return true;
- Jeśli kluczwęzeł < k – klucz, o ile istnieje w drzewie, zlokalizowany jest w prawym poddrzewie węzła:
- return Szukaj(prawy_synwęzeł);
- Jeśli kluczwęzeł > k – klucz, o ile istnieje w drzewie, zlokalizowany jest w lewym poddrzewie węzła:
- return Szukaj(lewy_synwęzeł);
edytuj Wyszukiwanie klucza o minimalnej wartości
- x := korzeń drzewa
- Dopóki x ma lewy następnik:
- x := lewy_synx
Po zakończeniu procedury x jest węzłem z kluczem o najmniejszej wartości.
edytuj Wyszukiwanie klucza o maksymalnej wartości
- x := korzeń drzewa
- Dopóki x ma prawy następnik:
- x := prawy_synx
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_synwęzeł = nil lub prawy_synwę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:
- Jeśli x jest liściem (nie ma synów) – po prostu usunąć
- Jeśli x ma tylko jednego syna – zastąpić go synem
- Jeśli x ma dwóch synów:
- Należy znaleźć jego następnik y (najbardziej lewy element w prawym poddrzewie x)
- zamiast następnika można też użyć poprzednika (czyli najbardziej prawy element w lewym poddrzewie x). Ponieważ nie ma większego znaczenia, którego z nich użyjemy, można zastosować metodę naprzemienną, albo nawet losową. Logiczne jest również używanie zawsze poprzednika lub zawsze następnika.
- 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 - prawego - syna (ewentualny syn y stanie się synem swojego dziadka)
- Należy znaleźć jego następnik y (najbardziej lewy element w prawym poddrzewie x)
edytuj Implementacja
Przykładowy program w języku Pascal. Buduje drzewo BST i je przekształca w drzewo wyważone.
program BST; uses crt; type wsk = ^wezel; wezel = record d : integer; l : wsk; r : wsk; end; var n,i,x : integer; p : wsk; poz : byte; procedure Wstaw(var p : wsk; x : integer); begin if p = nil then begin new(p); p^.d := x; p^.l := nil; p^.r := nil; end else if x<p^.d then Wstaw(p^.l,x) else Wstaw(p^.r,x); end; function Licz(p : wsk) : integer; var k : integer; begin if p <> nil then begin k := 1; if p^.l <> nil then k := k+Licz(p^.l); if p^.r <> nil then k := k+Licz(p^.r); Licz := k; end else Licz := 0; end; procedure Pokaz(p : wsk); begin writeln(p^.d); if p^.l <> nil then Pokaz(p^.l); if p^.r <> nil then Pokaz(p^.r); end; procedure Wywaz(var p : wsk; b : integer); var a : integer; q, w : wsk; begin b := b-1; a := Licz(p^.l); b := b-a; while abs(a-b) > 1 do begin if a > b then begin if p^.l^.r <> nil then begin q := p^.l; repeat w := q; q := q^.r; until q^.r = nil; q^.r := p; q^.l := p^.l; w^.r := nil; p^.l := nil; p := q; end else begin p^.l^.r := p; q := p^.l; p^.l := nil; p := q; end; a := a-1; b := b+1; end else begin if p^.r^.l <> nil then begin q := p^.r; repeat w := q; q := q^.l; until q^.l=nil; q^.l := p; q^.r := p^.r; w^.l := nil; p^.r := nil; p := q; end else begin p^.r^.l := p; q := p^.r; p^.r := nil; p := q; end; a := a+1; b := b-1; end; end; if p^.l <> nil then Wywaz(p^.l,a); if p^.r <> nil then Wywaz(p^.r,b); end; begin p := nil; clrscr; writeln; write('Ile elementow? '); readln(n); for i := 1 to n do begin write('Element numer ',i,': '); readln(x); Wstaw(p,x); end; writeln; writeln('Nie wywazone:'); Pokaz(p); n := Licz(p); writeln('Elementow jest ',n); Wywaz(p,n); writeln; writeln('Wywazone:'); Pokaz(p); readln; end.
edytuj Zobacz też