Zadanie domowe #3
Do oceny można zgłosić maksymalnie trzy wybrane zadania domowe.
Nazwa repozytorium z rozwiązaniem:
AISDI-HW 3: Nazwisko
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:
trees.cpp
#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
}
// ...
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.
tree_basic.dot
tree.dot
# 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
}
# Tree in DOT format, extended with GNU M4 macros and some additional styling
#
# Styles:
# - null pointers [NULL]
# - root node [YELLOW]
# - invisible padding nodes & edges for more symmetrical binary
# tree [INVISIBLE_N/INVISIBLE_E]
#
# Generate PNG file with:
# > m4 tree.dot | dot -Tpng -o tree.png
define(YELLOW, `color = "#ffc49c", fillcolor = "#ffe1cc:#ffe7d7"')
define(NULL, `label = "", width = .1, height = .1, color = "#b3b3b3", fillcolor = "#d7d7d7:#e4e4e4"')
define(INVISIBLE_E, `style = invisible, arrowsize = 0, weight = 10')
define(INVISIBLE_N, `style = invisible, label = ""')
strict digraph dot {