Sorting: Ep 08a - Binary Trees


Uploaded by lcc0612 on 03.02.2010

Transcript:
Hello YouTube, and welcome back to sorting algorithms.
Well, we're not covering a sorting algorithm today - Instead we're going to talk about Binary Trees.
Now, in computing, there are many ways you can store data
Whether as isolated values, in an array or list, a two dimensional array
a linked list... The list goes on! One of these ways is to use a binary tree
The data is arranged in a hierachy of items in a tree structure.
The word "binary" means that every item in it, also known as "nodes" can have up to two child nodes.
This is how it works - The items are extracted from the list one by one, and we begin building the tree structure.
The first item forms the first node in the tree, also known as the "Root Node".
Further nodes are inserted into the tree based on this idea
A new item, if smaller than an existing item, goes to the left of it. Otherwise, it goes to the right.
The item keeps moving based on this rule down the tree, until eventually it moves to an empty slot, in which it will occupy.
There isn't much more to be said, so let us begin with the demonstration.
"6" is larger than "5", so it goes to its right
"9" is larger than "5", so it belongs to the right of "5".
However, the slot right of "5" is occupied, so the process starts again - Now, "9" is larger than "6" as well
so we move to the right of "6", and encounter an empty slot. That is where "9" belongs.
"3" is smaller than "5", it goes to the left.
"1" is smaller than both "5" and "3", so it goes all the way to the left.
"4" is smaller than "5", so it belongs left of "5", but it's more than "3", so it belongs to its right.
Get the picture now? Try to follow along with the thinking process without my voice-over as a guide.
And that's all for creating the tree. There is one more quirk here, which I will explain before we end off this episode.
You'll notice that on the right side of the tree, there are quite a few more items than there are on the left side.
To use a proper technical term, that means the tree is "unbalanced".
A balanced binary tree ideally has an equal distribution of nodes on either side of the root node.
Since this series isn't on binary trees, I'm not going into detail regarding balancing trees.
Suffice to say that there are a couple of conditions that can create rather amusingly distributed binary trees
uch as an improperly chosen root node, like so, or attempting to load a sorted list into a binary tree
which creates a linked list instead.
Not only do these conditions create seriously stunted trees, the insertion of newer items into the list
will also take a really long time, because it needs to pass through a lot of items before it can find its correct place.
will also take a really long time, because it needs to pass through a lot of items before it can find its correct place.
That's basically it for this episode.
In the next episode I'll tell you why on earth I'm talking about Binary trees in the first place.
I'll see you soon, you're watching 0612 TV.