Logan Ortega 1 CMPSC 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 1 Graph 1 2 Graph 1 3 Logan 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 ef ciency 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 nd the node of interest Graph 2 1 Graph 2 2 Graph 2 3 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 ef cient as the AVL Therefore to access and delete nodes in the BST it doesn t have to make N iterations to nd the node of interest as it had to in the previous two cases Logan Ortega 3 Graph 3 1 Graph 3 2 Graph 3 3 CONCLUSION The AVL s self balancing rotations ensure the ef ciency of accesses deletions and further insertions The BST has no such properties that ensure its ef ciency As we have seen in the three cases above the BST can be nearly as ef cient as the AVL if the initial insertions are made in a optimal manner For this reason we can say that the BST s ef ciency is dependent on the properties of the elements it contains while the AVL is independent of such details