×

### Let's log you in.

or

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

×

or

17

0

7

# Class Note for CS 357 at UA-Data Structures (13)

Marketplace > University of Alabama - Tuscaloosa > Class Note for CS 357 at UA Data Structures 13

No professor available

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

COURSE
PROF.
No professor available
TYPE
Class Notes
PAGES
7
WORDS
KARMA
25 ?

## Popular in Department

This 7 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Alabama - Tuscaloosa taught by a professor in Fall. Since its upload, it has received 17 views.

×

## Reviews for Class Note for CS 357 at UA-Data Structures (13)

×

×

### 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: 02/06/15
CS 357 Data Structures Class 26 April 05 2002 Announcements Next time chapter 9 sections 3 amp 4 Project 4 is due today in class Project 5 will be out today No class next Friday April 12 Honor s Day zmzcsssiazssnms M2 AVL Trees An AVL tree is a binary search tree that satisfies the heightbalance property For every internal node the heights of its children can differ by at most 1 ensuring the height is log n Is this an AVL tree zmzcsssiazssnms mg Inserting Troubles Below you are given an AVL tree Insert 80 into the following tree Is this still a balanced AVL tree ignwzmzcssmchssnms ned Restructuring Algorithm restructurex both a parent y and a grandparent z 1 Let abc be an inorder Ii of x y and 2 not rooted at x y or z rooted at b and right subtrees of a respectively left and right subtrees of c respectively Input A node x of a binary search tree that has 39 9 0f XII1 and TnT1T2T3 be an inorder listing of the four subtrees Replace the subtree rooted at z with a new subtree Let a be the left child of b and let TH and T1 be the left Let c be the right child of b and let T2 and T3 be the ignwzmzcssmchssnms Single Rotation When by a single rotation occurs What s wron g with this one ignwzmzcssmchssnms Double Rotation When bx a double rotation is performed Meaning x is rotated over y and then over 2 What s wron g with this on e ignwzmzcssmchssnms AVL Insertion Restructuring The same restructuring algorithm works for single and double rotations For insertions Let 2 be the rst unbalanced node encountered going up from the inserted node Let y be the child ofz with higher height that is also an ancestor of the inserted node Let x be the child ofywith higher height On a tie choose x to be an ancestor of the inserted node ignwzmzcssmchssnms Quick Quiz What are x y and z What are TD T1 T2 and T3 What are a b and c What happens on rotation 69 99 ignwzmzcssmchssnms My Quick Answer Mzmzcssmazssnms New Removal Troubles Removal is the same as Binary Search Trees Below you are given an AVL tree Remove 97 from the following tree Is this still a balanced AVL tree 90 0 69 69 ignwzmzcssmchssms men Removal Restructuring The same restructuring algorithm is used as that for insertions For removals Let 2 be the rst unbalanced node encountered going up from the removed node Let y be the child ofz with higher height that is NOT an ancestor of the removed node Let x be the child ofywith higher height Must continue up the tree after restructuring looking for additional unbalanced nodes Mzmzcssmazssnms men Quick Quiz What are x y and z What are T T1 T2 and T3 What are a b and c What happens on rota ion a 99 Sgnvw2m2cs357cizssnms Consider restructuring the AVL tree given below Quick Answer Sgnvw2m2cs357cizssnms NotSoQuick Quiz Remove 100 from the following AVL Tree Sgnvw2m2cs357cizssnms NotSoQuick Answer Part Remove 100 from the following AVL Tree ignwzmzcssmchssnms NotSoQuick Answer Part II Remove 100 from the following AVL Tree ignwzmzcssmchssnms AVL Dictionary Performance ndEIement Oog n insertEIement Oog n removeEIement Oog n ndAIIElements Oog n s removeAlIEIements Oog n s Note this is NOT expected It is guaranteed ignwzmzcssmchssnms Visually Appealing httpwwwcgccsjhueduljklosshtmlsstructures ndexhtml Play with adding and removing Is there a problem with the remove s 2m2csss7cizssnms New

×

×

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

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Kyle Maynard Purdue

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made \$280 on my first study guide!"

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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