### Create a StudySoup account

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

Already have a StudySoup account? Login here

# LAB Data Structures CS 230

GPA 3.89

### View Full Document

## 10

## 0

## Popular in Course

## Popular in ComputerScienence

This 8 page Class Notes was uploaded by Jordon Hermiston on Thursday October 29, 2015. The Class Notes belongs to CS 230 at Wellesley College taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/230947/cs-230-wellesley-college in ComputerScienence at Wellesley College.

## Reviews for LAB 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/29/15

Binary Search Trees Wellesley College C8230 Lecture 19 Thursday April 12 Handout 30 P85 due 1159pm Wednesday April 18 Final Project Phase 2 Program Outline due 130pm Tuesday April 24 gsTIT Overview of Today s Lec rure TRU Review of Binary Search Trees BSTs Searching Inserrion and DeleTion in BSTs ImplemenTing SeTs Bags Tables using BSTs Binary Search Trees V Ru To geT full advanTage of binary Trees for daTa sTrucTures need The values To be ordered A binary search Tree BST is a binary Tree in which The following BST properTies hold aT every node 1 All elemenTs in The lefT subTree are 3 The value 2 All elemenTs in The righT subTree are 2 The value Here is a sample BST i NoTes A BST may conTain duplicaTes The inorder Traversal of BST elemenTs yields Them in sorTed order Eg39 C F F J M P S V For n gt 1 There is more Than one BST wiTh n elemenTs blTr Predecessors and Succesors TRU The predecessor of a node N is The node ThaT immediaTely precedes N in an inorder Traversal of The Tree or null if no such node exisTs Eg The predecessor of node P is node M of node M is node J and of node 339 is node F The successor of a node is The node N ThaT immediaTely follows N in an in order Traversal of The Tree or null if no such node exisTs Eg The successor of node F is node J of node 339 is node M and of node M is node P An MBSTltTgt Class import Javauti import Comparator Iterator public class MBSTltTgt private static MBinTree MBT Local abbreviation for MBinTree Instance Variables private ComparatorltTgt comp private MBinTreeltTgt elts Constructor Methods Constructor that supplies explicit Comparator public MBST ComparatorltTgt comp thiscomp comp elts MBTltTgtleaf Constructor without an explicit Comparator uses null as the Comparator public MBST thisnull other methods go here Comparisons in MBSTltTgt l2 Instance methods public ComparatorltTgt comparator return comp Method uses for all comparisons Use the explicit Comparator comp if it39s nonnull otherwise assume T extends ComparableltTgt and use the compareTo method of an element private int compare T x T y if comp null return compcomparexy else Note the cast here will generate a warning in Java 15 because the cast can fail at runtime for a nonComparable x return ComparableltTgt xcompareToy Searching in MBSTltTgt Refurn True if x is in The free and false o rher39wise public boolean sear39ch T x MBinTreeltTgt here el rs while MBTisLeafher39e inf c comparex MBTvalueher39e if c 0 refurn True else if c lt O here MBTlef rher39e else here MBTr igh rher e Only much here if go r ro leaf wi rhou r finding elemenf39 r39e rur39n false 9m EMAh Inser39fion in MBSTltTgt Tm public void insert T x MBinTreeltTgt child elts MBinTreeltTgt parent null parent of child boolean isChildToLeft true is child the left of parent initialized arbitrarily while MBTisLeafchild search for insertion point int c comparex MBTValuechild if c 2 0 throw new MBSTInsertionExceptionchild element is already in tree else if c lt 0 parent 2 child child MBTleftchild isChildToLeft true else parent 2 child child MBTrightchild isChildToLeft false Only reach here if got to leaf without nding elernent Replace the leaf in parent by a new node MBinTreeltTgt newNode MBTnodeMBTltTgtleaf x MBTltTgtleaf setChildparent isChildToLeft newNode Se r ring The Child private void seTChild MBinTr39eeltTgt por39en r booleon isChildToLef i MBinTreeltTgt newChild if por en i null special case when no por39en r el rs newChild else if isChildToLef r MBTseTLef rpor39en newChi Id else MBTseTRighTpor39enT newChi Id Dele rion In MBSTltTgt public boolean dele re T x MBinTreeltTgt child el rs MBinTr eeltTgt par en r null par en r of child boolean isChildToLef r True is child The lef r of par en r ini rialized ar bi rr ar ily while MBTisLeofchild search for inser rion poin r in r c comparex MBTvaluechild if c 2 dele reNodepar en r child isChildToLef r See nex r slide r e rur n rr ue elemen r is in Tree else if c lt O por39en r 2 child child MBTlef rchild isChildToLef r True else par eni 2 child child MBTr igh rchild isChildToLef r false Only reach here if go r ro leaf wi rhou r finding elemen r r e rur n false elemen r no r in free 19710 333 deleTeNodeO DeleTe a nonleaf child from possibly null parenT privaTe void deleTeNode MBinTreeltTgt parenT MBinTreeltTgt child boolean isChildToLefT Easy cases are if one subTree of child is a leaf if MBTisLeafNBTlefTchild seTChildparenT isChildToLefT MBTrighTchild else if MBTisLeafMBTrighTchild seTChildparenT isChildToLefT MBTlefTchild else Hard case is if neiTher subTree of child is a leaf In This case deleTe predecessor and replace child39s value by predecessor39s value T predecessorValue deleTePredecessorchild See nexT slide predecessorValue is guaranTeed To be nonnull in This case since only geT here if MBTlefTchild is noT a leaf MBTseTValuechi ld predecessorValue 19711 EXITED deleTePredecessor R DeleTes The predecessor of This node and reTurns iTs value ReTurns null if There is no predecessor privaTe T deleTePredecessor MBinTreeltTgt node if MBTisLeafMBTlefTnode reTurn null No predecessor reTurn null else MBinTreeltTgt parenT node MBinTreeltTgt child MBTIefTnode boolean isChildToLefT True while MBTisLeafMBTrighTchid Find The predecessor node righTmosT node To The lefT of given node parenT child child MBTrighTchild isChildToLefT false deleTeNodeparenT child isChildToLefT deleTe predecessor node Since righT of child is a leaf This will use quoteasyquot case of deleTeNode reTurn MBTvaluechild reTurn value in predecessor node 19712 99D DATA AbsTracTing over BST search FindInfo I Ru public class FindInfoltTgt public MBinTreeltTgt parenT child public boolean isChildToLefT public FindInfo MBinTreeltTgt parenT MBinTreeltTgt child boolean isChildToLefT ThisparenT parenT Thischild child ThisisChildToLefT isChildToLefT 19713 AbsTracTing over BST search find 392 If x exisTs in Tree reTurns a FindInfo fi where fichid is The node conTaining x fiparenT is The parenT of child or null if There is no parenT fiisChildToLefT is True if child is To The lefT of parenT or There is none else false If x does noT exisT in The Tree reTurns a FindInfo fi where fichid is The leaf where x would be inserTed inTo The Tree fiparenT is The node below which x would be inserTed inTo The Tree fiisChildToLefT is True if x would be inserTed To The lefT of feiparenT else false public FindInfoltTgt find T x MBinTreeltTgt child elTs MBinTreeltTgt parenT null parenT of child boolean isChildToLefT True is child The lefT of parenT iniTialized arbiTrarily inT c O resulT of comparison iniTialized arbiTrarily while lMBTisLeafchild ampamp sTuff resulT of comparison in variable c c comparex MBTvaluechid 2 0 if c lt O parenT 2 child child MBTlefTchild isChildToLefT True else parenT 2 child child MBTrighTchild isChildToLefT false reTurn new FindInfoltTgtparenT child isChildToLefT 19714 99D Qg j Abs rr39ac red searchO IHSCPTO deleTeO public boolean search T x r e rur n lMBTisLeaffindxchild public void inser r T x FindInfoltTgt fi findx if MBTisLeaffichid MBinTreeltTgt newNode MBTnodeMBTltTgtleaf x MBTltTgtleaf se rChildfipar en r fiisChildToLef r newNode else Throw new MBSTInser rionExcep rionUichild elemenf is already in Tree public boolean dele re T x FindInfoltTgt fi findx if lMBTisLeaffichild dele reNodefipar en r fichild fiisChildToLef r r e rur n rr ue elemen r is in Tree else r e rur n false elemen r no r in free 19715

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

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

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

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