Binary Search Tree

So its been a while !
I am currently studying for a course that will introduce me to 3D engines, networking and multi threading.

What I’ve been taught this week has blown me away so far so I’ll go through one subject which interested me.

Binary search trees.

So currently I haven’t really started on doing the assignment but I would love to tell you everything I know about BST’s.

Binary search trees or BST is a system for listing certain variables be it string, integers or floats in a way you can search through them in an effective manner.

Each object in this “tree” is called a node. A node carries with it a value(lets say an integer value) with a pointer that points to another node that either has a smaller value or a higher, these are called child or “leafs”; nodes without any children.

So nodes with children are called branches and nodes without are called leafs. Every node has a value an a pointer that points to a child with either a higher value or a smaller. These are then divided as well just the same, branches and children until you finally get to the leafs.

A setup can look like this.

Node(1)
/
Node(2)
/
/ Node(3)
RootNode(4)
Node(5)
/
Node(6)

Node(7)

The root node is the first node to be created, its from there all the others are designed.

Now!
The assignment need to have a class created in a way that you can easily search between the tree, remove unwanted nodes and print them out in different fashions.

We were taught today on how to do these so I’ll try my best to actually explain these, please do not use this as a reference as its only my interpretation of the lecture not religious text.

To search the tree for lets say value[5] it will first go to the root node and ask

“does this node have value 5?”
-no

is it bigger or smaller than 5?
-smaller

does the node point to a higher valued node? (just to send an error “cannot find value 5″)
-yes

The program then goes to node with the value of 6 and asks the same thing until it finally find the node and return the nodes value.

Unto deleting!

same thing then, you find the value by asking the questions and navigating to the node and delete the value.

But what if your destroying a value that has some children that needs to be re binded so they are connected.
You need to first look at its children and find the lowest value and point it just like any branch node to the rest of them, taking the place of the node you removed.

NOW UNTO PRINTING IN DIFFERENT FASHION!

So there are a few ways of printing your values in the BST.

Node(1)
/
Node(2)
/
/ Node(3)
RootNode(4)
Node(5)
/
Node(6)

Node(7)

One way would be to look for the lowest leaf then work yourself up from there.
So when you find [1] you go up to its parent [2] then see if it points to a higher value and take that and so on until you’ve seen those then start moving upwards to the root node again. The program starts to do the same with the higher valued node(higher than the node)

Now this is basically what I’ve learned this week in programming. Do not ask me why we always start with the lowest, its just a way to do it. There are tons of different ways I am sure.
Another thing is why I only pointed out one way to print them as well, well its because I cannot explain the others atm.

One thing I would like to add is templates but I’ll probably do that next week when I’ve actually coded this assignment.

Stay true and much love,
Ladbon