### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# CS 332 CS 332

UVA

GPA 3.71

### View Full Document

## 16

## 0

## Popular in Course

## Popular in ComputerScienence

This 24 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 332 at University of Virginia taught by David Luebke in Fall. Since its upload, it has received 16 views. For similar materials see /class/209679/cs-332-university-of-virginia in ComputerScienence at University of Virginia.

## Popular in ComputerScienence

## Reviews for CS 332

### What is Karma?

#### Karma is the currency of StudySoup.

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

Date Created: 09/21/15

CS 332 Algorithms Go over exam Binary Search Trees Davi ddddd ke Exam a Hand back go over exam David Luebke 2 7262007 Review Dynamic Sets 0 Next few lectures will focus on data structures rather than straight algorithms 0 In particular structures for dynamic sets I Elements have a key and satellite data I Dynamic sets support queries such as o SearchS k MinimumS MaximumS Success0rS x Predecess0rS x I They may also support modifying operations like 0 InsertS x DeleteS x David Luebke 3 7262007 Review Binary Search Trees o Binary Search Trees BSTS are an important data structure for dynamic sets 0 In addition to satellite data eleements have I key an identifying eld inducing a total ordering I left pointer to a left child may be NULL I right pointer to a right child may be NULL I p pointer to a parent node NULL for root David Luebke 4 7262007 Review Binary Search Trees 0 BST property key eftSubtree x Skeyx SkeyrightSubtree x 0 Example Davi ddddd ke Inorder Tree Walk o What does the following code d0 TreeWalkx TreeWalkleftx printx TreeWalkrightx o A prints elements in sorted increasing order 0 This is called an inorder tree walk I Preora er tree walk print root then left then right I Postora er tree walk print left then right then root David Luebke 6 7262007 Inorder Tree Walk 0 Example o How long will a tree walk take 0 Prove that inora er walk prints in monotonically increasing order Davi ddddd ke Operations on BSTs Search 0 Given a key and a pointer to a node returns an element with that key or NULL TreeSearchx k if x NULL or k keyx return x if k lt keyx return TreeSearchleftx k else return TreeSearchrightx k David Luebke 8 7262007 BST Search Example 0 Search for D and C Davi ddddd ke Operations on BSTs Search 0 Here s another function that does the same TreeSearchx k while x NULL if k lt X and k keyx keyx leftx else x rightx return x 0 Which of these two functions is more e ciem David Luebke 10 7262007 Operations of BSTs Insert o Adds an element X to the tree so that the binary search tree property continues to hold 0 The basic algorithm I Like the search procedure above I Insert X in place of NULL I Use a trailing pointer to keep track of Where you came from like inserting into singly linked list David Luebke 11 7262007 BST Insert Example 0 Example Insert C Davi ddddd ke BST SearchInsert Running Time o What is the running time of T reeSearchO or T reelhsertO o A Oh where h height of tree 0 What is the height of a binary search tree 0 A worst case h 0a when tree is just a linear string of left or right Children I We ll keep all analysis in terms of h for now I Later we ll see how to maintain h Olg n Davi ddddd ke Sorting With Binary Search Trees o Informal code for sorting array A of length n BSTSortA for i1 to n TreeInsertAi InorderTreewalkroot o Argue that this is 201 lg n o What will be the running time in the llewtame lxhwwagecawehh ren ndmntqfahy ng2 David Luebke 14 7262007 Sorting With BSTs 0 Average case analysis for i1 to n TreeInsert Ai l It s a fOI39IIl Of qUICkSOFt InorderTreeWalk root a David Luebke 15 7262007 Sorting with BSTs 0 Same partitions are done as with quicksort but in a different order I In previous example 0 Everything was compared to 3 once 0 Then those items lt 3 were compared to 1 once 0 Etc I Same comparisons as quicksort different order 0 Example consider inserting 5 David Luebke 16 7262007 Sorting with BSTs 0 Since run time is proportional to the number of comparisons same time as quieksort On lg n 0 Which do you think is better quicksort 0r BSTsort Why Davi ddddd ke Sorting with BSTs 0 Since run time is proportional to the number of comparisons same time as quicksort On lg n 0 Which do you think is better quicksort 0r BSTSort Why 0 A quicksort I Better constants I Sorts in place I Doesn t need to build data structure David Luebke 18 7262007 More BST Operations o BSTs are good for more than sorting For example can implement a priority queue o What Operations must a priority queue have I Insert I Minimum I ExtractMin David Luebke 19 7262007 BST Operations Minimum 0 HOW can we implement a Minimum query a What is the running time 72 2007 BST Operations Successor o For deletion we will need a Suooessor operation 0 Draw Fig 132 o What is the successor of node 3 Node 5 Node 3 o What are the general rules for nding the successor of node x hint two cases Davi ddddd ke BST Operations Successor 0 Two cases I X has a right subtree successor is minimum node in right subtree I X has no right subtree successor is rst ancestor of X Whose left child is also ancestor of X o Intuition As long as you move to the left up the tree you re Visiting smaller nodes 0 Predecessor similar algorithm David Luebke 22 7262007 BST Operations Delete o Deletion is a bit tricky o 3 cases I X has no children 0 Remove X I X has one child Example delete K o Spl1ce outX or H or B I X has two children 0 Swap X with successor 0 Perform case 1 or 2 to delete it David Luebke 23 7262007 BST Operations Delete 0 Why will case 2 always go to case 0 or case 1 o A because when X has 2 Children its successor is the minimum in its right subtree 0 Could we swap x with predecessor instead of successor o A yes Would it be a good idea 0 A might be good to alternate Davi ddddd ke

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

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

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

#### "I made $350 in just two days after posting my first study guide."

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

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

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

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.