1. Zaproponuj implementację operacji delmin w drzewach BST i AVL. Oszacuj i porównaj koszty wykonania tych operacji w obu strukturach.
    
2. Napisz algorytmy operacji insert, delmin i min  w kopcu zakładając, że etykietami są liczby naturalne, a porządkiem w zbiorze etykiet kopca jest relacja ³.
    
3. Napisz algorytm znajdowania k-tego co do wielkości elementu, jedynie z użyciem  operacji charakterystycznych dla kolejek priorytetowych. Jaki jest koszt tego algorytmu. Porównaj otrzymany wynik z algorytmem Hoare (wykład III).
    
4. Jaki będzie koszt operacji wyszukiwania elementu w tablicy z haszowaniem, jeżeli problem kolizji został rozwiązany przez utworzenie drzew BST dla elementów, których adresy są takie same?
    
5. Porównaj kolejki z kolejkami priorytetowymi:
   • Wskaż własności prawdziwe w strukturze kolejek priorytetowych, które różnią tę strukturę od struktury kolejek FIFO.
   • Wskaż własności prawdziwe w strukturze kolejek FIFO, które nie są prawdziwe w strukturze kolejek priorytetowych.
   • Wskaż własności prawdziwe w obu strukturach.
   • Wyraź te własności w terminach: wstaw do struktury wskazany  element, struktura jest pusta, wskaż i  usuń ze struktury element pierwszy, interpretując te operacje w strukturze kolejek FIFO, a następnie  w strukturze kolejek priorytetowych. Jeśli okaże się to potrzebne użyj dodatkowo relacji należenia do zbioru reprezentowanego przez strukturę.
      
6. Definicja: Dwukopiec jest to graf z wyróżnionym wierzchołkiem r (korzeniem) taki, że (a) każdy węzeł tego grafu, z wyjątkiem korzenia ma dwa poprzedniki i każdy węzeł, z wyjątkiem liści ma dwa następniki, (b) etykiety poprzedników są mniejsze od etykiety węzła, a etykiety jego następników są większe, (c)  ponadto, jeśli zbiór wierzchołków równoodległych od korzenia nazwiemy poziomem w dwukopcu, to poziom ity ma i elementów o ile i(i+1)/2 < n, gdzie n jest liczbą wierzchołków dwukopca, oraz jest wypełniony w sposób zwarty (bez "dziur"). 
   Uwaga: Dwukopiec przypomina kopiec, ale nie jest drzewem. Podobnie jak kopiec jest zapisywany w tablicy. Dokładna definicja znajduje się w książce Banachowski L., Kreczmar A., Rytter W. "Analiza algorytmów i struktur danych", WNT, 1987.
   Zaproponuj sposób zapisania dwukopca w tablicy i algorytm wstawiania elementu do dwukopca.
    
7. Definicja: 2-3 drzewem nazywamy drzewo z wyróżnionym korzeniem, takie że
   • każdy wierzchołek wewnętrzny ma dwa albo trzy następniki,
   • wszystkie liście znajdują się na ostatnim poziomie drzewa, a ciąg etykiet liści czytanych od lewej do prawej tworzy ciąg uporządkowany rosnąco,
   • etykietami liści są elementy reprezentowanego przez 2-3 drzewo zbioru, a każdy wierzchołek wewnętrzny przechowuje wartość największego elementu w pierwszym poddrzewie i wartość największego elementu w drugim poddrzewie. 

   Zaproponuj algorytm wyszukiwania elementu w danym 2-3 drzewie.

 

« poprzedni punkt

następny punkt »