So guys, now let us go through the examples in which we will going to discuss how report can be deleted
from the tried in a structure.
So you can see that is the amp tried in a structure which is already buried because at this point of
time these six rounds have been inserted into the same try to do structure.
All right.
So now let us delete each of these rules one by one, starting with the first round.
So we want to delete around 1.2.2.4 slash 32 from the same tried it out structure.
So the very first thing again we will do is to compute that effective prefix of disrupt.
All right.
And now let us go through that steps regarding without deletion.
So the very first thing that we need to do is that execute the root search algorithm and locate the
leaf node, which stores the data for this round 1.2.3.4 slash 32.
So the exact match about such a lot of time with going to give us the node number nine.
All right.
After having located such a node, simply delete that.
Not so.
The node number nine is deleted straight away.
All right.
So obviously in the parent node, you will add just the pointer value to point it to null because the
child has been deleted.
Now you can see that the node number two is a half note.
It is a node which has exactly one child and that is an unknown number ten.
So now we need to fix up our and try such that the node number two becomes the full note.
That is the node with exactly two children on the node with exactly zero children.
The node number two cannot continue to exist as a half node.
So the following step is the node merging algorithm.
So let us execute these steps one by one.
The very first step sees that append that the fact the prefix of the other child, which is the node
--.
So node nine appearances norge do and node two's adult child is node ten.
All right.
So append the the prefix on the node damage to the effect, the prefix of the node to the effective
prefix of the node and contains don't care, which is 24 times drawn care bits so that in fact the prefix
of the node tool would become.
The effect, the effects which it already has upended, but effective effects of the note ten, which
is 24 times don't care.
And obviously since you are merging 24, don't care words to the effect of prefix of the knowledge.
Do therefore the perfect slant of the nodes to what become eight plus 24, which is 32?
All right.
So, in fact, the profits of the model is.
Seven times zero, then one and then 24 times.
Don't care a bit.
Then the second step is that the transferred the data of the node returned to the node two.
So here the Nord then has the data, which is next.
All 1.0.0.0 slash it.
That is pointer to some object in the memory which represent the next hope.
So simply transfer this data to the parent, which is not true.
So the data part of the Nord two would become next to all.
1.0.0.0.
Slash it.
That is the next top of the hour out.
1.0.0.0 slash aid has been moved from the node down to the node two.
Then the next step sees being the parent child relationship between the two and the down that does this
linkage will going to be broken so nodules don't care.
Children would become null.
All right.
And the next step says that transfer all the children of the Norge down to the Node two.
So in this case, the node plans a leaf node A do not have any children.
Therefore there will be no transfer of any children of the Node Tam to the Node two.
But if Node Dan had any children, then they would have been moved as a children to the Node two and
finally delete the node down as well.
So it will take you a couple of to three times a practice to actually exercise this round deletion algorithm.
So don't worry, we will going to delete all these rules one by one from the same title structure.
So now you must be very eager to see what does the final try data structure look like when the root
1.2.3.4 has been deleted from this?
I'm trying to add a structure so you can see that deletion of a root from the and try and result in
the deletion of two nodes from the.
I'm trying to add a structure.
In this case, the node number nine and an order number ten.
So the final I'm trying to add a structure would look something like this.
All right.
You can see that, in fact, the prefix of the Node two is now grew from just prefix length age to full
prefix land.
32 Because this portion of the effective prefix is coming from the node number ten, which has been
smashed into the Node two.
So again, let us take one more example.
Let us delete the rule 120 8.2.3.4 slash 32.
So convert the round that is to be deleted into effective prefix form.
All right.
And now execute the exact match without such a lot of time.
And you will find that the node number five is the node, which we are willing to delete.
It is the node which holds the next hope for the root, which is being deleted.
So we are interested in building the node number five.
So of a delete the node number five, add just a pointer of the parent node to point it to null because
its child has been deleted and now the node number seven has become a half mode.
Therefore, node number seven will execute the merge a lot of time.
All right.
So, again, these steps will be executed.
You append the prefix of the node six to the effective prefix of the Node seven.
So in order to have an effective prefix would become x x x x 16 times and the perfect land of the Lord
seven would become 24 because 16.
Don't care.
Betts has been transferred to the North Salem.
Then transfer the data of the node six to the data of the Nord seven.
All right, so the data part of the Nordics would become null.
Then big the parent child relationship between the Lord seven and the Lord sakes of the Lord 7.5 needs
to be adjusted to point it to now, not problems for all the children of the Lord.
6 to 0 seven.
So in this case again, Lord six is a leaf naught.
Therefore there is no need to cross for any children of the Lord.
Six children or seven, and finally delete the Lord.
Six.
All right.
So the final add a structure would be this one.
All right.
The Nord number five and the Nord number six has been completely disappeared from the same tried it
out structure.
Now let us go through the next example.
So proceeding towards the next example, let us delete the number three, which is a default account.
So execute the exact match out search algorithm and you will find that you need to delete them before.
All right.
Now, it is an exceptional case that whenever you need to delete a node, which is a direct crime of
the root node, then you have to do nothing.
Simply delete that particular note from the and try to add a structure and add just the parent and add
just the child pointer of the parent node to pointer to know.
All right.
So the final I'm trying to now structure what looks something like this.
The node number four has simply disappeared from the same tried data structure.
All right.
The root node would never execute much algorithm.
Remember that?
There is no need for the root node to execute anymore algorithm.
Our root node can be half node.
It can have one child, it can have two children, it can have three children.
A route node enjoys all the privileges.
So guys now you can see our I'm in a structure is gradually shrinking.
Now let us continue with the our deletion.
Now let us delete that out.
Number four, which is 120 8.2.0.0, slide 16.
So the effect, the prefix of this root would be the following.
All right.
So using exact match out search, a lot of time, we were going to locate the node, which is a node
number seven, which holds the data for this rule 120 8.2.0.0 slash 16 and ask for the algorithm before
going to delete the node number seven straight away.
And it's better than us.
Node number three would become a half node, so it will execute the merge algorithm.
All right.
After executing the March algorithm, the node number eight would be vanished, and node number three
will borrow the effective prefixes of the Node eight, such that the node number three would have the
effective prefix of land 32.
The data part has also borrowed from the Node eight, which has just vanished.
Also, the node number eight, which is just deleted, did not have any children.
Therefore, there is no transfer of any children from the node age to the node three and the node three
becomes a new leaf not.
So this completes the deletion of the routing.
And before then coming to the routing number five, compute the effective prefix of the route five.
And triggered the troop surge.
Exact match algorithm which would give you that.
Nor number three.
All right.
And now we will simply going to delete the node number three.
And since the parent of the Node three is our root, therefore there is no need to execute my algorithm.
So the final I'm trying to add a structure would be the following, as simple as that.
And this completes the deletion of the round number five.
Now let us delete the final result.
So compute the effective prefix of the shroud and rebuild the exact match around such algorithm which
would going to give you that node number to.
All right.
So delete the number two.
And since the parent is en route, therefore there is no need to execute an emerging algorithm.
And the final I'm trying to add a structure would be the following.
All right, so we arrive at the same place from where we began.
Our root node enters into the initialized state again.
All right, so this completes the deletion of all the problems from this.
I'm trying to add a structure.
So I would suggest that you can rewind the lecture video and repeat an exercise, the round relation
algorithm again.
So so far we have completed the route insertion.
They're our search.
And route deletion.
And what is left is the final thing, which is root lookup, which is based on longest prefix match.
So this is the next and the final algorithm that they were going to discuss.