### Create a StudySoup account

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

Already have a StudySoup account? Login here

# INTRODUCTION TO ALGORITHMS CSCI 2300

RPI

GPA 3.63

### View Full Document

## 25

## 0

## Popular in Course

## Popular in ComputerScienence

This 10 page Class Notes was uploaded by Ransom Blanda on Monday October 19, 2015. The Class Notes belongs to CSCI 2300 at Rensselaer Polytechnic Institute taught by Staff in Fall. Since its upload, it has received 25 views. For similar materials see /class/224863/csci-2300-rensselaer-polytechnic-institute in ComputerScienence at Rensselaer Polytechnic Institute.

## Reviews for INTRODUCTION TO ALGORITHMS

### 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: 10/19/15

CSci 2300 7 Data Structures and Algorithms Week 7 Class 13 7 February 23 2001 AVL Trees 7 Balanced Binary Search Trees Test 1 7 General Comments 0 Average 772 There was no curve 0 Remember if this is your lowest test grade of the semester it will only count 5 toward your overall grade 0 Questions about grading 7 Argue only correctness issues not about point assignments 7 Refer all questions about correctness to me 0 We will go over solutions in class Solutions will also be posted on the web Review from Class 12 o Binary search tree de nitions 0 Binary search tree class overview 0 Core algorithms insert nd and remove 0 Copying and destroying Binary Search Trees 7 Analysis 0 Analysis is done in terms of the number of nodes N stored in the tree 0 The key consideration is the height of the root 0 The worstcase for the unbalanced implementation is 0N o BSTs can become lopsided quite easily since input is often nearly or dere o The averagecase height of a BST is Olog N 7 This assumes a randomordering of the nodes inserted into the tree 7 This implies the cost of insert remove and nd are each Olog N 7 We will derive this result in class using the notion of an internal path length Balanced Trees 7 Overview 0 Three classic data structures exist for maintaining balance in trees 7 AVL trees and Redblack trees guarantee that the height of the tree is Olog N7 while doing Olog N work for each insert7 remove or nd operation 7 Splay trees guarantee that any sequence of N operations will require ON log N work in total 0 We will study AVL trees and splay trees 0 STL uses Redblack trees7 but these are the hardest to implement AVL Trees 7 Introduction An AVL tree is a binary search tree such that at each internal node7 the differ ence in height between the left and right subtrees is 1 0 or ll We will call this property the AVL property 0 Insert and remove operations on AVL trees maintain the AVL property through operations called rotations o Rotations must preserve the ordering property at all times 0 AVL trees containing N nodes have Olog N heightl ln fact7 the worst case is about 144 log AVL Trees 7 Insert 0 The insert algorithm is designed based on the assumption that the tree has the AVL property before insert begins 0 Insert works exactly as in ordinary BST s until after a new node is inserted 0 As the recursion of the insert function unwinds7 each node is checked to make sure the AVL height difference property holds 0 At the rst node for which NodeIIt tgt1eft NodeI It tgtright NodeIIt tgtright NodeIIt tgt1eft a rotation must occur Rotations to Fix Insert Imbalance Let t be the pointer to the node at Which the imbalance is detected There are exactly four possibilities ll NodeJIttgt1eft gt NodeJIttgtright AND NodeHttgt1eftgt1eft gt NodeJIt tgt1eftgtright 2i NodeJIttgt1eft gt NodeJIttgtright AND NodeJIttgt1eftgt1eft lt NodeJIt tgt1eftgtright 3i NodeJIttgt1eft lt NodeJIttgtright AND NodeHttgtrightgt1eft gt NodeHttgtrightgtright 4i NodeJIttgt1eft lt NodeJIttgtright AND NodeJIttgtrightgt1eft lt NodeJIttgtrightgtright Recall that the height of a null node is ll Also7 think about Where the insert took place in each case These imbalances are xed as follows 1 Single rotation from left 2 Double rotation from left 3 Double rotation from right 4 Single rotation from right We7ll start With single rotations A drawing for single and double rotations Will be distributed separatelyl Single Rotation From Left Rotate t With tgt1eft BSNodeltComparab1egt k1 tgt1eft tgt1eft k1gtright k1gtright t tgtheight 1 Max NodeIIt tgt1eft NodeIIt tgtright k1gtheight 1 Max NodeIIt k1gt1eft NodeIIt k1gtright t k1 Single Rotation From Right Rotate t With tgtright BSNodeltComparab1egt k1 tgtright tgtright k1gt1eft k1gt1eft tgtheight 1 Max NodeIIt tgt1eft NodeIIt tgtright k1gtheight 1 Max NodeIIt k1gt1eft NodeIIt k1gtright t k1 d Double Rotation From Left 0 Do a single rotation from right between tgt1eft and tgt1eftgtrightl 0 Then do a single rotation from left between t and the new tgt1eftl This has the effect of moving what was at tgt1eftgtright to t s positionl Double Rotation From Right 0 Do a single rotation from left between tgtright and tgtrightgt1eftl 0 Then do a single rotation from right between t and the new tgtrightl This has the effect of moving what was at tgtrightgt1eft to t s positionl Insertion Notes 0 An imbalance can only be discovered at one node after insertion After the imbalance is xed7 no more rotations can occur for the same insert operation 0 The running time of insert is Olog Nl Software 0 The AVL tree code is part of the BSTree class distributed with the Class 12 notes 0 A simple simulation program will be used in class to help visualize the effect of Insert and Remove and rotations on AVL trees The source code will be available on the we i o A simple comparison program will also be used to demonstrate the differ ence between ordinary BST s and AVL trees on random and on ordered inputi AVL Trees 7 Remove 0 The remove algorithm is designed based on the assumption that the tree has the AVL property before remove begins 0 Remove works exactly the same as ordinary BST s until after a node has been actually removed from the tree 0 As the recursion of the Remove function unvvinds7 each node is checked to make sure the AVL height difference property holds 0 At each node for Which NodeIIt tgt1eft NodeI It tgtright NodeIIt tgtright NodeIIt tgt1eft a rotation must occur Rotations to Fix Remove Imbalances Let t be the pointer to the node at Which the imbalance is detected There are exactly four possibilities and these are only slightly different from those of Insert 1 NodeJIttgt1eft gt NodeJIttgtright AND NodeHttgt1eftgt1eft gt NodeHttgt1eftgtright E0 NodeJIttgt1eft gt NodeJIttgtright AND NodeJIttgt1eftgt1eft lt NodeJIt tgt1eftgtright 9 NodeHttgt1eft lt NodeHttgtright AND NodeHttgtrightgt1eft gt NodeHttgtrightgtright F NodeJIttgt1eft lt NodeJIttgtright AND NodeJIttgtrightgt1eft lt NodeJIt tgtrightgtright They are xed as follows 1 Single rotation from left 2 Double rotation from left 3 Double rotation from right 4 Single rotation from right Notes on Fixing Remove Imbalances o If the node removed was in the left subtree7 the rotation comes from the right If the node removed was in the right subtree7 the rotation comes from the left Insert is the opposite o Rotations can occur at several nodes7 but the overall work is still Olog N timer Exercises 1 10 points Show the contents of an AVL tree at the end of each of the following sequences of operations a lnsert20 lnsert30 lnsert40 b lnsert35 lnsert37 lnsert36 c lnsert10 lnsert29 Remove35 d Remove 36 Remove 40 2 10 points Find an example AVL tree such that removing a single spe ci c value from the tree causes rebalancing to occur starting at two dif ferent nodes 3 Read Section 45 NGLE mmon mm LEFT Nue mgtku gt magma A Mm m gtIz gtlrjn N54511quot gt ND Hr er oouaLs mum mm LEFT mamgt74 gt Mun ugh1 AND may gt15 rgtIr lt Ivme gt14 mm v Dnzvftcmd vaH May mm awn1 Academic Integrity Agreement Students can learn a great deal by collaborating but not by copying Getting help is often the best way to interpret error messages and nd bugs even for experienced programmers Thus in order to encourage collaboration but not copying the following rules will be strictly enforced Students may work together in designing algorithms in interpreting error messages in discussing strategies for nding bugs but NOT in writing code No records may be taken away from any discussion for example written or otherwise Students may not share code or copy code from anyone This policy extends up to two days after the submission deadline Students may not show the work code or theory to anyone until two days after the submission deadline Students may not look at anyone s work code or theory in preparation for or while doing an assignment Students may not leave their work electronic or printed versions in publically accessible areas Students may not share personal computers or computer accounts in any way when there is an assignment pending Students may discuss solutions to theory problems unless the problem explicitly states that discus sion is not allowed Such discussion is allowed up to 2 days before the due deadline No records may be taken away from any discussion Any written work handed in cannot be copied from anywhere other than the text book or class notes This includes the WWW All solutions handed in must be written by you If either in the theory or in the coding some collaboration occurred you MUST at the end of your assignment for theory parts and in the README le for coding parts state who you discussed with and what the nature of the discussion was A violation of Academic Integrity will almost certainly result in an F for students who do not own up For students who do own up a zero on that assignment and a 5 decrease in the overall grade will be enforced the rst time The second time will result in an F All such incidents are also reported to the Dean of Students and will become part of your permanent record By signing below you af rm that you have read and understood this agreement Signature Date Full Name RID Number Academic Integrity Agreement YOUR COPY Students can learn a great deal by collaborating but not by copying Getting help is often the best way to interpret error messages and nd bugs even for experienced programmers Thus in order to encourage collaboration but not copying the following rules will be strictly enforced Students may work together in designing algorithms in interpreting error messages in discussing strategies for nding bugs but NOT in writing code No records may be taken away from any discussion for example written or otherwise Students may not share code or copy code from anyone This policy extends up to two days after the submission deadline Students may not show the work code or theory to anyone until two days after the submission deadline Students may not look at anyone s work code or theory in preparation for or while doing an assignment Students may not leave their work electronic or printed versions in publically accessible areas Students may not share personal computers or computer accounts in any way when there is an assignment pending Students may discuss solutions to theory problems unless the problem explicitly states that discus sion is not allowed Such discussion is allowed up to 2 days before the due deadline No records may be taken away from any discussion Any written work handed in cannot be copied from anywhere other than the text book or class notes This includes the WWW All solutions handed in must be written by you If either in the theory or in the coding some collaboration occurred you MUST at the end of your assignment for theory parts and in the README le for coding parts state who you discussed with and what the nature of the discussion was A violation of Academic Integrity will almost certainly result in an F for students who do not own up For students who do own up a zero on that assignment and a 5 decrease in the overall grade will be enforced the rst time The second time will result in an F All such incidents are also reported to the Dean of Students and will become part of your permanent record By signing below you af rm that you have read and understood this agreement Signature Date Full Name RID Number For Your Information Code is compared within sections across sections and across years We use sophisticated automatic code comparison tools to help spot assignments that have been submitted in Violation of the rules I then follow up by looking at the code carefully Last semester 20 students were penalized mostly with an F in the class If you did Violate the rules the rst time you will be given a chance to own up In this unfortunate circumstance I strongly urge you to own up When the message goes out that some people have Violated the rules assume that you have been caught The result of not owning up is an F at the minimum Some of the work in this class is tough and designed so that it can confuse you at the begining The odds are that other students are also confused so when you bang your head on a problem a little and nd you are getting nowhere I suggest you rst seek help from the TA s or myself to set you on the right path conceptually Note however that the TA s are not there to debug your programs and l have explicitly instructed them that debugging is not their task it is your task

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

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

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I 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."

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