Deleteing from BST
ok, i need to delete a tree from a binary search tree, the simplest case is when i want to delete a leaf node, check if the left and right are null and delete it.
now comes the hard part, if the node i want to delete has nodes to the right or the left. i need to link back the nodes after deletion, i mean i how do i do that, i though i could use two pointers but its not helpful, because i would only have access to the node i am going to delete and the node that is hanging off the node that is going to be deleted, i can't connect it back to the node that is before the node that is going to be deleted, i though of then three pointers but that gets a bit weird.
is there any algorithm you can point me to for deletion of a node from binary search tree.
The problem is that we were never though how to do deletion, they said in class you never have to do it, it's just a mess. but in a assignment we are to.
now comes the hard part, if the node i want to delete has nodes to the right or the left. i need to link back the nodes after deletion, i mean i how do i do that, i though i could use two pointers but its not helpful, because i would only have access to the node i am going to delete and the node that is hanging off the node that is going to be deleted, i can't connect it back to the node that is before the node that is going to be deleted, i though of then three pointers but that gets a bit weird.
is there any algorithm you can point me to for deletion of a node from binary search tree.
The problem is that we were never though how to do deletion, they said in class you never have to do it, it's just a mess. but in a assignment we are to.
Depends on how that tree is build.
If I'd do that I'd have an array/vector for the actual data and the tree contains the indexes to that array. Deleting a learf would be removing the data from that array and then rebuild the tree.
If I'd do that I'd have an array/vector for the actual data and the tree contains the indexes to that array. Deleting a learf would be removing the data from that array and then rebuild the tree.
Topic archived. No new replies allowed.