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)
# Basic tree in DOT format
#
# Generate PNG file with:
# > dot -Tpng -o tree_basic.png tree_basic.dot
strict digraph dot {
40 -> 20
40 -> 60
20 -> 10
20 -> 30
60 -> 50
60 -> 70
}
Przykład generowania szkicu drzewa za pomocą TikZ/LaTeX
\documentclass[crop,tikz,10pt]{standalone}
\usepackage{xcolor}
\definecolor{background}{HTML}{F0F4F5}
\definecolor{border}{HTML}{D3E0E3}
\definecolor{blue}{HTML}{1395ba}
\definecolor{dark_blue}{HTML}{0e708c}
\definecolor{pink}{HTML}{f8216e}
\definecolor{dark_pink}{HTML}{b3174e}
\definecolor{yellow}{HTML}{f8ca00}
\definecolor{orange}{HTML}{ff8a39}
\definecolor{green}{HTML}{4fa400}
\definecolor{dark_green}{HTML}{306400}
\usepackage{tikz}
\usetikzlibrary{
arrows,
backgrounds,
positioning,
}
\begin{document}
\begin{tikzpicture}[%
scale=1.0,
node distance=0.5cm,
every node/.style={minimum size=0, inner sep=0},
on grid,
background rectangle/.style={draw=border!80!black,fill=background},
show background rectangle,
inner frame sep=0.5cm,
level/.style={
sibling distance = 5cm/#1,
level distance = 1.5cm
},
every node/.style={
font=\sffamily\footnotesize,
circle,
minimum size=0.6cm,
line width=0.025cm,
draw=blue!50,
top color=blue!20,
bottom color=blue!30,
},
root/.style={
draw=yellow!50,
top color=yellow!20,
bottom color=yellow!30,
},
null/.style={
minimum size=0.2cm,
inner sep=0,
draw=black!30,
top color=black!10,
bottom color=black!20,
},
edge from parent/.style={
draw,
pink,
thick
}
]
\clip (0, 0) rectangle (10.0, 7.0);
\node [root] at (5, 6) {40}
child {
node {20}
child {
node {10}
child { node [null] {} }
child { node {15} }
}
child {
node {30}
child { node {25} }
child { node {35} }
}
}
child {
node {60}
child {
node {50}
child { node [null] {} }
child { node {55} }
}
child {
node {70}
child { node {65} }
child { node {75} }
}
}
;
\end{tikzpicture}
\end{document}
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