Implementation of Abstract Data Type (ADT) for Binary Search Trees (BSTs).

Created a spell checker implemented with BST and another one implemented with chained hash table(using arrays and linked list).

The spell checker that was implemented with binary search tree (BST) does read, check, insert and print the words from the two files in almost 0.6 sec in a Mac machine. This happens as the BST has an average time complexity for search, insertion and deletion of O(log n) and in worst case O(n).However, the spell checker implemented with hash tables does it in 0.25s in a Mac machine. This happens as the hash table has an average time complexity for search, insertion and deletion of O(1) and in worst case O(n).

The reason why the hash table implementation is faster lies on the fact that we have allocated an indexed array of double the size of the words of the biggest file. As otherwise we would have created longer linked lists which would require look up time closer to O(n) but we have eliminated that by making an array bigger (almost double) than the words to be input. It is worth mentioning that the quality of the hash function plays a key role of how long the linked lists will be as well.

In terms of space, comparing the two implementations, their average complexity is 0(n). More precisely, in case of BST we have an extra pointer in the structure which usually will cost us 4 bytes (in 32-bit system) while in the hash table we do not have this extra pointer. However, in the hash table, we initially allocate more space to the array than we will need. In our case, we allocate to the array almost double space for the elements (n) that we are going to input. Hence, because the structure in every node includes a char of size thirty (30) and a pointer will probably require more space than the BST. For example, if we allocate to the array double the size of the elements to be input, the space will be 2 * O(n) for the hash table while only O(n) for the BST.

Given that the amount of time for this extension section was limited I did not have the chance to work on adjusting the array size based on the words to be insert so as we do not allocate all the space in the start and so as we can reuse the code more efficiently for other files too.