In this algorithm, we take a body, b, and start inserting

it into a tree recursively by starting with the root node, n.

Inside this recursion, if a node is empty, which means it does not already

contain a body, then when we are done we just take the body, b, and put it there.

And we have a new n node with this body, b.

But if on the other hand the node is an internal node,

which means it contains children, then while this node will

represent a portion of space In which we have right now introduced a new body,

which means that this node needs to update its total mass and

its center of mass in order to take into account the mass and

position of the new body b.

Then, we recursively insert a body b into the appropriate quadrant, which is

one of the children of this node, by repeating over again the same algorithm.

Finally, if the node n in which we try to place the body is already

an exterior node then this means that it already contains previous body which

was previously inserted which collides with the body we are trying to insert.

In this case, we need to further cell divide the base node into four

quadrants and place the two bodies which were in conflict into their appropriate

quadrant and reapply this procedure recursively if they collide again.

And that's what we do with this.

Whenever we treat a new node, we update the center-of-mass of this

new node to take into account the mass of the two conflicting bodies.

We also of course, update the center of mass, to take into account their position.

Now that we have this cost of the general terms of the algorithm,

let's finish inserting all of the ten particles, or

all of the ten stellar bodies which we have in this system.

We're down with inserting body two and three, which were colliding and

which we have to take to the third recursion level to

find n nodes in which they are separate from each other.

Body number four is placed into the northeast quadrant

at the first recursion level, which means the northeast right quadrant.

The northeast right quadrant is all ready and

then t nodes there are all ready bodies there.

So we go at the next level, at the green level,

the second recursion level and see that this recursion level,

the new body goes into the northeast quadrant which is empty.

We therefore create a new n node and

place body number four into this quadrant.

Body number five, and

we are going to take shortcuts now because I think that you understood the concept.

Body number five is in the same red quadrat and

the same green quadrant as body number four.

We therefore need to take this quadrant and

subdivide it into two black quadrants at the third recursion level and

place the four colliding bodies four and five into their own third level quadrant.

After which, we insert all the remaining bodies, six, seven, eight, nine, and ten.

We see that the first recursion level, the red level, one quadrant remains empty.

It is the southwest quadrant.

For this quadrant, we don't allocate anything.

It does not exist in the tree we have just created.

On the other hand, the northwest quadrant has a total of four particles.

One of which, particle 10, is in its own green quadrant,

whereas particles seven, eight and nine collided or

were in conflict in the northeast green quadrant and

were subdivided into block third level quadrants.

On the right-hand side, you now see the full tree.

All bodies are end nodes in this tree, and they are represented by an orange node.

The blue nodes are interior nodes at which we have placed no body, but

which represents a portion of space which contain the bodies which

are the children of these nodes.

They have their own center of mass and their own total mass which we

have computed and updated and insert it in your bodies.

Now that we have created this tree structure,

we are ready to apply it and use it to efficiently compute

the forces which act from all other bodies on to one given body.

But we will take

this to the next module.

This ends our current module on the creation of an tree, or

a quadtree in according to the Barnes-Hut algorithm.

In the next module, we'll describe how we use this quadtree.

Thank you. [MUSIC]