CS130A: AVL & BST Analysis
CS130A: AVL & BST Analysis
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 3 page Test Prep (MCAT, SAT...) was uploaded by logeybearrr on Saturday June 7, 2014. The Test Prep (MCAT, SAT...) belongs to a course at University of California Santa Barbara taught by a professor in Fall. Since its upload, it has received 61 views.
Reviews for CS130A: AVL & BST Analysis
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 06/07/14
Logan Ortega 1 CMPSC 130A PA2 Adelson Velslltii and Landis Tree amp 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 eft 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 11 through 13 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 Olog N while the BST runs in ON However the delete operation runs in Olog 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 13 mcreasing msert Increasing Access 3 N 04 035 0 us be II 025 C O 0391 AVL 0AVL 015 0 4 QBST 9BST Processing Time s 0 0 II IJ Processing Time s 0 ix 005 l 12345678910 12345678910 Sample Size in thousands Sample Size in thousands Increasing Delete 0 Lu 0 N 11 0 N 1 O S GAVL 0 00 U39III D39BST Processing Time s O 1 2 3 4 5 6 7 8 9 10 Sample Size in thousands 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 21 through 23 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 Oog N for the AVL however in this case all three operations run in ON for the BST Just like before the AVL s rotations allow it to only traverse ceiog 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 Increasing Insert Decreasing Access 0 D 3quot gtN 035 Time s O 0 is 0 lJ U1 U0 on be 9AVL 9AVL Processing 0 l U 9BST Q l WBST Processing Time s 0 0 0 O D 005 0 ON 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Sample Size in thousands Sample Size in thousands Decreasing Delete 04 035 0 us 025 TAVL 015 Processing Time s O N D BST 0 i 005 1 2 3 4 5 6 7 8 9 10 Sample Size in thousands 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 31 through 33 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 Oog N The rotations of the AVL guarantee its operations run in Olog 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 Logan Ortega Random Insert Random Access 0 16 018 014 016 E 012 E 014 Q s 01 012 quot 01 2 0 08 E 39 3 0AVL 5 008 WAVL 006 0 06 o EBsf 39 9 004 2 004 B 002 002 0 0 12345678910 12345673910 Sample Size in thousands Sample Size in thousands Random Delete 009 008 E 007 G E 006 39 005 004 aAVL 003 iiBsT o 002 001 1 2 3 4 5 6 7 8 9 10 Sample Size in thousands CONCLUSION The AVL s selfbalancing 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