×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: logeybearrr

61

0

3

# CS130A: AVL & BST Analysis

logeybearrr
UCSB
GPA 3.75

Koc

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

Detailed analysis and comparison of AVLs and BSTs written in plain English.
COURSE
PROF.
Koc
TYPE
Test Prep (MCAT, SAT...)
PAGES
3
WORDS
CONCEPTS
Computer Science, CS, CMPSC, 130A
KARMA
75 ?

## 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

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

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

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Jennifer McGill UCSF Med School

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over \$500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Bentley McCaw University of Florida

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com