|
Yesterday we met with the Assignment 3 group during the morning and made ourselfs a task list for the holiday project. I won’t talk too much about it on here until i’m done with the other parts.
During the lecture we were taslked to figure out one segment ourselves and while i was close to solving it, i couldn’t quite figure it out. With my mood ruined i went home and started reworking my erase function on y binary search tree while being too angry to write anything on the blog.
The rework of the erase function was the final thing i needed for the first part of the assignment.
Previously i had made them to take into account each of the node to be removed’s children’s children, as well as the relation to the node’s parent. The first version was also not entirely reliable as when i designed the list i was going to use and what numbers to remove i didn’t take into proper account what the nodes’ relations between each other would be when some had been removed.
I completely rewrote the erase function and divided the cases into 4 kinds, multiplied by a few other variables.
1. Node has no children.
When the node in question is childless not a lot needs to happen.
The only thing that needs to be done is check the relation between the node and the node’s parent, if the node is the highchild of the parent, the parent’s highchild is changed into a nullpointer and vice versa if the node is the lowchild.
The node and it’s values are then simply removed.
2. Node has one child.
Slightly trickier than the first, first it checks which of the node’s child pointers isn’t empty.
Then it checks the relation between the node to be removed and it’s parent.
It then sets the parent’s corresponding pointer with the node to be removed’s child node and sets the child node’s parent pointer to the parent of the node to be removed.
There are actually four different cases depending on the high and low child relations.
3. Node has two children. The lowChild’s highChild is empty.
Similarly to case 2, this case simply replaces the pointers to the node to be removed with it’s earlier lowchild. This can be done since the original node’s highChild can be placed as the highchild of the node replacing the original node.
4. Node has two children. The lowChild’s highChild is not empty.
Rather than check the children of both children to the original node to find the first empty one, this function loops through the highChilds’ highChilds of the original node’s lowChild to find the highest one without a highChild of it’s own. Once it locates this it sets the original node to be the value of the bottom before removing the bottom node.
The one thing that needs to be done for this is if the lowest highchild has a lowchild. In which case the lowchild takes the place of the node which is removed and the parent node’s highchild is set to point to it.
5+
There are a few modifications to these, most importantly if the node to be removed is the root of the list. This manifests in a boolean which is set at the beginning and to which a check is put around most places in the other cases where the parent of a node is used. Rather than set a node to be removed parent’s child pointer to a specific node, the removed node’s replacer’s parent is simply set to a nullpointer and set to be the root of the tree.
For this new system i made a new list of variables and replaced the arguments of the functions in the main class in which i modify the numbers in the tree and search list while running checks in order to make sure the numbers are handled correctly.
I finished the erase function before lunch today but before that we had a small extra meeting with Tommi where he went through some of the basics of how a web server is structured and how the server and client connects to each other using sockets. Unlike during the lectures he actually drew on a whiteboard to describe the process which made it much easier to understand. I’ll make sure to bring that up in the course review. Also i am aware of how ironic it is to write this in a post with no images, i should post some at some point.
During the afternoon we made our planning for the holiday project but also had some alumni speaker presentations which i expected to be a waste of time but i actually found them interesting and a nice change of pace from the regular work.
 
|