Kopiec (binarny) to tablicowa struktura danych, którą można traktować jako drzewo binarne, pełne na wszystkich poziomach z wyjątkiem być może najniższego, który jest wypełniony od lewej strony do pewnego miejsca.

Kopiec n-elementowy ma wysokosc

Dowód: Niech h będzie wysokością kopca. Ponieważ pełne drzewo binarne o wysokości h zawiera
elementów, więc
, stąd
, czyli
.

HEAPIFY

Poddrzewo, na którym wywołujemy HEAPIFY rekurencyjnie, ma wysokość
, stąd

Łatwo wykazać przez indukcję, że
, czyli
.

Stąd otrzymujemy, że HEAPIFY działa na drzewie rozmiaru k w pesymistycznym czasie
.

BUILD-HEAP

Ustalmy dowolny węzeł x kopca rozmiaru n i niech d oznacza jego głębokość, a h wysokość, to znaczy wysokość poddrzewa o korzeniu x. Wtedy d + h jest wysokością całego kopca, czyli
.

Dowolne drzewo binarne ma co najwyżej
węzłów o głębokości d, a zatem n-elementowy kopiec ma co najwyżej
węzłów o głębokości h.

Czas działania procedury HEAPIFY wywołanej w węźle o wysokości h wznosi O(h), a zatem pesymistyczny czas działania BUILD-HEAP dla tablicy n-elementowej szacuje się przez

.

Zauważmy, że szereg
jest zbieżny. Oznaczając przez s jego sumę otrzymujemy, że dla dowolnego n zachodzi
, czyli
.

HEAPSORT

Pesymistyczny czas działania algorytmu heapsort na tablicy n-elementowej wynosi
, ponieważ budowa kopca przez BUILD-HEAP zajmuje czas O(n), a każde z n-1 wywołań HEAPIFY zajmuje czas
,
.

Quicksort

Przypadek pesymistyczny

Przypadek optymistyczny

Związek formuły rekurencyjnej z algorytmem

przez wstawianie
przez scalanie
przez kopcowanie
quicksort

Dowolny algorytm sortujący n elementów za pomocą porównań w przypadku pesymistycznym wymaga
porównań.

Sortowanie przez zliczanie

Sortowanie pozycyjne

Sortowanie kubełkowe
- dla danych wejściowych rozmiaru n

Kolejka priorytetowa to struktura danych reprezentująca zbiór dynamiczny S, którego każdy element ma przyporządkowana wartość, zwana kluczem =
.

Typowe operacje na stosach, kolejkach i listach:

Implementacja w postaci kopca umożliwia wykonanie wszystkich operacji kolejki priorytetowej na zbiorze n-elementowym w czasie
.

Operacja INSERT i DELETE =

Operacja SEARCH - czas potrzebny na wyszukanie elementu o kluczu k zależy liniowo od długości listy.

Haszowanie

Średni czas wszystkich operacji słownikowych na tablicy z haszowaniem za pomocą łańcuchowej metody rozwiązywania kolizji wynosi
.

Haszowanie modularne

Haszowanie przez mnożenie

Adresowanie otwarte

Wszystkie elementy są przechowywane wprost w tablicy.

Jeśli
, to oczekiwana liczba sprawdzonych pozycji w czasie wyszukiwania elementu, którego nie ma w tablicy, jest nie większa niż
.

Wstawianie elementu wymaga średnio co najwyżej
sprawdzeń pozycji w tablicy.

Adresowanie liniowe - funkcja

Wada - grupowanie się zajętych pozycji. Grupy zajętych pozycji pojawiają się, ponieważ pusta pozycja poprzedzona przez i zajętych pozycji jest następnie zapełniana z prawdopodobieństwem (1+i)/m. Spójne ciągi zajętych pozycji powiększają się, co powoduje wzrost średniego czasu wyszukiwania.

Adresowanie kwadratowe - funkcja

muszą być dobrane tak, żeby ciąg kontrolny każdego klucza był permutacją ciągu <0,1,…,m-1>.

