AIDS-Sprawozdanie.tex

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[polish]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\author{Maksymilian Ryder}
\title{Złożone struktury danych}

\usepackage{hyperref}

\usepackage{booktabs}
\usepackage{multirow}

\usepackage[dvipsnames]{xcolor}

\usepackage{pgfplots}
\pgfplotsset{compat=newest}
\usepgfplotslibrary{units}
\pgfplotsset{
	every axis legend/.append style={
		at={(1.01,1)},
		anchor=north west
	}
}

\begin{document}
\maketitle
\medskip 
\medskip 
\medskip 
\medskip 
Implementacja algorytmu konstruowania drzewa AVL metodą przeszukiwania binarnego oraz algorytmu konstruowania „losowego” drzewa BST


\section{Wykresy}
\subsection{Czas Tworzenia}
\medskip
\begin{tikzpicture}
\begin{axis}[
	width=13cm,
	height=12cm,
	ylabel=$time$,
	xlabel=$size$,
	y unit=s, y SI prefix=nano,
	title={Creation Time}
	]
\addplot [smooth, mark=*, mark size=0.5pt]
	plot [error bars/.cd, y dir = both, y explicit]
	table[
		x=size,
		y=creation_time,
		col sep=semicolon
	]
	{data/RandomListGenerator/AVL.csv};
\addlegendentry{AVL}

\addplot [smooth, color=Dandelion, mark=*, mark size=0.5pt]
	plot [error bars/.cd, y dir = both, y explicit]
	table[
		x=size,
		y=creation_time,
		col sep=semicolon
	]
	{data/RandomListGenerator/BST.csv};
\addlegendentry{BST}
\end{axis}
\end{tikzpicture}

\subsection{Czas Znajdywania najmniejszej wartości}

\begin{tikzpicture}
\begin{axis}[
	width=13cm,
	height=5cm,
	ylabel=$time$,
	xlabel=$size$,
	y unit=s, y SI prefix=nano,
	title={Trace Smallest Value Time}
	]
\addplot [smooth, mark=*, mark size=0.5pt]
	plot [error bars/.cd, y dir = both, y explicit]
	table[
		x=size,
		y=trace_min_time,
		col sep=semicolon
	]
	{data/RandomListGenerator/AVL.csv};
\addlegendentry{AVL}

\addplot [smooth, color=Dandelion, mark=*, mark size=0.5pt]
	plot [error bars/.cd, y dir = both, y explicit]
	table[
		x=size,
		y=find_min_time,
		col sep=semicolon
	]
	{data/RandomListGenerator/BST.csv};
\addlegendentry{BST}
\end{axis}
\end{tikzpicture}
\medskip
\subsection{Czas Przejścia Drzewa In Order}
\medskip
\begin{tikzpicture}
\begin{axis}[
	width=13cm,
	height=5cm,
	ylabel=$time$,
	xlabel=$size$,
	y unit=s, y SI prefix=nano,
	title={Trace In Order Time}
	]
\addplot [smooth, mark=*, mark size=0.5pt]
	plot [error bars/.cd, y dir = both, y explicit]
	table[
		x=size,
		y=trace_in_order,
		col sep=semicolon
	]
	{data/RandomListGenerator/AVL.csv};
\addlegendentry{AVL}

\addplot [smooth, color=Dandelion, mark=*, mark size=0.5pt]
	plot [error bars/.cd, y dir = both, y explicit]
	table[
		x=size,
		y=trace_inorder_time,
		col sep=semicolon
	]
	{data/RandomListGenerator/BST.csv};
\addlegendentry{BST}
\end{axis}
\end{tikzpicture}
\medskip
\subsection{Czas Balansowania Drzewa}
\medskip
\begin{tikzpicture}
\begin{axis}[
	width=13cm,
	height=5cm,
	ylabel=$time$,
	xlabel=$size$,
	y unit=s, y SI prefix=nano,
	title={Balance BST}
	]
	
\addplot [smooth, color=Dandelion, mark=*, mark size=0.5pt]
	plot [error bars/.cd, y dir = both, y explicit]
	table[
		x=size,
		y=balance_time,
		col sep=semicolon
	]
	{data/RandomListGenerator/BST.csv};
\end{axis}
\end{tikzpicture}
\medskip
\section{Podsumowanie}
Wartości próbkowania:
\begin{description}
\item[Rozmiar] 1000 - 13000
\item[Krok] 1000
\item[Liczność] 50x
\end{description}

Jak łatwo można zaobserwować, drzewo AVL tworzy się szybciej oraz wymaga mniej czasu na pobieranie wartości niż BST z tymi samymi danymi.
Drzewo AVL powstaje tak naprawdę dużo dłużej, gdyż wymaga uformowania drzewa BST z podanych wartości, lecz czas  na to potrzebny nie jest brany pod uwagę podczas liczenia.

Drzewo AVL teoretycznie jest nieporównywanie szybsze, podczas pobierania wartości, ale operacje dodawania i usuwania elementów, zajmują odpowiednio więcej czasu ponieważ wymagają wyważania lokalnego drzewa.

Kiedy stosować jaką strukturę? Jeśli potrzebujemy często dodawać i usuwać wartości to BST będzie idealnym wyborem. AVL użyjemy w sytuacji gdy skupiać się będziemy na pobieraniu informacji i ich statycznym przetrzymywaniu.

\section{Kod}

\href{https://github.com/McSymilian/AISD_PUT_Testing_Support/tree/master/src/main/java/org/data_structures/tree}{GitHub repository}
\end{document}