Ma 17 stron. Porusza takie zagadnienia jak: wyszukiwanie w tablicy posortowanej, wyszukiwanie interpolacyjne, modyfikacja operacji usuwania, drzewa AVL, algorytm operacji wstawiania dla drzew AVL.
Algorytmy i struktury danych I Wyszukiwanie 1
Wyszukiwanie w tablicy posortowanej
Wyszukiwanie binarne w tablicy a[1..n] uporządkowanej niemalejąco.
wersja z jednym porównaniem w każdej iteracji
{ α : n >= 1
a[1] <= a[2] <= ... <= a[n] }
L 1
R n
while (L < R) do
{ γ : n >= 1
a[1] <= a[2] <= ... <= a[n] }
1 <= L <= R <= n
x ∈ a[1..n] wtw x ∈ a[L..R] }
M (L + R) DIV 2 // L<=M<R
if x <= a[M] then
R M
else L M+1
{ β : x jest w a[1..n] wtw x = a[L] }
Ciekawa własność algorytmu "1 porównanie":
W przypadku istnienia kluczy powtarzających się znajduje skrajnie prawe wystąpienie klucza.
Złożoność - liczba porównań:
- pesymistyczna log n + O(1)
- średnio: identyczna jak w przypadku pesymistycznym
Można wykazać, że każdy algorytm wyszukujący metodą porównań w tablicy posortowanej ma pesymistyczną złożoność Ω(log n). Zatem wyszukiwanie połówkowe jest optymalne w przypadku pesymistycznym.
Wyszukiwanie interpolacyjne wersja "1 porównanie"
Metoda doskonała w przypadku średnim.
Intuicyjnie: jeśli szukany X ma wartość bliską wartości na końcu tablicy, to lepiej sprawdzać adres blisko tego końca. Formalnie: stosujemy interpolację liniową - obliczamy nowe miejsce tak, aby różnica indeksów nowego miejsca i skrajnie lewego elementu była proporcjonalna do różnicy wartości elementu szukanego i skrajnie lewego elementu.
zamieniamy wiersz
M (L + R) DIV 2 przez ciąg instrukcji
M = L + (X-a[L])*(R-L) / (a[R] - a[L])
if M = R then M--
else if M = L then M++
a dodatkowo zakładamy, że n>2 oraz a[1] <= x < a[n] (np. za pomocą wartowników).
Złożoność (liczba porównań):
pesymistyczna: n + O(1)
średnia, przy założeniu że elementy słownika S wybrane z równomiernym rozkładem prawdopodobieństwa w przedziale otwartym (c, d): nie więcej niż lg lg n + c, c ≈ 0.7
np. dla n=106 oczekiwana liczba porównań ≈ 5
Drzewa BST (binary search tree)
drzewa poszukiwań binarnych
jako realizacja słownika:
search(x)
insert(x)
delete(x)
Drzewo BST to drzewo binarne, w którym dla dowolnych węzłów x, y zachodzi:
jeśli x jest w lewym poddrzewie o korzeniu y, to x<y
jeśli x jest w prawym poddrzewie o korzeniu y, to x>y
Istotną rolę odgrywa porządek przeglądu drzewa binarnego inorder:
(…)
… twierdzenie:
Twierdzenie:
Jeśli drzewo BST jest puste i wykonujemy wstawienie n różnych elementów w losowej kolejności, to oczekiwana wysokość drzewa wynosi Θ(lg n).
Fakty: Operacje delete wykonane po ciągu operacji insert zachowują losowość drzewa BST (w sensie losowej permutacji wstawianych elementów)
Operacje insert wykonane po operacjach delete powodują że drzewo BST przestaje być losowe, empirycznie, średni czas operacji wzrasta do n1/2.
(empiryczny) Jeśli w operacji delete w przypadku 2.3 losujemy czy przepisywać następny element s czy poprzedni, to oczekiwana długość ścieżki dostępu jest logarytmiczna.
Modyfikacja operacji usuwania:
lazy-delete(x):
1. wyszukaj węzeł p zawierający klucz x
2. oznakuj węzeł p jako usunięty, ale nie usuwaj go z drzewa
Wniosek:
Jeśli słownik realizowany jest za pomocą…
... zobacz całą notatkę
Komentarze użytkowników (0)