Haszowanie dwukrotne - funkcja

BST jest to drzewo binarne, w którym spełniona jest własność:

- jeśli y jest węzłem znajdującym się w lewym poddrzewie węzła x, to

- jeśli y jest węzłem znajdującym się w prawym poddrzewie węzła x, to

INORDER -WALK - gwarantuje wypisanie kluczy w kolejności niemalejącej =

SEACH, MINIMUM, MAXIMUM, TREE-SUCCESSOR, PREDECESSOR, INSERT, DELETE =

Wysokość h drzewa binarnego o n węzłach spełnia nierówności:
.

Oszacowanie dolne jest osiągnięte przez drzewo prawie pełne, a oszacowanie górne przez drzewo składające się z pojedynczej ścieżki od korzenia do jedynego liścia.

Drzewo czerwono-czarne jest drzewem wyszukiwań binarnych, w którym każdy węzeł posiada dodatkowy atrybut: kolor, który może być albo czerwony, albo czarny.

- każdy węzeł jest albo czerwony, albo czarny

- korzeń jest czarny

- każdy liść jest czarny

- jeśli węzeł jest czerwony, to obaj jego synowie są czarni

- każda ścieżka z ustalonego węzła do liścia ma tyle samo czarnych węzłów

Własności zakłócone przy INSERT:

- korzeń jest czarny

- jeśli węzeł jest czerwony, to obaj jego synowie są czarni

węzłów wewnętrznych

wysokość drzewa o n węzłach wewnętrznych

operacje na drzewach przy zachowaniu właściwości

ROTATE =
ponieważ każdy wiersz jest wykonywany co najwyżej raz.

Sposoby organizacji efektywnych algorytmów

Dziel i zwyciężaj - sortowanie przez scalanie, quicksort, sortowanie kubełkowe

Strategia zachłanna - kody Huffmana

Programowanie dynamiczne - NWP,

Kody prefiksowe to takie kody, w których słowo kodowe żadnego znaku nie jest prefiksem słowa kodowego innego znaku.

Drzewo binarne:

- liście drzewa odpowiadają zakodowanym znakom;

- słowo kodowe dla znaku odpowiada ścieżce od korzenia do tego znaku;

- 0 oznacza „przejście do lewego syna”, a 1 „przejście do prawego syna”.

Koszt:

Niech C oznacza zbiór wszystkich znaków (alfabet).

Mając dane drzewo T odpowiadające kodowi, łatwo jest obliczyć liczbę bitów potrzebnych do zakodowania pliku.

Dla każdego
niech f(c) oznacza liczbę wystąpień (częstość) c w pliku, a
głębokość liścia c w drzewie.

Zauważmy, że
jest również długością słowa kodowego dla c.

Liczba bitów potrzebnych do zakodowania pliku jest równa

Liczbę tę nazywamy kosztem drzewa T.

Kod prefiksowy jest optymalny, jeżeli jego koszt jest minimalny dla danego alfabetu.

Drzewo binarne nazywamy regularnym, jeżeli każdy węzeł wewnętrzny ma dwóch synów.

Drzewo binarne reprezentujące optymalny kod prefiksowy jest regularne, o ile ma przynajmniej dwa liście.

B-drzewo T jest drzewem ukorzenionym o następujących własnościach:

• każdy węzeł x ma następujące pola:

• n[x] - liczba kluczy aktualnie pamiętanych w węźle x;

• n[x] kluczy pamiętanych w porządku niemalejącym

• leaf[x] - pole logiczne, którego wartością jest TRUE, jeśli x jest liściem, lub FALSE, jeśli x jest węzłem wewnętrznym

• każdy węzeł wewnętrzny x zawiera także n[x]+1 wskaźników do swoich synów. Liście nie mają synów, więc ich pola
  nie są zdefiniowane.

• klucze
  rozdzielają przedziały kluczy pamiętanych w poddrzewach: jeśli
  jest dowolnym kluczem z poddrzewa o korzeniu
  , to

