×

### Let's log you in.

or

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

×

or

14

0

26

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

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

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
26
WORDS
KARMA
25 ?

## Popular in Department

This 26 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 14 views.

×

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

×

×

### 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 25 April 03 2002 Announcements Next time finish chapter 9 section 2 Project 4 is due either April 04 by 1159p or in class April 05 Project 5 will be out on Friday No class on Friday April 12 Spring 2002 CS 357 Class Notes Page 2 Binary Search Tree A binary search tree is a binary tree used to implement a dictionary Each node stores a keyelement pair of a dictionary For any node v keys stored at nodes in the left subtree of v are less than or equal to the key stored at v For any node v keys stored at nodes in the right subtree of v are greater than or equal to the key stored at v Spring 2002 CS 357 Class Notes Page 3 Searching Beginning at the root determine how the key in question relates to the key of the current node If it is equal to the current key terminate successfully If it is less than the current key continue with the left child of the current node or terminate unsuccessfully if one does not exist Otherwise continue with the right child of the current node or terminate unsuccessfully if one does not exist Spring 2002 CS 357 Class Notes Page z Recursiver Speaking Algorithm TreeSearchkv if v null then return v if k keyv then return v else if k lt keyv then return TreeSearchkeftChidv else return TreeSearchkrightChiIdv What order is this algorithm Specifically How good could it be How bad Spring 2002 CS 357 Class Notes Page 5 Quick Quiz What nodes are traversed to find key 76 9 6 Spring 2002 CS 357 Class Notes Quick Answer 88a65a82a76 Spring 2002 CS 357 Class Notes Inserting Traverse the tree in the same manner as the search algorithm If the key is found continue the traversal to the right or equivalently to the left Must be consistent with the direction choice If the child to be traversed does not exist insert the keyelement pair in a new node at that location Spring 2002 CS 357 Class Notes Page E Recursiver Speaking Algorithm Treelnsertxv if v null then return x if keyx s keyv then eftChidv TreelnsertxeftChidv else rightChiIdv TreelnsertxrightChidv return v Spring 2002 CS 357 Class Notes page E Quick Quiz What nodes are traversed to insert key 84 Where is the key inserted 6 Spring 2002 CS 357 Class Notes Page 1 Quick Answer 88 a 65 a 82 6 9 Spring 2002 CS 357 Class Notes Page 1 Removal Easy The node to be removed is external Simply remove the node setting the child pointer to null Not so easy The node is internal Find the node y such that y immediately follows this node in an inorder traversal Replace this node s keyelement pair with that of y eplace the child pointer to ywith ys right subtree What about y s left subtree Spring 2002 CS 357 Class Notes Page 12 Quick Quiz Easy Version What nodes are traversed to remove key 80 What is the resulting tree Spring 2002 CS 357 Class Notes Quick Answer 88a65a82a76a80 Spring 2002 CS 357 Class Notes Quick Quiz Harder Version What nodes are traversed to remove key 65 What is the resulting tree Spring 2002 CS 357 Class Notes Quick Answer 88a65a82a76 66 ac ac e we Spring 2002 CS 357 Class Notes Page 16 Dictionary Performance insertltem Oh removeEIement Oh findEIement Oh removeAIIEIements Oh s findAIIEIements Oh s h is expected to be log n Spring 2002 CS 357 Class Notes Page 17 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 Spring 2002 CS 357 Class Notes Page 15 Inserting Troubles Below you are given an AVL tree Insert 80 into the following tree Is this still a balanced AVL tree Spring 2002 CS 357 Class Notes page 1g Restructuring Algorithm restructurex Input A node x of a binary search tree that has both a parent y and a grandparent z 1 Let abc be an inorder listing of xyz and T0T1T2T3 be an inorder listing of the four subtrees of x y and 2 not rooted at x y or z 2 Replace the subtree rooted at z with a new subtree rooted at b 3 Let a be the left child of b and let T0 and T1 be the left and right subtrees of a respectively 4 Let c be the right child of b and let T2 and T3 be the left and right subtrees of c respectively Spring 2002 CS 357 Class Notes Page 2 Single Rotation When by a single rotation occurs What s wrong with this one Spring 2002 CS 357 Class Notes Page 2 Double Rotation When bx a double rotation is performed Meaning x is rotated over y and then over 2 What s wrong with this one Spring 2002 CS 357 Class Notes Page 22 AVL Insertion Restructuring The same restructuring algorithm works for single and double rotations For insertions Let 2 be the first unbalanced node encountered going up from the inserted node Let y be the child of z with higher height that is also an ancestor of the inserted node Let x be the child ofy with higher height On a tie choose x to be an ancestor of the inserted node Spring 2002 CS 357 Class Notes Page 23 Quick Quiz What are x y and z What are T0 T1 T2 and T3 What are a b and c What happens on rotation 66 Spring 2002 CS 357 Class Notes Page 24 Quick Answer Spring 2002 CS 357 Class Notes Visually Appealing httpwwwcgccsjhuedujkosshtmsstructuresindexhtml Spring 2002 CS 357 Class Notes Page 26

×

×

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

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."

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!"

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!"

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