Drzewce
03.10.2010 - Michał Karpiński
Średnia wysokość drzewcaZł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 . Zapewnienie drzewu binarnemu wysokości dokładnie 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 przemnożone przez jakąś stałą. Musimy udowodnić, że . Losowo zbudowane drzewo binarnePodejdziemy do naszego problemu z innej strony. Wyobraźmy sobie, że budujemy drzewo binarne poprzez wstawienie elementów z posortowanego zbioru kluczy 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 do korzenia. Długość tej ścieżki jest równa ilości przodków -a. Korzystając z liniowości wartości oczekiwanej otrzymujemy, że oczekiwana głębokość węzła jest równa sumie prawdopodobieństw, że jest przodkiem -a, gdzie . Element jest przodkiem -a, jeśli został wstawiony jako pierwszy z elementów z przedziału (lub jeśli < ). W takim razie, prawdopodobieństwo, że jest przodkiem -a w posortowanym ciągu wynosi 1/2: jeśli i 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 , (gdzie jest -tą liczbą harmoniczną) a to jest równe . Czyli głębokość dowolnego węzła w losowo zbudowanym drzewie binarnym wynosi . W szczególności liście drzewa mają taką głębokość. Oznacza to, . Drzewce VS losowo zbudowane drzewa binarneAnaliza, 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 przypiszemy losowy, unikalny priorytet i posortujemy 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 . Złożoność czasowa operacji na drzewcachOto lista procedur, które omawialiśmy do tej pory i ich asymptotyczny czas działania zależny od zmiennej :
(2 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com