Welcome! Log In Create A New Profile

Advanced

Assignment 4 Question 4

Posted by stevenv 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Assignment 4 Question 4
July 05, 2006 11:26PM
Does anybody know what is meant by "the minimum node in a binary search tree"? Does this mean the node with the smallest info value or is it referring to a node's position within the tree?

Also, why would you need to pass in a node pointer type to this function? Surely it should be a parameter-less function which will just find the node and remove it?

Steven
Re: Assignment 4 Question 4
July 08, 2006 11:27AM
Just realised that this method must be recursive (as required in the question) so obviously you'd have to have a node pointer type parameter! I'm going with the assumption that the minimum part means that it must be the node with the smallest info value.
avatar Re: Assignment 4 Question 4
July 10, 2006 08:39PM
This seems almost too simple, am I missing something?

Binary search trees are automatically sorted to the node with the smallest info value is the one on the far left. Are we supposed to combine the delete and search operations.

An inefficient algorithm, which I'm thinking of submitting is to traverse as far left as I can to find the value of the info of that node and then call the delete function. It's inefficient because the delete function will be traversing the same route a second time in order to do it's own search for the node.
Re: Assignment 4 Question 4
July 11, 2006 02:47PM
I basically wrote a function to traverse the left nodes of the tree and remove the node furthest to the left. If that node is null, I removed its parent and moved the right-hand siblings up a level to where the parent was. Basically combined core functionality from search and delete methods into new routine which does these two tasks. I also initially called search and delete routines but also realised that its not very efficient because of the duplication of tree traversal.
avatar Re: Assignment 4 Question 4
July 11, 2006 04:05PM
I didn't bother - I don't need the credits
Sorry, only registered users may post in this forum.

Click here to login