156 lines
7.5 KiB
TeX
156 lines
7.5 KiB
TeX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
||
%% I, the copyright holder of this work, release this work into the
|
||
%% public domain. This applies worldwide. In some countries this may
|
||
%% not be legally possible; if so: I grant anyone the right to use
|
||
%% this work for any purpose, without any conditions, unless such
|
||
%% conditions are required by law.
|
||
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
||
|
||
\documentclass[
|
||
digital, %% The `digital` option enables the default options for the
|
||
%% digital version of a document. Replace with `printed`
|
||
%% to enable the default options for the printed version
|
||
%% of a document.
|
||
color, %% Uncomment these lines (by removing the %% at the
|
||
%% beginning) to use color in the digital version of your
|
||
%% document
|
||
notable, %% The `table` option causes the coloring of tables.
|
||
%% Replace with `notable` to restore plain LaTeX tables.
|
||
oneside, %% The `twoside` option enables double-sided typesetting.
|
||
%% Use at least 120 g/m² paper to prevent show-through.
|
||
%% Replace with `oneside` to use one-sided typesetting;
|
||
%% use only if you don’t have access to a double-sided
|
||
%% printer, or if one-sided typesetting is a formal
|
||
%% requirement at your faculty.
|
||
nolof, %% The `lof` option prints the List of Figures. Replace
|
||
%% with `nolof` to hide the List of Figures.
|
||
nolot, %% The `lot` option prints the List of Tables. Replace
|
||
%% with `nolot` to hide the List of Tables.
|
||
%% More options are listed in the user guide at
|
||
%% <http://mirrors.ctan.org/macros/latex/contrib/fithesis/guide/mu/fi.pdf>.
|
||
]{fithesis3}
|
||
%% The following section sets up the locales used in the thesis.
|
||
\usepackage[resetfonts]{cmap} %% We need to load the T2A font encoding
|
||
\usepackage[T1,T2A]{fontenc} %% to use the Cyrillic fonts with Russian texts.
|
||
\usepackage[
|
||
main=english, %% By using `czech` or `slovak` as the main locale
|
||
%% instead of `english`, you can typeset the thesis
|
||
%% in either Czech or Slovak, respectively.
|
||
english, czech, slovak %% The additional keys allow
|
||
]{babel} %% foreign texts to be typeset as follows:
|
||
%%
|
||
%% \begin{otherlanguage}{german} ... \end{otherlanguage}
|
||
%% \begin{otherlanguage}{russian} ... \end{otherlanguage}
|
||
%% \begin{otherlanguage}{czech} ... \end{otherlanguage}
|
||
%% \begin{otherlanguage}{slovak} ... \end{otherlanguage}
|
||
%%
|
||
%% For non-Latin scripts, it may be necessary to load additional
|
||
%% fonts:
|
||
\usepackage{paratype}
|
||
\def\textrussian#1{{\usefont{T2A}{PTSerif-TLF}{m}{rm}#1}}
|
||
%%
|
||
%% The following section sets up the metadata of the thesis.
|
||
\thesissetup{
|
||
date = \the\year/\the\month/\the\day,
|
||
university = mu,
|
||
faculty = fi,
|
||
type = bc,
|
||
author = Matej Focko,
|
||
gender = m,
|
||
advisor = {prof. RNDr. Ivana Černá, CSc.},
|
||
title = {Rank-Balanced Trees},
|
||
TeXtitle = {Rank-Balanced Trees},
|
||
keywords = {algorithms, data structures, rank, trees, balanced trees, study material, visualization, AVL, WAVL},
|
||
TeXkeywords = {algorithms, data structures, rank, trees, balanced trees, study material, visualization, AVL, WAVL},
|
||
abstract = {%
|
||
In this bachelor thesis, we demonstrate the usage of a rank for implementing balanced binary search trees and algorithms related to a specific rank-balanced tree, the weak AVL tree. In the first part of the thesis, we present commonly used balanced search trees. In the second part, we describe the rank-balanced tree, followed by a comparison to other balanced trees that can be implemented using rank, and also diagrams and pseudocodes related to the weak AVL tree. We also present an implementation of the weak AVL tree in Python, tested with property-based testing. The final part of the thesis is a web page that allows performing operations on the weak AVL tree with animations and a step-by-step walkthrough of pseudocode.
|
||
},
|
||
thanks = {%
|
||
First, I would like to thank my advisor, Ivana Černá, for her support, valuable suggestions and patience during the writing of this thesis. Secondly, I want to thank my friends and family for their support. Last but not least, I would like to thank Elice and Villain Village for being in the background while I was losing my mind over web development.
|
||
},
|
||
bib = bibliography.bib,
|
||
%% Uncomment the following line (by removing the %% at the
|
||
%% beginning) and replace `assignment.pdf` with the filename
|
||
%% of your scanned thesis assignment.
|
||
%% assignment = assignment.pdf,
|
||
}
|
||
\usepackage{makeidx} %% The `makeidx` package contains
|
||
\makeindex %% helper commands for index typesetting.
|
||
%% These additional packages are used within the document:
|
||
\usepackage{paralist} %% Compact list environments
|
||
\usepackage{amsmath} %% Mathematics
|
||
\usepackage{amsthm}
|
||
\usepackage{amsfonts}
|
||
\usepackage{url} %% Hyperlinks
|
||
\usepackage{tabularx} %% Tables
|
||
\usepackage{tabu}
|
||
\usepackage{booktabs}
|
||
\usepackage[vlined,longend,linesnumbered]{algorithm2e}
|
||
\usepackage{listings} %% Source code highlighting
|
||
\lstset{
|
||
basicstyle = \ttfamily,
|
||
identifierstyle = \color{black},
|
||
keywordstyle = \color{blue},
|
||
keywordstyle = {[2]\color{cyan}},
|
||
keywordstyle = {[3]\color{olive}},
|
||
stringstyle = \color{teal},
|
||
commentstyle = \itshape\color{magenta},
|
||
breaklines = true,
|
||
}
|
||
\usepackage{floatrow} %% Putting captions above tables
|
||
\floatsetup[table]{capposition=top}
|
||
\usepackage{hyperref}
|
||
|
||
\usepackage[x11names, svgnames, rgb]{xcolor}
|
||
\usepackage{tikz}
|
||
\usetikzlibrary{decorations,arrows,shapes}
|
||
\usetikzlibrary{trees}
|
||
\tikzset{
|
||
treenode/.style = {shape=circle, draw, align=center,},
|
||
left side node/.style={above left, inner sep=0.1em},
|
||
right side node/.style={above right, inner sep=0.1em}
|
||
}
|
||
|
||
\usepackage{graphicx}
|
||
|
||
\SetKwProg{Fn}{function}{ is}{end}
|
||
\SetKwProg{Proc}{procedure}{ is}{end}
|
||
|
||
\newcommand{\avlDeleteRebalance}{\hyperref[algorithm:avl:deleteRebalance]{\texttt{deleteRebalance}}}
|
||
\newcommand{\avlDeleteFixNode}{\hyperref[algorithm:avl:deleteFixNode]{\texttt{deleteFixNode}}}
|
||
\newcommand{\avlDeleteRotate}{\hyperref[algorithm:avl:deleteRotate]{\texttt{deleteRotate}}}
|
||
|
||
\newcommand{\findParentNode}{\hyperref[algorithm:findParentNode]{\texttt{findParentNode}}}
|
||
|
||
\newcommand{\wavlInsertRebalance}{\hyperref[algorithm:wavl:insertRebalance]{\texttt{insertRebalance}}}
|
||
\newcommand{\wavlFixZeroChild}{\hyperref[algorithm:wavl:fix0Child]{\texttt{fix0Child}}}
|
||
|
||
\newcommand{\wavlDeleteRebalance}{\hyperref[algorithm:wavl:deleteRebalance]{\texttt{deleteRebalance}}}
|
||
\newcommand{\wavlBottomUpDelete}{\hyperref[algorithm:wavl:bottomUpDelete]{\texttt{bottomUpDelete}}}
|
||
\newcommand{\wavlFixDelete}{\hyperref[algorithm:wavl:fixDelete]{\texttt{fixDelete}}}
|
||
|
||
\begin{document}
|
||
|
||
\include{introduction}
|
||
\include{self_balancing_search_trees}
|
||
\include{rank_balanced_trees}
|
||
\include{wavl_trees}
|
||
\include{implementation}
|
||
\include{visualization}
|
||
\include{summary}
|
||
|
||
\printbibliography
|
||
|
||
\appendix %% Start the appendices.
|
||
\chapter{Source code}
|
||
The source code can be found in the appendix of this thesis as \texttt{wavl.zip}. It consists of the following directories:
|
||
|
||
\begin{itemize}
|
||
\item \texttt{python}, which contains the implementation in the Python.
|
||
\item \texttt{thesis}, which contains the source code of this thesis.
|
||
\item \texttt{web}, which contains the implementation of the web page.
|
||
\end{itemize}
|
||
|
||
Contents of the \texttt{wavl.zip} is also present at \url{https://fi.muni.cz/~xfocko/wavl}.
|
||
|
||
\end{document}
|