2
Personal as the tree looks after the removal of the number 40?
In my understanding, instead of 40 would be number 41, right 44 and left 30. And the right of the 44 the number 49, to right?
3 answers
1
Well, you have to define which methodology to adopt. You can choose the node on the left, 30, as the new knot that will stand in place of the 40 and then in this case you will have to fetch the right most knot of the knot 30, to allocate the node that was to the right of the 40, the 44. Or you can also choose the 44 as the knot that will stand in place of the 40, and in this case you will have to look for the leftmost node of the 44 to allocate what was left of the 40, in case the 30. Anyway it depends on your methodology, and this way will not unbalance your tree. It would not be feasible for you to try to reorganize it so as to put the 41 instead of the node removed, this is because it would be too laborious to ensure that the tree would not be unbalanced.
Slide by professor Marcos Caetano - Unb.
As you can see, your tree will remain balanced
1
From what I can understand this tree is a binary search tree (ABB).
Whenever a node is removed, the one that replaces its position in the tree must keep the tree as still a binary search tree. That is, smaller numbers on the left and larger numbers on the right. For this you must take the child of the subtree on the left that is the most right and put in place of the node that will be removed.
In this case, since there is no subtree on the left, but only one node, it is this left node that will be put in place. That is, the 30 will replace the position of the 40 in ABB.
This is because the largest element in the subtree on the left is larger than the smallest element in the subtree on the right.
You can understand more about Binary Tree Search removal in this video. That’s where I got the picture.
-
So, but I have a question, he asked for it in the exercise, in the test: "For what if you continue to have a binary search tree configuration, after removing the nodes shown below, what will be the new tree configuration? Redesign."
0
Just remove the desired one and take the larger one on the left or the smaller one on the right and put it in its place.
Browser other questions tagged c graph
You are not signed in. Login or sign up in order to post.
So based on what he asked in the statement: "For what if you continue to have a binary search tree configuration, after removing the nodes shown below, what will be the new tree configuration? Redesign." Could I put in place the 40, the same number 41 I did? He might consider?
– André
You couldn’t, you have to consider that you don’t know what the values of each node are, because it doesn’t follow a numerical order, and you only know that smaller is left and larger is right. Then, you can only define which child node will be in place, whether the left or right. The tree will continue to be a binary search tree in either of the two options.
– Leonardo Rodrigues