So, welcome to today's lecture. Do you hear me today well? Yes? Okay. Great. It's the

last lecture before Christmas. Bernhard is travelling, that's why we're doing this lecture

Our topics for today will be binary trees and Git and version control. We'll start with binary

trees. In the last lecture, we've seen searching and sorting as example of lists. And now we're

looking at data structures, which can be organized as trees. A binary tree is a collection of nodes

where each node has at most one parent and anywhere from zero to two children. You see

something like that depicted on the right. We have our nodes which have a value and they're

interconnected. And every node has zero up to two children. So we have our root node here. It's

a parent at the top of the tree. So basically our tree is the other way around. And a natural tree

would be we have the root at the top. But it's easier for us to organize this way. That's why the

root is at the top. And then we have leaf nodes. Leaf nodes are nodes with our children, like for

example, six, also four. And the substructures are called subtrees. For example, the two would

start a new subtree around here. And the five starts another subtree as well. You can go to three

and you have the subtree with all the four included. The longest path from root node to any leaf node

denotes the height of the tree. And the overall tree can have a height and subtrees can have heights

as well. So it's about we count the number of edges, which would be the arrows in this case here.

So what is the height of the following binary trees? We have seen height as a number of edges

contained in the longest path from root node to any leaf node. You can define height differently.

So be careful if you talk to people you haven't talked about that before. We define it here as a

number of edges. So if you look at the first entry, what would here be the height of the tree?

Any suggestions? Yes. I heard it already. It's height two here since we count the number of edges.

For the middle tree, we have the height of the middle tree. So we have the height of the middle

tree and the height of the edges. For the middle tree, what are the suggestions here?

Zero. Yes, I heard it already. It's zero. And the last case, any suggestions here?

Yes, undefined. But we need to assign a value and it can be any value which we haven't used for any

other height. We just choose here minus one. But you could assign minus 100 as well if you like.

It's just that you have to put anything there.

Okay. If we look at these structures, as let's assume we have a binary tree of height h,

now we are interested in what could be the maximum number of leaves and the maximum number of nodes.

In this case, we are on the left side here. We would get a very balanced tree if we get the maximum

number at any point. And for the leaves, it would be two to the power of eight. For the nodes,

it's two to the power of eight plus one minus one. Our overall height in this example is three,

the longest path down this tree, as well as here. But on the right side, we have a very degenerate

version of a tree. It's more a list than we get them to this easiest case. And the minimum number

of leaves in this case would be one and the minimum number of nodes, h plus one. So we have

these two extremes our structure could look like. One is more like a linked list and the other one

is a very balanced tree. These are the two extremes. So we have a very balanced tree.

These are the two extremes we have for binary trees.

Now we want to do something with our structured data. In most cases, it's searching for data.

For this, it's useful to add invariants to our data, which we can use for meta-searching.

One of these structures would be the binary search tree invariant.

This invariant's rules for your data structure, the whole tree, which is valid for the whole tree.

In this case, the binary search tree invariant is very useful and it is for every node with key k.

The left subtree has only key smaller than k and the right subtree has only keys greater than k,

which means sorting by the absolute of the value. In this case, we have only positive numbers.

If we look at the example here, our root node would be the nine and all values on the left

and the left subtree are smaller than nine. All values in the right subtree are greater than nine.

If we don't know what invariants are true for our data, we need to find out. If we make mistakes here

and don't check for that, our searching will obviously not work. But keep in mind the binary

search tree invariant. It's one of the invariants which are useful for searching in these structures.