Zadanie domowe #3
Do oceny można zgłosić maksymalnie trzy wybrane zadania domowe.
Nazwa repozytorium z rozwiązaniem: AISDI-HW 3: Nazwisko
Treść zadania
Rozpatrujemy standardowe binarne drzewo poszukiwań, drzewo typu splay i drzewo AVL. Proszę naszkicować kolejne stany poszczególnych drzew po każdej z wykonywanych operacji:
wstaw kolejno wartości
51, 22, 43, 84, 35, 86, 57, 98,następnie znajdź wartość
57,następnie usuń kolejno wartości
57, 51.
Schemat wywołania tych operacji wyglądałby następująco:
#include <vector>
template<typename Key>
struct Node {
Key key;
// ...
};
template<typename Key>
class Tree {
public:
// ...
virtual void erase(const Key& key) { /* ... */ }
virtual Node<Key>* insert(const Key& key) { /* ... */ }
virtual Node<Key>* find(const Key& key) const { /* ... */ }
};
template<typename Key>
class BinarySearchTree : public Tree<Key> {
// ...
};
template<typename Key>
class SplayTree : public Tree<Key> {
// ...
};
template<typename Key>
class AVLTree : public Tree<Key> {
// ...
};
// ...
auto bst = BinarySearchTree<int>();
auto splay = SplayTree<int>();
auto avl = AVLTree<int>();
std::vector<Tree<int>*> trees{};
trees.push_back(&bst);
trees.push_back(&splay);
trees.push_back(&avl);
// Operacje wykonujemy dla każdego typu drzewa
for (const auto& tree : trees) {
tree->insert(51); // ...-00.pdf
tree->insert(22); // ...-01.pdf
tree->insert(43); // ...-02.pdf
tree->insert(84); // ...-03.pdf
tree->insert(35); // ...-04.pdf
tree->insert(86); // ...-05.pdf
tree->insert(57); // ...-06.pdf
tree->insert(98); // ...-07.pdf
tree->find(57); // ...-08.pdf
tree->erase(57); // ...-09.pdf
tree->erase(51); // ...-10.pdf
}
// ...Do realizacji szkiców można wykorzystać na przykład pakiet Graphviz lub LaTeX.
W ramach niniejszego zadania domowego nie jest wymagana implementacja poszczególnych drzew. Operacje można "policzyć" na kartce i na tej podstawie bezpośrednio przygotować szkice.
Przykład zapisu drzewa w języku DOT (Graphviz)
Przykład generowania szkicu drzewa za pomocą TikZ/LaTeX
Pomocne narzędzia
Na stronie viz-js.com można poeksperymentować z zapisem w języku DOT bezpośrednio w przeglądarce, bez konieczności instalacji pakietu Graphviz.
VisuAlgo zawiera interaktywne wizualizacje drzewa BST, AVL i wielu innych struktur danych i algorytmów.
W repozytorium przygotowałem skrypt w Pythonie, który pozwala przyspieszyć generowanie wykresów za pomocą XeLaTeX-u.
Forma dostarczenia wyników
Proszę wgrać wynikowe pliki do repozytorium oznaczając je jednoznacznie co do kolejności (np. bst-00.png, ..., bst-10.png) lub scalając w jeden obraz/PDF. Nie jest konieczne załączanie plików pomocniczych czy implementacji drzew. Do wizualizacji można wykorzystać również inne dowolne narzędzia. W ostateczności może nimi być kartka i ołówek, ale preferowane są wersje elektroniczne.
Last updated