Drzewce

03.10.2010 - Michał Karpiński
TrudnośćTrudnośćTrudność

Średnia wysokość drzewca

Złożoność czasowa wszystkich metod poznanych do tej pory jest zależna od wysokości drzewca. Jak było wspomniane na początku: do efektywnego operowania na dowolnych drzewach binarnych potrzebne jest zapewnienie, że drzewo będzie miało wysokość bliską wartości optymalnej. Dla drzew binarnych taką wartością jest $ log_2 n $.

Zapewnienie drzewu binarnemu wysokości dokładnie $ log_2 n $ jest kosztowne. W przypadku drzewców jest to niemożliwe, z uwagi na losowość. Co prawda może się zdarzyć, że powstały drzewiec, będzie pełnym drzewem binarnym, ale taka sytuacja jest małoprawdopobobna (zwłaszcza dla drzewców o dużych rozmiarach).

Dla naszych potrzeb wystaczy, że istnieje duże prawdopodobieństwo, że wysokość drzewca wynosi $ log_2 n $ przemnożone przez jakąś stałą. Musimy udowodnić, że $ h=O(log_2 n) $.

Losowo zbudowane drzewo binarne

Podejdziemy do naszego problemu z innej strony. Wyobraźmy sobie, że budujemy drzewo binarne poprzez wstawienie $ n $ elementów z posortowanego zbioru kluczy $ K = \{k_1,k_2,k_3 \cdots k_n\} $ w losowej kolejności do początkowo pustego drzewa. Załóżmy, że uzyskanie każdej permutacji tego zbioru jest tak samo prawdopodobne. Drzewo, które otrzymaliśmy nazywamy losowo zbudowanym drzewem binarnym.

Zbadajmy oczekiwaną długość ścieżki od dowolnie wybranego węzła $ x $ do korzenia. Długość tej ścieżki jest równa ilości przodków $ x $-a. Korzystając z liniowości wartości oczekiwanej otrzymujemy, że oczekiwana głębokość węzła $ x $ jest równa sumie prawdopodobieństw, że $ y $ jest przodkiem $ x $-a, gdzie $ y \in K/\{x\} $.

Element $ y $ jest przodkiem $ x $-a, jeśli $ y $ został wstawiony jako pierwszy z elementów z przedziału $ \langle x,y\rangle $ (lub $ \langle y,x\rangle $ jeśli $ y $ < $ x $). W takim razie, prawdopodobieństwo, że $ y $ jest przodkiem $ x $-a w posortowanym ciągu $ K $ wynosi 1/2: jeśli $ x $ i $ y $ stoją obok siebie, 1/3: jeśli są oddalone od siebie o jeden, 1/4: jeśli są oddalone o dwa itd.

Sumę tych prawdopodobieństw można oszacować przez $ 2H_n $, (gdzie $ H_n $ jest $ n $-tą liczbą harmoniczną) a to jest równe $ 2 \ln n + O(1) $. Czyli głębokość dowolnego węzła w losowo zbudowanym drzewie binarnym wynosi $ O(log_2 n) $. W szczególności liście drzewa mają taką głębokość. Oznacza to, $ h=O(log_2 n) $.

Drzewce VS losowo zbudowane drzewa binarne

Analiza, którą przed chwilą dokonaliśmy przyda się przy badaniu wysokości drzewca. Tak na prawdę posiadamy już wszystkie narzędzia potrzebne do rozwiązania naszego problemu.

Trzeba tylko zauważyć, że można zdefiniować drzewiec w nieco inny sposób niż my to zrobiliśmy. Jeśli dla każdego klucza z podanej listy $ K $ przypiszemy losowy, unikalny priorytet i posortujemy $ K $ malejąco według priorytetów, a następnie zbudujemy drzewiec wstawiając kolejno klucze do drzewca pustego zaczynając od klucza o najwyższym priorytecie, to kształt drzewca ma taki sam rozkład prawdopodobieństwa jak losowo zbudowane drzewo binarne.

Z tego wniosek, że wysokość drzewca wynosi $ O(\log_2 n) $.

Złożoność czasowa operacji na drzewcach

Oto lista procedur, które omawialiśmy do tej pory i ich asymptotyczny czas działania zależny od zmiennej $ n=|T_1| $:

  • $ SEARCH{-}TREAP $: $ O(\log_2 n) $

  • $ INSERT{-}TREAP $: $ O(\log_2 n) $

  • $ DELETE{-}TREAP $: $ O(\log_2 n) $

  • $ SPLIT{-}TREAP $: $ O(\log_2 n) $

  • $ MERGE{-}TREAP $: $ O(\log_2 n) $ (w najlepszym przypadku) lub $ O(m\log_2 n) $ ($ m=|T_2| \le n $)

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com