New User Special Price Expires in

Let's log you in.

Sign in with Facebook


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


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Ulises Graham Jr.


Ulises Graham Jr.
GPA 3.58


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 39 page Class Notes was uploaded by Ulises Graham Jr. on Saturday September 12, 2015. The Class Notes belongs to CSCI 2720 at University of Georgia taught by Liu in Fall. Since its upload, it has received 46 views. For similar materials see /class/202312/csci-2720-university-of-georgia in ComputerScienence at University of Georgia.

Similar to CSCI 2720 at UGA

Popular in ComputerScienence




Report this Material


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/12/15
CSCI 2720 Data Structures Lecture 20 23 Tree Tianming Liu Department of Computer Science amp Bioimaging Research Center The University of Georgia Slides Courtesy Eileen Kraemer Outline El Balanced Search Trees 0 23 Trees 0 234 Trees 0 RedBlack Trees Why care about advanced implementations Same entries different insertion sequence 9 Not good Would like to keep tree balanced 2 3 Trees Features gt each internal node has either 2 or 3 children gt all leaves are at the same level 2 3 Trees with Ordered Nodes 2node 3node a Search keys lt S Search keys gt S Search keys lt S Search keys gt L Search keys gt S and lt L Example of 2 3 Tree Traversing a 2 3 Tree inorderin ttTreeI TonhreeTree ifttTree s root node r is a leaf Visit the data items else ifr has two data items inorder1eft subtree of ttTree s root Visit the first data item inordermidd1e subtree of ttTree s root Visit the second data item inorderright subtree of ttTree s root else inorder1eft subtree of ttTree s root Visit the data item inorderright subtree of ttTree s root What did we gain 8 b 6 What is the time efficiency of searching for an item 1020 Gain Ease of Keeping the Tree Balanced Binary Search Tree both trees after inserting items 39 38 32 Inserting Items Insert 39 Inserting Items Insert 38 dh deleaf insertinleaf and nwove n ddle value up to parent result Inserting Items Insert 37 Inserting Items Insert 36 insert in leaf divide leaf and move middle value up to parent b 50 overcrowded node Inserting Items still inserting 36 divide overcrowded node move middle value up to parent attach children to smallest and largest result Inserting Items After Insertion of 35 34 33 I Inserting so far 0 M P gt quot lt9 quot n1 n2 0 gt 5 M L 39 a b P M n1 n2 I Inserting so far Inserting Items 9 creating a new root if necessary 9 tree grows at the root New root Inserting Items How do we insert 32 Inserting Items Final Result Deleting Items Delete 70 a Swap with inorder successor Deleting Items Deleting 70 swap 70 with inorder successor 80 a Swap with inorder successor Deleting Items Deleting 70 get rid of 70 b c d ill 0 93 Delete value from leaf Merge nodes by deleting empty leaf and moving 80 down Deleting Items Result Deleting Items Delete 100 Deleting Items Deleting 100 Delete value from leaf Doesn t work Redistribute Deleting Items Result d Deleting Items Delete 80 d Deleting Items Deleting 80 a Swap with inorder successor Deleting Items Deleting 80 0 Delete value from leaf Merge by moving 90 down and removing empty leaf lt Node becomes empty Deleting Items Deleting 80 d e 4 Root becomes empty Merge move 50 down adopt empty leaf39s child remove empty node Remove empty root Deleting Items Final Result comparison with binary search tree Deletion Algorithm I Deleting item I 1 2 9 3 Locate node n which contains item I If node n is not a leaf 9 swap I with inorder successor deletion always begins at a leaf If leaf node n contains another item just delete item I else try to redistribute nodes from siblings see next slide if not possible merge node see next slide Deletion Algorithm II Redistribution a A sibling has 2 items Redistribute o 9 redistribute item between siblings and parent 6 0 Sibling Leaf Merging b No sibling has 2 items 9 merge node 9 move item from parent to sibling Sibling Leaf Deletion Algorithm III Redistribution C R d lb Internal node n has no item left 95 o 9 redistribute 333 6 0 n a b C d a b c d d Merglng 0 Merge Redistribution not possible a 9 Empty 9 merge node men 9 move item from parent to sibling a b C 9 adopt child ofn If n39s parent ends up without item apply process recursively Deletion Algorithm IV If merging process reaches the root and root is without item 9 delete root Height h Height h 1 Operations of 2 3 Trees all operations have time complexity of log n I The End


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

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

Amaris Trozzo George Washington University

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

Steve Martinelli UC Los Angeles

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

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.