report.txt

Advanced Topics in Algorithms (2016/2017) - Assignment 2

Implementation by:
	André Cascais  	up201103896
	Raul Ferreira	up200905641

The group decided to implement some Self Balancing Structures for this assignment due to fact that they were an upgrade over the similar structures implemented by us before.
The language of choice was C++ due to its fast execution times and also as a challenge to get more accustomed to the language.
We looked firstly at both AVL and Red-black Trees and then expanded our work to Splay Trees as well.

The AVL was not so hard to implement, being somewhat similar to regular binary trees, due to us making sure that all of the pointers to fathers/sons were set correctly.
There were however a few tough cases but after using both https://www.ics.uci.edu/~pattis/ICS-46/lectures/notes/avl.txt for guidance and https://www.cs.usfca.edu/~galles/visualization/AVLtree.html for debugging/visualization, the job was made much easier.
This structure has a complexity of O(log(n)) for both insertion, removal and lookup and the height of it isn't bigger than ~ 1.44 log(n) for n > 3, as we were able to show experimentally.
This structure is most useful when we have to guarantee low cost in all of the operations and it grants us the lowest bound for the tree height.

The Red-Black Trees were the hardest of the structures to implement. Its tricky cases that can fallthrough into one another, along with a harder to fully understand algorithm made the debug process a lot harder since the failures were usually simple cases but it could be hard to understand exactly where things went wrong.
This structure has the same complexity for all of the operations when compared to the AVLTrees, it is overall a bit faster but it can't guarantee such a lower bound for the height of the tree.
This new bound is O(2*log(n)). Red-Black trees are highly used in the industry.

The Splay Trees were the easiest to implement of all of these structures, after already having the generic code prototype for the trees as well as implementations of rotations, insertions, lookups, etc.
This structure can have bad complexities for single instructions but its amortized costs are in the same complexity of the previous structures.
This structure is most useful due to its relatively easy implementation and especially when we expect to have to lookup for the same element several times in the near future.