### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithms and Data Structures CS 2420

Utah State University

GPA 3.85

### View Full Document

## 19

## 0

## Popular in Course

## Popular in ComputerScienence

This 11 page Class Notes was uploaded by Reed Aufderhar on Wednesday October 28, 2015. The Class Notes belongs to CS 2420 at Utah State University taught by Vicki Allan in Fall. Since its upload, it has received 19 views. For similar materials see /class/230446/cs-2420-utah-state-university in ComputerScienence at Utah State University.

## Reviews for Algorithms and Data Structures

### 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/28/15

Chapter 4 Binary Search Trees Binary Search Trees 0 De nition 0 All keys are distinct 7 why 0 Key in the root ofthe le subtree is less than the root 0 Key in the root of the right subtree is greater than the root 0 Left and right subtrees are binary search trees 0 Figure l is an example Figure 1 Binary Search Tree Where would you add X B and E At seats build tree from the nodes B R L M T C A N P D o What about deletion 0 Since it is easier to delete from a leaf we rst replace the node with its inorder successor and then delete the node that contained the inorder succes The code for insertion is as follows I like to create the new node outside the insert routine Binary Search Tree lnclude lt1OStreamgt uslng namespace std template ltclass Etypegt class TreeNode public Etype element TreeNode left TreeNode rlght TreeNode Etype e O TreeNode l NULL element e left l TreeNode r NULL rlght r l l template ltclass Etypegt Binary Search Trees Page 1 class BinarySearchTree protected TreeNodeltEtypegt root void makeEmpty TreeNodeltEtypegt amp t TreeNodeltEtypegt amp t TreeNodeltEtypegt t const bool insertEtype amp x Etype find const Etype amp x void printTree TreeNodeltEtypegt t string indent public BinarySearchTree root NULL void makeEmpty makeEmpty root void printTreestring msg const cout ltlt msg ltlt endl printTree rootquotquot return find x root const Etype amp x root virtual Etype find return insert x virtual int insertEtype amp x template ltclass Etypegt void BinarySearchTreeltEtypegtzz printTree TreeNodeltEtypegt tstring indent const if tNULL return printTreet gtright indentquot cout ltlt indent ltlt t gtelement ltlt endl printTreet gtleft indentquot quot quotgt r Return true if insertion is successful template ltclass Etypegt bool BinarySearchTreeltEtypegtzz insertEtype amp x TreeNodeltEtypegt amp t if t NULL t new TreeNodeltEtypegt x if t NULL return false return true if x lt t gtelement return insert x t gtleft if x gt t gtelement return insert x t gtright cout ltlt quotWarning duplicate ignored quot ltlt x ltlt endl return false does not allow duplicate insertions template ltclass Etypegt Etype BinarySearchTreeltEtypegtzz find const Etype amp x TreeNodeltEtypegt t if t NULL return NULL if x lt t gtelement return find x t gtleft L return find x t gtright if x gt t gtelement return ampt gtelement Page 2 Binary Search Trees template ltclass Etypegt void BinarySearchTreeltEtypegtzz makeEmpty TreeNodeltEtypegt amp t I if t l NULL makeEmpty t gtleft makeEmpty t gtright delete t t NULL 0 Operations 0 Search 7 Oh where h is the height ofthe tree In the best case balanced h is logn In the worst case h is n the number of nodes in the tree 0 Insert 7 Oh where h is the height ofthe tree 0 Delete 7 Oh where h is the height of the tree I What makes deletion dif cult Balanced Trees 0 Binary search trees are a good technique for nding elements in a dictionary 0 But it has a disadvantage o In the worst case the operations are still On 0 There are applications that are time critical and this amount of time is not acceptable 0 We will consider balanced trees AVL redblack and AA trees where the worst case operation is Ologn 0 Go over recursion handout showing trace of recursion AVL Trees Balanced tree 7 the height of left subtree and height of right subtree differ by at most one o AVL trees are height balanced trees 0 The name comes from the people that came up with the idea 7 AdelsonVelskii and Landis 0 De nition 0 An empty binary tree is an AVL tree 0 If T is a nonempty binary tree with TL and TR as its left and right subtrees then T is an AVL tree iff I TL and TR are AVL trees and I hL hR S1 where h and me are the heights of TL and TR respectively For several examples determine if AVL or not How bad can a tree be and still be AVL AnAVL search tree is a binary search tree that is also an AVL tree See Figure 2 for some possible examples For each tree Binary Search Trees Page 3 o Is it an AVL tree 0 Is it an AVL search tree 20 so 60 30 15 25 5 an 70 5 40 12 10 22 2 65 80 2 50 a 1b 5 d Figure 2 Possible AVL Trees and AVL Search Trees 0 Properties of AVL trees 0 The height of an AVL tree with n elementsnode is Ologn o For every value ofn n 2 0 there exists an AVL tree 0 An nelement AVL search tree can be searched in Oheight Ologn time o A new element can be inserted into an nelement AVL search tree so that the result is an n1 element AVL tree and such an insertion canbe done in Ologn time 0 An element can be deleted from an nelement AVL search tree so that the result is an n71 element AVL tree and such a deletion can be done in Ologn time From here on out when I refer to anAVL tree I mean an AVL search tree The bound in the height of an AVL tree can be shown by the recursive routine shown below 0 worsttree h Worst tree of height h l 0 root left worsttreeh1 0 root right worsttreeh2 Searching 0 How is this done Same way as with the binary search tree Insertion Insertions 7 just like BST nd the leaf where the node needs to go A er that node is placed in the AVL tree the tree is rebalanced if necessary We need to have a balance factor associated with each node x in the AVL tree height ofleft subtree ofx 7 height ofright subtree ofx See Figure 3 for an example of inserting 32 into an AVL tree and the subsequent rebalancing Notice that the balance factor is contained in each of the nodes shown in the Binary Search Trees Page 4 a onginai Tree b Mar 32 rs Insaned c Following Rebaiancrng gure 3 Example of Inserting into an AVIrTree Observations about the unbalanced tree that results from an insertion the unbalanced tree the balance factors are lirnitedto 72 71 0 1 and 2 o A node with balance factor 2 has a balance factor of 1 before the insertion Similarly a node with balance factor 72 has a balance factor of 71 before the insertion The balance factors of only those nodes on the path from the root to the newly inserted node can change as a result of the insertion LetA denote the nearest ancestor of the newly inserted node whose balance factor is either 72 or 2 The balance factor of all nodes on the path fromA to the newly inserted node was 0 prior to the insertion In Figure 3b what isA Node 40 There are four cases have to be consider when inserting into an AVL tree We categorize these starting from A o Inserted node is in the le subtree ofA New node is a le subtree of the le subtree of A 7 call LL rotation I New node is a right subtree of the left subtree of A 7 called LR rotation o Inserted node is in the right subtree of A New node is a le subtree of the right subtree of A 7 call RL rotation New node is a right subtree of the right subtree of A 7 called RR rotation The RR and RL rotations are symmetric to the LL and LR so we don t need to discuss them A generic LL type imbalance appears in Figure 4 O O A 5 AR 7 539L BR h h m1 7 n h a Before Insertion b After Inserting rme aL c Aner LL Rotation gure 4 LL Rotation Binary Search Trees Page 5 o A generic LR type imbalance appears in Figure 5 c B A BL CL CR AR h n a After LR Rulalion a Beiore lnsemon b After Inserting inlo 8 gure 5 LR Rotation The balance factor b in the tree is de ned below b 0 5 bfB bfA 0 a er rotation b l 5 bfB 0 and bfA 71 a er rotation b 71 bfB l and bfA 0 a er rotation The complexity of insertion into an AVL tree is Oheight Olog n Notice that a single rotation is su icient to restore balance the insertion causes imbalance Consider the tree in Figure 6 o 70 0 Insert 22 gure 6 AVL Insertion Try inserting the following state abbreviations into an AVL tree RI PA DE GA OH MA IL MI IN NY VT TX WY The resulting tree is shown in Figure 7 AVL tree with States Binary Search Trees Page 6 gure 7 AVL tree with states Deletion Deletions Replace With inorder successor delete and rebalance An R0 imbalance at A is recti ed by performing the rotation shown in Figure 8 A A B AR B A s h h1 BL BR Bl 57 n n h n h h 1 a Before Deletion o After Deleting from AR c After R0 Rotation gure 8 R0 Rotation Figure 9 shows how to handle an R1 imbalance B AR B A h h1 BL BR BL BR BR AIR h h1 n h1 h1 71 a Before Deletion o After Deleting from AR 0 After R1 Rotation gure 9 R1 Rotation Binary Search Trees Page 7 0 Following an R1 rotation we must continue to examine nodes on the path to the root Unlike the ease of an insertion one rotation may not su iee to restore balance following a deletion The number ofrotations needed is Ologn The transformation needed When the imbalance is of type R71 appears in Figure 10 aL c EL 0 2R A39R n 1 m m lt3L cR a Belore Deletion b After Deleting ram AR 0 A er R4 Rotation gure 10 R71 Rotation Rl rotations may possibly need to continue to the root See the LR rotation for the de nition of b What happens if AVL property is extended so le and right differ by 2 or 3 or K o Termed height balanced tree HB As K increases worst case height increases but time to rebalance is less 0 There are symmetric rotations Consider the tree shown in Figure 11 We want to delete node 60 gure 11 Delete node 60 0 Consider the tree shown in Figure 12 We want to delete node 70 Binary Search Trees Page 8 Figure 12 Delete node 70 Rotations LL and R1 rotations are identical 0 LL and R0 rotations differ only in the nal balance factors 0 LR and R71 rotations are identical Binary Search Trees Page 9 Splay Trees Splay trees support all the operations of binary trees But they do not guarantee OlogN worstcase performance Instead its bounds are amortized meaning that although individual operations can be expensive any sequence of operations is guaranteed to behave as if each operation in the sequence exhibited logarithmic behavior Selfadjusting and Amortized Analysis Limitations of balanced search trees 0 Balanced search trees require storing an extra piece of information per node 0 They are complicated to implement and as a result insertions and deletions are expensive and potentially errorprone 0 We do not win when easy inputs occur Balanced search trees have a second feature that seems improvable 0 Their worstcase averagecase and bestcase performance are essentially identical 0 It would be nice if the second access to the same piece of data was cheaper than the rst 0 The 90 10 rule 7 empirical studies suggest that in practice 90 of the accesses are to 10 of the data items 0 It would be nice to get easy wins for the 90 case Amortized Time Bounds Binary Search Trees Given the above information what can we do Since the time to access in a binary tree is proportional to the depth of the accessed node we can attempt to restructure the tree by moving most recently accessed items toward the root Even if there are intervening operations we would expect the node to remain close to the root and thus be quickly found We could call this strategy the rotate to root strategy Ends up having a Olog n time bound for nonuniform access For uniform access is actually worse than balanced trees An application of the rotatetoroot strategy to node 3 is shown in Figure 13 Page 10

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

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

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

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