So, we’ve started out with a new Game Programming course, called Game programming III. We’ll be focusing on 3D programming this time around.
So, let’s have a little chat about something I’ve studied this week:
I’ve started looking at our first assignment, which is to create a binary search tree using C++. (I’ll be writing this to help me understand how a Binary Search Tree works myself, whilst also hopefully help anyone reading this understand it as well)
What is a binary search tree, and how does it work?
A binary search tree is a node based data structure that categorizes each node after their size on a left (the smaller size) and a right side (the larger size). Each node has two child nodes, one smaller (left side) and one larger (right side).
Each time a new node allocated to the tree, it first looks at the root value: Is it larger or smaller than the root value? If it is, go to the right side node. If not, go to the left side node. Secondly, it checks again is it larger or smaller than the child of the root? If it is, go to the right side. etc.
Here’s an example:
So let’s use letters for this example; if we were to introduce, let’s say Z to the tree (assuming A has the value of 1, and B the value of 2 etc.), we first check,
Is it larger than the root, F? It is, so let’s go down the right side child of F.
Is it larger than G? It is, so let’s go down to the right side child of G.
Is it larger than I? It is, so let’s add it as a new right hand child of I.
The tree would now look like this:
The assignment requires us to create the following methods: insert, erase, search, size,
traversal_pre_order, traversal_in_order and traversal_post_order.
As I’m still just starting out with this assignment, let’s have a quick look at how to create an insert method:
So I’ve started out by defining what my method should do:
- Check if we have a root node. If not, we have to create a root node.
- If the element we want to inser is less than the element in the root node, go down the left sub-tree until the element becomes a child of another node.
- If the element we want to inser is greaterthan the element in the root node, go down to the right sub-tree until the element becomes a child of another node
Now, what if we want to insert an Element that has the same size as the Root? The element has to be ignored.
How about deletion?
This is what I’m currently trying to wrap my head around, as there is at least three cases we have to consider before deleting a node, Nodes with no children, Nodes with one child and Nodes with two Children (look at the example above, Z has no children, D has two children, etc).
This means that removing a node with no childs is quite simple, by just removing the pointer from any element linked to it, whilst when you have to delete a node with a child (that sounds morbid come to think about it), we have to re-point the value of the element we want to deletes child to the root of the element.
Example:
Deleting the letter I:
That’s it for now. I’ve been busy writing a new concept document all week, and I’m still trying to wrap my head around this subject (I haven’t programmed for months!). Anyway, that’s a small introduction to Binary Search trees.
Perkulatorn's Game Design Blog 