• wszystkie liście leżą na tej samej głębokości równej wysokości drzewa

• istnieją dolne i górne ograniczenia na liczbę kluczy w danym węźle. Ograniczenia te są określone za pomocą ustalonej liczby całkowitej
  nazywanej minimalnym stopniem B-drzewa:

• każdy węzeł różny od korzenia musi mieć co najmniej t-1 kluczy. Każdy węzeł wewnętrzny różny od korzenia ma zatem co najmniej t synów. Jeśli drzewo jest niepuste, to korzeń musi mieć co najmniej jeden klucz.

• każdy węzeł może zawierać co najwyżej 2t-1 kluczy. Dlatego każdy węzeł wewnętrzny może mieć co najwyżej 2t synów. Mówimy, że węzeł jest pełny jeżeli zawiera dokładnie 2t-1 kluczy

Dla każdego B-drzewa o
kluczach, wysokości h i minimalnym stopniu
mamy

Korzeń zawiera co najmniej jeden klucz, a wszystkie pozostałe węzły zawierają co najmniej po t-1 kluczy.

Mamy więc co najmniej 2 węzły na głębokości 1, co najmniej 2t węzłów na głębokości 2, co najmniej
węzłów na głębokości 3 itd.

Liczba dostępów do dysku w SEARCH =
, gdzie h jest wysokością B-drzewa, a n liczbą zapisanych w nim kluczy.

SEARCH =

SPLIT-CHILD = czas działania =
, ilość odwołań do dysku =

INSERT =czas działania =
, ilość odwołań do dysku =

DELETE =
, ilość odwołań do dysku =

Uzasadnienie rozbicia: Rozbicia dokonuje się względem środkowego klucza
, który jest przesuwany do ojca y. Schodząc w dół drzewa podczas szukania miejsca dla nowego klucza rozbijamy wszystkie napotkane po drodze pełne węzły. Tak więc za każdym razem kiedy rozbijamy pełny węzeł, mamy gwarancję, że jego ojciec nie jest pełny.

Analiza kosztu zamortyzowanego metodą potencjału (s 411 - print)

Na początku mamy strukturę danych
, na której chcemy wykonać n operacji. Dla każdego i=1, 2,…,n niech
oznacza faktyczny koszt i-tej operacji, a
niech będzie strukturą danych powstałą ze struktury
po wykonaniu i-tej operacji. Funkcja potencjału przyporządkowuje każdej strukturze
liczbę rzeczywistą
, nazywaną potencjałem struktury
. Koszt zamortyzowany
dla i-tej operacji względem funkcji potencjału
definiuje się jako

Kopce dwumianowe (s 454 - print)

Rodziny zbiorów rozłącznych

MAKE-SET

UNION = liczba operacji =

FIND-SET

n - liczba operacji MAKE-SET

m - łączna liczba operacji MAKE-SET, UNION i FIND-SET

Reprezentacja listowa:

MAKE-SET, FIND-SET = czas =

UNION =
, łączna liczba obiektów uaktualnionych

MAKE-SET =

Całkowity czas wykonania ciągu operacji wynosi
, czyli
, ponieważ
, a
. Średnio na każdą operację przypada więc czas
. Oznacza to, że zamortyzowany czas operacji wynosi
.

Heurystyka łączenia z wyważeniem

Dla dowolnego
po uaktualnieniu wskaźnika od x do reprezentanta
razy otrzymany zbiór liczy przynajmniej k elementów. Ponieważ największy zbiór zawiera co najmniej n elementów, wskaźnik do reprezentanta każdego obiektu był uaktualniany co najwyżej
razy we wszystkich operacjach UNION. Łączny czas uaktualniania n obiektów wynosi zatem
.

Każda operacja MAKE-SET i FIND-SET zajmuje czas
, co w sumie daje
. Łączny czas wykonania całego ciągu operacji wynosi zatem

---