Hello again! In this video, we are going to look at the tree data structure. C++ uses this for implementing
associative containers in the standard library, so it is useful to have some idea of how it works.
If you already know this, then you can just skim through this video.
But if you are not familiar with trees, or you want to go over them again, then I hope this will help
you. The elements in a tree are similar to the elements in a linked list.
We have a separate node for each element.
This has a key which will identify the element, and two pointers, which point to other elements in
the data structure. In the tree,
these are called left and right, and the position of the element in the tree depends on the value
of its key.
The left pointer will be to an element which has a lower value of the key than ours, and the right
pointer will be to an element which has a higher value of the key.
The tree data structure looks like this, and I know it is not like a real tree! In computer science,
trees always have their root at the top and the branches at the bottom.
So we start here, and then we grow downwards and outwards.
The first element, which is added to the tree, is called the root.
So here is our root, with the key 6, and left and right pointers.
If we add an element with the key seven, 7 is greater than 6, so we need to be on the right of 6
and then we set the right pointer of 6 to point to this new element.
If the key is 4, then 4 will need to go to the left of 6, because it is lower than 6, and the
left pointer will point to this element.
What happens if we have an element with key 5? So, 5 is less than 6, so we go left, but 5
is greater than 4,
so we go right. And then, for an element with key 3,
3 is less than 6,
So we go left, and 3 is less than 4.
So we go left again.
So we now have five elements, and 3 was the last one which was added. So inserting an element,
once you know where to insert it, just involves modifying a pointer.
Erasing an element can be a little bit more complex.
If we erase this element 4, then we need to make sure that 3 and 5 go into the right position.
The main advantage of this structure is that locating and searching for elements is very fast.
Let's say we want to find this element with the key 3.
So we start at the root. 3 is less than 6, go left.
3 is less than 4, go left again.
And we found it.
So we only needed to look at three elements to find this, even though there are five elements in the container,
and this was the last one which was added.
So this is quicker than searching a sequential container.
So adding or removing an element is very fast.
There are no memory operations, apart from the actual allocation of the node.
Only one other element needs to be modified, and that is just a pointer assignment.
And there is no moving around of elements within the tree.
And also finding elements is very fast.
We just need to compare the data and dereference a pointer for each element, until we get there.
There is just one potential drawback to trees. If we have too many elements on one branch, or on one
side of the tree, then the tree becomes unbalanced and operations take longer.
If this gets too bad, we may need to rebalance the tree.
To do that, we need to choose a different element as the root, and then move all the elements around
it, making sure they have their correct relative positions.
And that will make the tree balanced again.
There are some tree structures which will actually do this automatically. These are "balanced" trees
or "self-balancing" trees.
They will notice when the tree gets too badly unbalanced and they will rebalance
it. Examples of these are the red-black tree and the AVL tree.
I am not going to go into any detail about how to actually implement a tree yourself, but it is actually
a good exercise in using pointers, if you want to try it.
And there is plenty of material around.
Okay, so that is it for this video.
I will see you next time.
Until then, keep coding!