Dany jest następujący szkielet klasy listy jednokierunkowej:

struct Node {
    Node* next;
    int value;
};
​
class LinkedList {
  public:
    int length;
    Node* head;
​
    LinkedList();
​
    void erase_after(int pos);  // usuwa elem. za pozycją pos
    void insert_after(int pos, int value);  // wstawia elem. za pozycją pos
    void pop_front();  // usuwa pierwszy element
    void push_front(int value);  // wstawia element na początek listy
};

Zaimplementuj brakujące metody.

Zaimplementuj metodę, która dla listy jednokierunkowej zwróci trzeci element od końca. Załóż, że długość listy nie jest znana.

Zaimplementuj metodę, która zwróci środkowy element listy jednokierunkowej. Załóż, że długość listy nie jest znana.

Zaproponuj sposób odwracania listy jednokierunkowej w jednym przejściu bez tworzenia kopii wszystkich elementów.

Zaproponuj sposób usuwania węzła mając tylko odwołanie do niego. Załóż, że nie jest to ostatni węzeł listy.

Zaimplementuj uproszczony iterator (tylko operacje -> i ++ ) po elementach listy. Jak wyglądałby taki iterator, gdyby miał zwracać najpierw elementy na rosnących pozycjach nieparzystych listy, a następnie na parzystych?

Narysuj binarne drzewo poszukiwań utworzone przez wstawienie w kolejności elementów:

31, 72, 23, 44, 85, 106, 17, 28, 9, 30, 41

Zaimplementuj metody wstawiania i wyszukiwania węzła w drzewie BST.

Zaimplementuj rekursywne przechodzenie po węzłach drzewa w kolejności "in-order".

Zaimplementuj uproszczony iterator (tylko operacje -> i ++ ), który będzie przechodził węzły drzewa w kolejności "in-order".

Zaimplementuj w klasie drzewa BST funkcjonalność usuwania węzła o zadanej wartości.

Stwórz dwa drzewa BST przez wstawianie w kolejności następujących wartości:

A: 40, 20, 60, 10, 30, 50, 70

B: 10, 20, 30, 40, 50, 60, 70

Porównaj złożoność podstawowych operacji dla obydwu drzew.

Następnie dla drzewa niezrównoważonego B wykonaj kolejno operacje rotacji:

• L(40)

• L(30)

• L(20)

• L(10)

• L(20)

Dane jest drzewo splay o takiej samej strukturze jak drzewo A z zadania 1.

Wykonaj w kolejności następujące operacje:

• znajdź element o wartości 30,

• znajdź element o wartości 50,

• wstaw element o wartości 25,

• wstaw element o wartości 22,

• usuń element o wartości 50,

• usuń element o wartości 25.

Stwórz drzewo AVL przez wstawianie kolejno wartości:

10, 20, 30, 40, 50, 60, 70

Na stworzonym drzewie przeprowadź operacje:

• wstaw element o wartości 55,

• wstaw element o wartości 52,

• usuń element o wartości 52,

• usuń element o wartości 70.

Zapisz w reprezentacji tablicowej drzewo binarne następującej postaci:

Dla zapisu tablicowego:

[95, 80, 85, 40, 70, 90, 50, 30, 10, 20]

narysuj zupełne drzewo binarne. Czy drzewo to przedstawia kopiec typu max-heap?

Do pustego kopca binarnego max-heap wstaw w kolejności elementy o wartościach klucza:

43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40

Następnie trzykrotnie wykonaj operację usunięcia największego elementu z kopca.

Zilustruj stan kopca po każdym kroku.

Z podanej tablicy stwórz kopiec binarny typu max-heap metodą Floyda (przywracanie własności kopca kolejnym poddrzewom):

[2, 7, 26, 25, 19, 17, 1, 90, 3, 36]

Zlicz ilość wykonanych operacji, porównaj z metodą tworzenia kopca przez wstawianie.

Do pustego kopca 3-arnego (ternary heap) typu max-heap wstaw w kolejności elementy o wartościach klucza:

43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40

Następnie trzykrotnie wykonaj operację usunięcia największego elementu z kopca.

Zilustruj stan kopca po każdym kroku.

Do pustego kopca dwumianowego typu min-heap wstaw w kolejności elementy o wartościach klucza:

43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40

Następnie trzykrotnie wykonaj operację usunięcia najmniejszego elementu z kopca.

Zilustruj stan kopca po każdym kroku.

Do pustego kopca Fibonacciego typu min-heap wstaw w kolejności elementy o wartościach klucza:

43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40

Następnie trzykrotnie wykonaj operację usunięcia najmniejszego elementu z kopca.

Zilustruj stan kopca po każdym kroku.

Porównaj stany przejściowe kopca stworzonego na bazie poniższego ciągu operacji:

• push(43),

• push(24),

• push(11),

• push(47),

• pop(),

• push(13),

• push(67),

• pop(),

• push(59),

• push(95),

• pop(),

• push(29),

• push(17),

• pop(),

• push(54),

• pop(),

• push(40).