Zadanie domowe #3

Do oceny można zgłosić maksymalnie trzy wybrane zadania domowe.

Materiały pomocnicze do zadania znajdują się w repozytorium na GitHub.

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:

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
    }
// ...

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)

tree_basic.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.dot

tree_basic.png

tree.png

Przykład generowania szkicu drzewa za pomocą TikZ/LaTeX

tree.tex

\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}

tree.pdf

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.