So guys, now going forward, I have enumerated here the routing session algorithm.
I request you to go through these six steps off route insertion algorithm and try to relate that we
have actually exercised all these six steps in the examples so far we have discussed regarding without
insertion in the I'm trying it out structure.
All right.
Nevertheless, we will going to discuss one more example of round insertion and the entry.
So so far our M tried to add a structure has taken the following shape as you can see on the screen.
And now the next out that we will going to insert is there are number five.
All right so we will going to insert around 128.1 20 8.0.0 and the mass value is 16.
So obviously we will going to convert this out into its effective prefix form.
So as you proceed towards inserting this round into this in structure, we start our traversal from
the root mode of this and try to add a structure.
All right.
So the very first bit of this new root is one.
So it means that we will going to take the path along the one at the end of the root node of the tree.
And we land at node number three and now we start comparing the effective prefix bits of the new root
with the effective prefix bits of the current node and the try.
So you can see that the first eight bits of this node number three matches with the first bits of the
new root.
But the mismatch happens at the following bit.
That has been zero in the Node three and a bit one in the new root.
All right.
So the node split algorithm will be triggered again at node number three, and the split will happen
on this, but zero, which is highlighted in pink color.
So once again, the node split algorithm will be triggered at node number three.
And as per the algorithm, we immediately create two new nodes, the total node as well as Dani's node.
So let's say this time the data nodes, the node number seven underneath node is the node number eight.
As a part of the algorithm, all the children of the node, which is undergoing a split, is transferred
to the data node.
All right.
So it means that the node number five and node number six, which are the children offload number three,
will be transferred to the node number seven.
And as it is, it's just a plain copy paste.
If you had more nodes, which are the descendants of the node number five, then those nodes would have
also moved as it is being the descendant of the node number five.
So in fact, here we are transferring the entire subtree, which is rooted at node number five.
So when I say moving the children, that is node number five and six, it simply means I'm moving the
entire subtree, which is rooted at more number five and the entire subtree, which is rooted at node
number six from the node number three to node number seven.
All right.
So remember that we are just not moving the children.
We are moving the entire subtree.
Now, the next thing that would happen is transferring the bits from the effective prefix of the node,
which is being going under a split.
So these many bits that is that is starting from the mismatched bit up to the last bit, all the bits
in the effective prefix of the node three will be transferred to the total note.
All right.
So these bits, these eight Brits will be transferred to the data node and the parent node three will
remain with the following bits which are left over.
So it means that node number three would left with the following effect.
The prefix and the length of the affected prefix would be reduced from 16 to 8, because the remaining
Edward's has been transferred to the data node.
The data of the node number three before a split was null.
Therefore copy the data from the parent node to the data node.
The data no data would also be null.
And finally copying the bits from the input round, starting from the mismatched build up to the last
bit.
We will simply copy all these birds as the prefix as the effective prefix birds of the nest.
Not all right.
And the knees note is made that one of the child offered spitting because its first bird is one and
the daughter mode is made.
The zeroth child offered spitting mode because its first bird is zero.
So we have successfully executed the insertion of the five in the same tried it out structure.
All right.
So it is the Node three which will undergo split again and it will give birth to the new Lord seven
and Lord number eight in the trial.
So if you want to see one complete tree, the following is the tree, which would be created after insertion
of five rules that we have discussed.
So this is the final tree and tree keep growing as more number of rolls are added to the tree.
All right.
So not much happens and tree shrinks when the rounds are deleted.
So we will going to discuss our deletion algorithm in detail and having understood the root in such
an algorithm, the rule deletion algorithm would be a cakewalk.
The raw deletion algorithm would be exactly opposite to the round insertion algorithm.
So in this I am trying to add a structure which you can see on the screen we have inserted of these
following five groups and you can see that in this I'm trying in a structure, we have five leaves.
You will have as many leaves, as many rounds you have inserted in the same try to add a structure.
So node number two is leaf nor number four is leaf, nor number five is leaf.
Node number six is leaf and note number eight is leaf.
The pot from the root node to the leaf node represent exactly one root.
All right.
Next we will going to discuss the around search algorithm, loud sounds and what it means that in this
tree we know that we have already inserted five roots.
What if I tell you that?
Hey, tell me whether the root hundred and 28.2 .0.0 slash 16 is present in this MRI or not.
So you have to come up with the yes or no answer that whether the route is present or not, as simple
as that.
So that is called an outside algorithm.
And not to be confused, it is not along as prefix match algorithm.
All right.
I am simply telling you that given around such whether this route was inserted in this M tried it out
structure or not.
So that is the results algorithm, which is really going to discuss next.
So guys, with this we have completed the round in such an algorithm and as a part of exercise, I would
suggest to you that you try to draw your own and try it in a structure and see how does the M created
a structure transform when you insert the following groups and the in this already constructed I'm try
all right.
And the time complexity of inserting a root in the central internal structure is Order of K, which
is the number of words that you are inserting so far.
IPV four outs is a concern with just how to do so.
In other words, the time complexity of inserting it out in the same kind of structure is order of one.