• Tomasz Żok
• Home
• Publications
• Conferences
• Projects

Kolejka FIFO (First-In-First-Out)

• Kolejka FIFO to struktura danych wspierająca następujące operacje:
  • Dodawanie elementu na koniec kolejki (Enqueue)
  • Pobieranie elementy z początku kolejki (Dequeue)
  • Sprawdzenie czy kolejka jest pusta (IsEmpty)
• Kolejka queue o rozmiarze n to tablica n-elementowa wraz z trzema atrybutami:
  • queue.length: maksymalna pojemność kolejki
  • queue.head: początek kolejki
  • queue.tail: koniec kolejki

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{Enqueue}{$ queue, x $}
    \STATE {$ queue[queue.tail] \gets x $}
    \IF {$ queue.tail = queue.length - 1 $}
        \STATE {$ queue.tail \gets 0 $}
    \ELSE
        \STATE {$ queue.tail \gets queue.tail + 1 $}
    \ENDIF
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Dequeue}{$ queue $}
    \STATE {$ x \gets queue[queue.head] $}
    \IF {$ queue.head = queue.length - 1 $}
        \STATE {$ queue.head \gets 0 $}
    \ELSE
        \STATE {$ queue.head \gets queue.head + 1 $}
    \ENDIF
    \RETURN {$ x $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{IsEmpty}{$ queue $}
    \IF {$ queue.head = queue.tail $}
        \RETURN \TRUE
    \ENDIF
    \RETURN \FALSE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Stos / Kolejka LIFO (Last-In-First-Out)

• Stos (czasem nazywany kolejką LIFO) to struktura danych wspierająca następujące operacje:
  • Dodawanie elementu na wierzch stosu (Push)
  • Pobieranie elementy z wierzchu stosu (Pop)
  • Sprawdzenie czy stos jest pusty (IsEmpty)
• Stos stack o rozmiarze n to tablica n-elementowa wraz z jednym atrybutem:
  • stack.top: indeks pierwszego wolnego miejsca na stosie

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{Push}{$ stack, x $}
    \STATE {$ stack[stack.top] \gets x $}
    \STATE {$ stack.top \gets stack.top + 1 $}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Pop}{$ stack $}
    \STATE {$ stack.top \gets stack.top - 1 $}
    \RETURN {$ stack[stack.top] $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{IsEmpty}{$ stack $}
    \IF {$ stack.top = 0 $}
        \RETURN \TRUE
    \ENDIF
    \RETURN \FALSE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Lista dwukierunkowa

• Lista to struktura danych, w której elementy utrzymywane są w liniowym porządku
• Inaczej niż w przypadku tablic, elementy listy nie adresujemy przez indeksy 1, 2, ...
• Elementy listy dwukierunkowej składają się z:
  • prev: wskaźnika na poprzedni element listy
  • next: wskaźnika na następny element listy
  • key: wartości
• Lista list ma wyróżniony atrybut list.head wskazujący na pierwszy element

Przykład

Wyszukiwanie elementów

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{ListSearch}{$ list, key $}
    \STATE {$ x \gets list.head $}
    \WHILE {$ x \neq $ \textsc{null} \AND $ x.key \neq key $}
        \STATE {$ x \gets x.next $}
    \ENDWHILE
    \RETURN {$ x $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Dodawanie elementów

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{ListInsert}{$ list, key $}
    \STATE {$ node \gets $ new \CALL{ListNode}{$ prev=$ \textsc{null} $, next=list.head, key=key $}}
    \IF {$ list.head \neq $ \textsc{null}}
        \STATE {$ list.head.prev \gets node $}
    \ENDIF
    \STATE {$ list.head \gets node $}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Usuwanie elementów

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{ListDelete}{$ list, node $}
    \IF {$ node.prev \neq $ \textsc{null}}
        \STATE {$ node.prev.next \gets node.next $}
    \ELSE
        \STATE {$ list.head \gets node.next $}
    \ENDIF
    \IF {$ node.next \neq $ \textsc{null}}
        \STATE {$ node.next.prev \gets node.prev $}
    \ENDIF
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Drzewo BST

• Drzewo to struktura danych składająca się z węzłów połączonych w relacji rodzic-potomek
• Drzewo binarne to drzewo, w którym każdy węzeł może mieć co najwyżej dwa węzły potomne
• Węzły w drzewie binarnym przechowują:
  • parent: wskaźnik na rodzica
  • left: wskaźnik na lewy węzeł potomny
  • right: wskaźnik na prawy węzeł potomny
  • key: wartość
• Drzewo tree ma wyróżniony atrybut tree.root wskazujący na korzeń drzewa (jedyny węzeł, dla którego wartość parent to null)
• Drzewo BST (Binary Search Tree) dodatkowo odróżnia lewy i prawy węzeł potomny oraz definiuje, że zachodzić musi zawsze warunek:
  • Wartość w lewym węźle potomnym jest mniejsza niż wartość własna
  • Wartość w prawym węźle potomnym jest większa niż wartość własna
• Wysokością węzła w drzewie nazywamy liczbę krawędzi od tego węzła do korzenia
• Wysokość drzewa h to maksymalna wysokość spośród wszystkich węzłów (drzewo posiadające tylko korzeń ma wysokość 0)

Przykład

Rodzaje drzew binarnych

• Drzewo wyważone to drzewo binarne, w którym dla każdego węzła bezwzględna wartość różnicy wysokości lewego i prawego poddrzewa wynosi co najwyżej 1
  
• Drzewo dokładnie wyważone to drzewo binarne, w którym dla każdego węzła bezwzględna wartość różnicy liczby elementów lewego i prawego poddrzewa wynosi co najwyżej 1
  
• Drzewo AVL (Adelson-Velsky & Landis) to zrównoważone drzewo BST, w którym każdy węzeł przechowuje dodatkowo wartość współczynnika równowagi bf równego różnicy wysokości lewego i prawego poddrzewa
• Drzewo AVL można równoważyć dynamicznie, po dodaniu/usunięciu wartości:
  1. Przejdź przez drzewo metodą BFS
  2. Znajdź pierwszy wierzchołek, dla którego |bf| > 1, a jeżeli takiego nie ma to zakończ działanie
  3. Usuń znaleziony wierzchołek, a jeżeli miał dwa węzły potomne to wybierz element z tego poddrzewa, które ma większą wysokość
  4. Wyznacz ponownie współczynniki bf i wróć do punktu 1

Wyszukiwanie elementów

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{TreeSearch}{$ tree, key $}
    \STATE {$ node \gets tree.root $}
    \WHILE {$ node \neq $ \textsc{null} \AND $ node.key \neq key $}
        \IF {$ key < node.key $}
            \STATE {$ node \gets node.left $}
        \ELSE
            \STATE {$ node \gets node.right $}
        \ENDIF
    \ENDWHILE
    \RETURN {$ node $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Dodawanie elementów

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{TreeInsert}{$ tree, key $}
    \STATE {$ node \gets $ new \CALL{TreeNode}{$ parent = $ \textsc{null} $, left = $ \textsc{null} $, right = $ \textsc{null} $, key= key $}}

    \STATE {}
    \STATE {$ parent \gets $ \textsc{null}}
    \STATE {$ current \gets tree.root $}
    \WHILE {$ current \neq $ \textsc{null} \AND $ current.key \neq key $}
        \STATE {$ parent \gets current $}
        \IF {$ key < current.key $}
            \STATE {$ current \gets current.left $}
        \ELSE
            \STATE {$ current \gets current.right $}
        \ENDIF
    \ENDWHILE

    \STATE {}
    \STATE {$ node.parent \gets parent $}
    \IF {$ parent = $ \textsc{null}}
        \STATE {$ tree.root \gets node $}
    \ELSIF {$ key < parent.key $}
        \STATE {$ parent.left \gets node $}
    \ELSE
        \STATE {$ parent.right \gets node $}
    \ENDIF
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Usuwanie elementów

Przykład

Wariant 1: 0 węzłów potomnych

Wariant 2: 1 węzeł potomny

Wariant 3: 2 węzły potomne

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{TreeMinimum}{$ node $}
    \WHILE {$ node.left \neq $ \textsc{null}}
        \STATE {$ node \gets node.left $}
    \ENDWHILE
    \RETURN {$ node $}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{TreeDelete}{$ tree, node $}
    \IF {$ tree.root = $ \textsc{null} \OR $ node = $ \textsc{null}}
        \RETURN
    \ENDIF

    \STATE {}
    \IF {$ node.left = $ \textsc{null} \AND $ node.right = $ \textsc{null}}
        \IF {$ node.parent = $ \textsc{null}}
            \STATE {$ tree.root \gets $ \textsc{null}}
        \ELSIF {$ node.parent.left = node $}
            \STATE {$ node.parent.left \gets $ \textsc{null}}
        \ELSE
            \STATE {$ node.parent.right \gets $ \textsc{null}}
        \ENDIF
        \RETURN
    \ENDIF

    \STATE {}
    \IF {$ node.left = $ \textsc{null}}
        \IF {$ node.parent = $ \textsc{null}}
            \STATE {$ tree.root \gets node.right $}
        \ELSIF {$ node.parent.left = node $}
            \STATE {$ node.parent.left \gets node.right $}
        \ELSE
            \STATE {$ node.parent.right \gets node.right $}
        \ENDIF
        \STATE {$ node.right.parent \gets node.parent $}
        \RETURN
    \ENDIF

    \STATE {}
    \IF {$ node.right = $ \textsc{null}}
        \IF {$ node.parent = $ \textsc{null}}
            \STATE {$ tree.root \gets node.left $}
        \ELSIF {$ node.parent.left = node $}
            \STATE {$ node.parent.left \gets node.left $}
        \ELSE
            \STATE {$ node.parent.right \gets node.left $}
        \ENDIF
        \STATE {$ node.left.parent \gets node.parent $}
        \RETURN
    \ENDIF

    \STATE {}
    \STATE {$ succesor \gets $ \CALL{TreeMinimum}{$ node.right $}}
    \STATE {$ node.key \gets successor.key $}
    \STATE \CALL{TreeDelete}{$ tree, successor $}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Zrównoważone drzewo BST

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{TreeInsertBiject}{$ tree, array, p, r $}
    \IF {$ p = r $}
        \STATE \CALL{TreeInsert}{$ tree, array[p] $}
    \ELSIF {$ r - p = 1 $}
        \STATE \CALL{TreeInsert}{$ tree, array[p] $}
        \STATE \CALL{TreeInsert}{$ tree, array[r] $}
    \ELSE
        \STATE {$ q \gets p + \frac{r - p}{2} $}
        \STATE \CALL{TreeInsert}{$ tree, array[q] $}
        \STATE \CALL{TreeInsertBiject}{$ tree, array, p, q - 1 $}
        \STATE \CALL{TreeInsertBiject}{$ tree, array, q + 1, r $}
    \ENDIF
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{BalancedTreeCreate}{$ tree, array, n $}
    \STATE \CALL{Sort}{$ array, n $}
    \STATE \CALL{TreeInsertBiject}{$ tree, array, 0, n-1 $}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Przechodzenie drzewa binarnego

Istnieją trzy sposoby przechodzenia drzewa binarnego:

• pre-order (wypisz-lewe-prawe)
• in-order (lewe-wypisz-prawe)
• post-order (lewe-prawe-wypisz)

Podane trzy akcje oznaczają:

• wypisz: wyświetl wartość w aktualnie przeglądanym węźle
• lewe: rekurencyjnie wywołaj przechodzenie drzewa dla lewego potomka
• prawe: jw. dla prawego potomka

Pre-order (w kolejności dodawania)

In-order (w kolejności rosnącej)

Post-order (w kolejności usuwania)

Przykład przechodzenia drzewa

• pre-order: 4 2 1 3 6 5 7
• in-order: 1 2 3 4 5 6 7
• post-order: 1 3 2 5 7 6 4

Treść zadania

Na ocenę 3.0

• Zaimplementuj strukturę danych typu FIFO (operacje Enqueue, Dequeue)
• Zaimplementuj strukturę danych typu LIFO (operacje Push, Pop)

Na ocenę 3.5

• Zaimplementuj strukturę danych typu lista dwukierunkowa (operacje ListSearch, ListInsert, ListDelete)

Na ocenę 4.0

• Zaimplementuj strukturę danych typu BST (operacje TreeSearch, TreeInsert)
• Zaimplementuj przechodzenie przez drzewo metodami pre-order, in-order oraz post-order

Na ocenę 4.5

• Zaimplementuj budowanie dokładnie wyważonego drzewa BST (operacja BalancedTreeCreate)

Na ocenę 5.0

• Zaimplementuj usuwanie węzłów z drzewa BST (operacja TreeDelete)

Sprawozdanie

• Zmierz czas działania operacji ListSearch dla różnych wartości n i przedstaw wyniki na wykresie (na ocenę 3.5):

  1. Wygeneruj n liczb w tablicy
  2. Dodaj je w takiej kolejności do listy
  3. Losowo przetasuj tablicę
  4. Zacznij mierzyć czas
  5. Powtórz m razy znalezienie każdej wartości w tablicy
  6. Podziel zmierzony czas przez n i przez m by otrzymać średni czas znalezienia jednego elementu dla listy długości n

• Ważne! W powyższym chodzi o to, żeby zmierzyć łączny czas wyszukiwania wszystkich elementów i następnie go podzielić przez liczbę elementów. Mierzenie czasu działania dla jednego elementu jest nieprawidłowe!

• Wykonaj eksperyment w dwóch wariantach dla zmieniającego się n:

  • Gdy w kroku 1 dane generowane są rosnąco
  • Gdy w kroku 1 dane generowane są losowo

• Wartość m określa ile będzie powtórzeń “szukania każdej wartości” i służy temu by zmierzyć czas, który potencjalnie jest bardzo niski (bliski zera)

• Wartość m należy dobrać eksperymentalnie, żeby żadne pomiary czasowe nie wynosiły zero (np. można zacząć od m=1 i podwajać dopóki którykolwiek z pomiarów czasowych wynosi zero)

• Uwaga! Odpowiednia wartość m może być różna w zależności od typu danych (rosnące / losowe) oraz typu struktury danych (listy / drzewa), więc dobór odpowiedniej wartości należy powtórzyć przy każdym eksperymencie

• Zmierz czas działania operacji TreeSearch analogicznie jak poprzednio (na ocenę 4.0)

• Zmierz czas działania operacji TreeSearch dla drzew zrównoważonych analogicznie jak poprzednio (na ocenę 4.5)

Pseudokod do operacji przetasowania tablicy

\begin{algorithm}
\begin{algorithmic}
\PROCEDURE{Shuffle}{$ array, n $}
    \FOR {$ i \gets n-1 $ \DOWNTO $ 2 $}
        \STATE {$ j \gets $} \CALL{Random}{$ 0, i-1 $}
        \STATE \CALL{Swap}{$ array, i, j$}
    \ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}