Logan Ortega!1CMPSC 130A: PA2 !Adelson-Velskii and Landis’ Tree & Binary Search Tree Profiling ABSTRACT!Upon profiling the implementation of AVL and BST data structures, the evidence clearly states the superiority of the AVL Tree. The basis of this report will be the comparison of runtimes for insert, access and delete operations. The insert operations of both structures are iterative, while their delete operations share a recursive nature. It should be noted that the delete operations of both trees form their basic branching structure from a while loop; however, the BST’s special case of a node having two children requires a recursive call to remove the value after being swapped from the position as left-most child of the right subtree. The following content of this report will consist of multiple graphs illustrating the relationship between the above operations and their respective data structures, as well as a brief description and analysis of the graphs and their significance. Note the x-axis represents the sample size in increments of one thousand elements, while the y-axis shows the relative processing time in seconds. !CASE 1: INCREASING, INCREASING, INCREASING!The first case of observance comes from comparing both structures when inserting, accessing and deleting N elements, the sample size, in an increasing order. Graphs 1.1 through 1.3 illustrate the relationship between these operations and their respective data structures. It is evident in all operations that the AVL’s processing time exceeds the efficiency of the BST’s. For the insert and access operations, the AVL runs in O(log N), while the BST runs in O(N). However, the delete operation runs in O(log N) for both data trees. To conceptualize these relationships, we must imagine the structures of each tree. While the AVL has its rotations to balance the tree’s height, the BST has no such checks. Consequently, the BST in this first case is in essence a linked list, so inserting and accessing is linear. Whereas the AVL only has to travel the height of the tree, log N, in the worst case to find an element. Since we are deleting in the same order as insertion, the BST simply needs to replace the root with its right child and runs at the same rate as the AVL. This however does not mean that they are equally efficient as is clearly illustrated by Graph 1.3. !!!!!!!!!!!!!!!!!!!Graph 1.1Graph 1.2Graph 1.3Logan Ortega!2!CASE 2: INCREASING, DECREASING, DECREASING!The second case of observance comes from comparing both structures when inserting N elements in an increasing order then accessing and deleting the same N elements in a decreasing order. Graphs 2.1 through 2.3 illustrate the relationship between these operations and their respective data structures. It is once again evident in all operations that the AVL’s processing time exceeds the efficiency of the BST’s. Once again, all three operations run in O(log N) for the AVL; however, in this case, all three operations run in O(N) for the BST. Just like before the AVL’s rotations allow it to only traverse ceil(log N) nodes, the height of the tree, to insert, access or delete. Similar to case 1, the structure of the BST after strictly increasing inserts is simply a linked list. Because of this primitive structure of the tree, accesses and deletes of elements with decreasing key value run in linear time. This is a result of having to travel the entire height of the tree, N, to find the node of interest. !!!!!!!!!!!!!!!!!!!!!!CASE 3: RANDOM, RANDOM, RANDOM!The third case of observance comes from comparing both structures when inserting, accessing and deleting N elements in a random order. Graphs 3.1 through 3.3 illustrate the relationship between these operations and their respective data structures. Contrary to the previous two cases, it is not completely obvious that the AVL’s processing time exceeds that of the BST. All three operations for both data structures run in O(log N). The rotations of the AVL guarantee its operations run in O(log n) no matter the properties of the inputs; however, the randomness of the insertions, simulate a near balanced tree that acts almost as efficient as the AVL. Therefore, to access and delete nodes in the BST it doesn’t have to make N iterations to find the node of interest as it had to in the previous two cases. !Graph 2.1Graph 2.2Graph 2.3Logan Ortega!3 !!!!!!!!!!!!!!!!!!!!!CONCLUSION!The AVL’s self-balancing rotations ensure the efficiency of accesses, deletions and further insertions. The BST has no such properties that ensure its efficiency. As we have seen in the three cases above, the BST can be nearly as efficient as the AVL if the initial insertions are made in a optimal manner. For this reason, we can say that the BST’s efficiency is dependent on the properties of the elements it contains, while the AVL is independent of such details. Graph 3.1Graph 3.2Graph