| Welcome to UCR CS 14 Klefstad. You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free. Join our community! If you're already a member please log in to your account to access all of our features: |
| HELP remove function | |
|---|---|
| Tweet Topic Started: Nov 16 2013, 01:48 AM (120 Views) | |
| Deleted User | Nov 16 2013, 01:48 AM Post #1 |
|
Deleted User
|
Hi guys, I just can't figure this remove function out and could use some help, I think I have it almost all solved(could be wrong. But there is one thing I don't get. When you want to remove a node that happens to be a leaf. After you pop it off, How do you set its parent node to NULL in the direction of the leaf you removed. Here is my code. please critique it if you see its incorrect. And give me advice on how to get it working and solve my problem. Spoiler: click to toggle
|
|
|
| Deleted User | Nov 16 2013, 02:04 AM Post #2 |
|
Deleted User
|
First I'll critique an error I see. Line 9: remove(toRemove->key, toRemove->right) should be remove(key, toRemove->right) As for the leaf case. There's two ways to deal with this. The first to modify your find to return the node before the one you want to remove (very messy). The second is to make a helper function findParent(TreeNode* t) that returns a TreeNode pointer to the parent node of t. The latter is easier to implement, so it will save you time code, but it requires you to traverse the tree again. The prior would save a traversal, but adds extra overhead to your function. Either one should work. EDIT: critique is based on the assumption that find checks the node passed to it (though it'd be pretty wonky if it didn't) and that findMin finds the successor to the node passed to it. |
|
|
| Deleted User | Nov 16 2013, 02:55 AM Post #3 |
|
Deleted User
|
Perfect, I'll use the helper function. And I'm not sure I'm following your critique, Since I want to remove the predecessor, now that I have copied it's key and info into tobeRemoved. Now the predecessor and toberemoved share information, so I want to remove the original value which is at the bottom of my tree, so I need to pass in its key since it remains unchanged. |
|
|
| Deleted User | Nov 16 2013, 03:03 AM Post #4 |
|
Deleted User
|
findMin has to be finding the successor if it's going to the right of toRemove. The sub tree to the right of toRemove can only contain keys greater than toRemove's key. By finding the min of that sub tree you find the successor (aka, if you were to print, this key would come after toRemove's). Either way, I get what you mean. I didn't fully understand the code (getting late, slightly tired). Your recursive call to remove is correct. Do keep in mind that when you use the find predecessor or successor method, you get another special case. That special case is the one where the predecessor's node is directly to the left of toRemove or when successor's node is directly to the right. The recursive call to remove would fail in this case as you lose the method to find the parent (which would be toRemove in this case, with t being it's pred/succ). That special case will occur a lot when removing for words.txt. |
|
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
| « Previous Topic · Homework 6 · Next Topic » |





12:15 PM Jul 11