All you need to define is a node class potentially that holds some parameters and depending on

what you plan to do with it, you add some internal data like what are the leaves of

the trees.

Tree height, whatever you like, right? Remember how classes work. So implementing them, a

given structure is relatively straightforward. With trees and graphs, the thing is processing

them is difficult. So inserting new nodes, deleting nodes, finding specific parts. For

the trees, finding is not that difficult because what we have already established that if you

have a binary search tree, remember how this works, right? So all the leaves are smaller

than the root on the left and on the right, all the leaves are larger. This is just a

binary search tree invariant. So having that is great if the structure itself doesn't change

too much.

Now what we have started to discuss last week is what are we going to do if things change?

If we need to add a new element and then maintain certain invariants here. And from this point

overall I would really like to emphasize that it's only about understanding the concepts.

So you will probably never be asked to reproduce source code for something that follows from

here from memory. If you need something like that, the most important thing is to remember

what's possible, what are the restrictions, what are the terms to look for. And then you

can ask JetJPT to write the kind of class that does it for you or some binary search

tree or something like that, or just Google it on Stack Overflow. Really key is that you

understand these key concepts. And one of the key concepts in trees is really this AVL

invariant. We need to make sure that somehow the tree does not degenerate. It means that

the tree probably becomes a list and everything is on one side. And to maintain that we have

several options. We can process the entire tree all the time and rebalance things and

make sure everything is after every insertion good again. But the problem is that this rebalancing,

this kind of reshaping of the tree operation should not take longer than a tree search,

log n. Should not take longer than that log n we have. A little bit more is okay, but

anything that goes towards n, all of that becomes useless because then I could just

throw it in a list and just look at every list element and find it or whatever I like.

So we want to keep that overhead low. And so what we figured out is that of course I

can rebalance that or make kind of assumptions that the left side and the right side, a root

should always have kind of two sides. But some of these assumptions are way too strong

runtime wise and others are too weak. We would probably run into stinty generated trees and

smart people in the sixties came up with this AVL invariant and the AVL invariant says nothing

else that for every node, the height of its left and right sub tree may only differ by

at most one node, one leaf. So the differences between sub trees should not be more than

one or must not be more than one. And now implementing this is a little bit cumbersome,

but there AVL in general means Addison, Velsky and Landis, which were the inventors of that

idea. People also call it a very lovable tree. Really, if you remember AVL tree, then that's

the key word to look for if you want to have an overest balance tree and kind of the base

variant of a self-dependent tree. And if this invariant is maintained, then our tree will

have a height of log n. So we will be able to search this tree at the log n time. Now

how to do this actually? So just a few examples first. I mean, this here is obviously, I mean,

it is a binary tree, right? Every node has two leaves here. It is the BSD invariant is

not maintained here, right? So the four is on the right side. It should be on the left

side to be a binary search tree. And since the BSD invariant is violated here, it cannot

be an AVL tree. AVL tree has to fulfill these. Now the problem with this tree here is the

AVL invariant says the two sub trees must at least differ, must at most differ by a

height of one. And remember how to count heights at zero, one, two, three. And here we have

also zero, one, two, three. But the subtree here has two and each of those have basically

just one. So there is that the AVL invariant is not maintained in this subtree. So there