((Explanation))
My program works almost completely, with the exception of occasional errors during LR and RL rotations. These errors are rare enough that they do not have a significant effect on my experiements.
(BST Dynamic Dictionary)
My implementation is pretty standard. The BST is created by linking nodes that each contain a key, some data, and references to a left and right child BSTNode. As expected from its definition, the BST follows the design pattern that for every node, A, in the BST, all nodes in A's right subtree are nodes greater than A and all nodes in A's left subtree are less than A. Reiterating, this property holds for all arbitrary A in the tree.
Nearly all of the operating methods employ recursion, which often necessitates overloaded methods (identical methods with the exception of their parameters and operation), where the user calls for instance the "find(key)" method which then in turn calls an internal method "find(key,BSTNode)" which is used in the recursion.
The find method simply starts on the root node, and unless operating on a null node or a node whose key is equal to the key being looked for (in which case the task is done and the data is returned), calls itself on the left and right child until
The insert method operates identically with the exception that it only calls itself on its appropriate child if the key being inserted is less than or greater than the key of the node currently considered. Because this is done recursively, it ensures that the node is inserted at the appropriate depth and in the right location. Note that only once we have reached the right depth is a new BSTNode created and returned).
The remove method operates identically in the tree traversal and identification of what node to remove, with the exception that once the node is deleted, we determine what node in the node deleted's subtree should fill in the newly created gap by finding the maximum value in the deleted node's left subtree.
The count and height function are also recursive, and simply operate by going recurring down to the bottom most level of the tree, and then returning 1 and upon each unfolding of the recursion, adding 1 to the current count (if the node had only one child). If the node has two children, we simply add 1 to sum of the count of the right and left subtree and in the case of height we add one to the max of the height of the left and right subtree.
A precondition of the findMax function is that the passed value must not be null.
(AVL Dynamic Dictionary)
This is again a pretty standard implementation, which most methods functioning as they did in the BST implementation. Each node holds the same as the BST implementation with the added properties of height and an extant int value which indicates whether they have been deleted (we use a lazy delete). We decided to use an integer rather than a boolean because an integer could hold the same information but also could be used in height and count calculations without translations into integers (which matter for functions like count).
The find, findMax, count, and height methods operating almost exactly as they did in the BST dynamic dictionary.
The insert functions almost identically, except we employ rotations to ensure a relatively balanced tree (this is the primary difference between BST and AVL trees). In each rotation, we ensure to update the new currentNodeConsidered (that is, the new root of the considered subtree) to ensure proper tree traversal. After each rotation, we update the height of every node in the tree recursively so that future imbalances can properly be detected.
The remove method operates more simply than the previous remove method as we use lazy delete, by which we mean we simply change a node's "extant" property to 0, leaving the tree otherwise the same. This saves a lot of hassle with updates and imbalancing that would be inefficient.
The updateHeight method works similarly to the height method, except it sets the height of the currentNodeConsidered to be equal to the returned value.
A precondition of the findMax function is that the passed value must not be null.
((Test Plan))
We have conducted some tests (included in the DDtester package) that manually insert nodes in such a way that certain rotations should take place automatically. In each of these cases, our results match the expectations and the count and height of the resulting tree matches expectations. We also performed the insertions while debugging and checked to make sure the tree matched the expected form by inspecting the value of all the necessary variables (essentially, manually traversing the tree).
We have also conducted various removes on both implementations and found that in both instances the number of nodes after these removals matches its expected value.
((Experiments))
We conducted the following trials each 5 times, and report the average runtime (in milliseconds). Note that each run contained n inserts and n removes.
(Random)
BST Dynamic Dictionary, n=10: 1.5
BST Dynamic Dictionary, n=30: 3.5
BST Dynamic Dictionary, n=50: 4.5
BST Dynamic Dictionary, n=100: 7
BST Dynamic Dictionary, n=200: 16
AVL Dynamic Dictionary, n=10: 3.5
AVL Dynamic Dictionary, n=30: 4.5
AVL Dynamic Dictionary, n=50: 6.5
AVL Dynamic Dictionary, n=100: 12
AVL Dynamic Dictionary, n=200: 32
(Increasing input)
BST Dynamic Dictionary, n=100: 2.5
BST Dynamic Dictionary, n=300: 8
BST Dynamic Dictionary, n=500: 16
BST Dynamic Dictionary, n=1000: 31
AVL Dynamic Dictionary, n=100: 10
AVL Dynamic Dictionary, n=300: 22
AVL Dynamic Dictionary, n=500: 34
AVL Dynamic Dictionary, n=1000: 66.5
(Decreasing input)
BST Dynamic Dictionary, n=100: 2.5
BST Dynamic Dictionary, n=300: 9
BST Dynamic Dictionary, n=500: 15
BST Dynamic Dictionary, n=1000: 28.5
AVL Dynamic Dictionary, n=100: 11
AVL Dynamic Dictionary, n=300: 22
AVL Dynamic Dictionary, n=500: 35
AVL Dynamic Dictionary, n=1000: 73
((Conclusions))
Our conclusions are pretty simple, and no graphs are necessary because the trend is evident, as we can easily see that the BST implementation is faster in every experiment conducted.
The BST implementation is about twice as fast in each test, and it seems as though this speed difference is n independent. The reasons for this are obvious: each time an insertion occurs, rebalancing often has to occur (especially in the ordered input experiments), which is time intensive. We must also realize that BSTs are faster despite the (faster) lazy delete implementation of AVL nodes.
However, we note that AVL trees do perform faster for finding nodes (because fewer layers of recursion are necessary as they have lower heights), especially in instances of ordered data (which is very taxing for BST trees as they are very tall and one sided). So there is still some use for AVL nodes yet.
((Honor Code))
I have neither given nor received unauthorized aid on this assignment.
Signed: