10 lines
No EOL
1.6 KiB
TeX
10 lines
No EOL
1.6 KiB
TeX
\chapter*{Summary}
|
|
\addcontentsline{toc}{chapter}{Summary}
|
|
|
|
In this thesis, we have presented a different view on the balancing of the binary search trees, and that is the rank-balanced tree as described by \textit{Haeupler et al.}~\cite{wavl}. Apart from describing the algorithms that implement the AVL tree using the rank-balanced tree, we have also described the WAVL tree, a relaxation of the AVL tree presented in the article mentioned above.
|
|
|
|
All of the rules that were presented are tied to the self-balancing binary search trees that base their balancing on the height of the tree. During the implementation and experiments, we have concluded that it should also be possible to implement a self-balanced binary tree that bases the balancing on the sizes of the subtrees rather than their heights. An example of such tree is described in the \textit{Functional Pearls: Efficient sets -- a balancing act} by \textit{Stephen Adams}~\cite{adams_1993}. Therefore, we conclude that rank as a balancing tool is quite flexible.
|
|
|
|
The thesis also includes the implementation of the rank-balanced tree in Python for the AVL, WAVL and rAVL trees with a set of property-based tests that can be used to verify any part of the implementation.
|
|
|
|
The last and probably most expressive part of the thesis is the web page that allows visualization of the WAVL tree and also compares operations on pair of chosen trees from AVL, WAVL or rAVL. This tool is quite demanding on the screen resolution, and in the case of the comparator, we do not see many options for the improvement, as having two trees side-by-side is quite space-consuming. |