Welcome!

Join our community of MMO enthusiasts and game developers! By registering, you'll gain access to discussions on the latest developments in MMO server files and collaborate with like-minded individuals. Join us today and unlock the potential of MMO server development!

Join Today!

[tut]Understanding and Making a Binary Search Tree

Newbie Spellweaver
Joined
Nov 25, 2006
Messages
52
Reaction score
0
Understanding and Making a Binary Search Tree

This is probably more of a Java Tutorial, But this could be used here. Also, I suggest you know a thing or two about Java before you try this.

So, I felt like it was about time I did another tutorial, This one will be a little more Advanced. I like to keep my tutorials more Concept rather than Objective, Meaning, I want you to learn something, not just make something happen.

So, with that said, Lets get some background knowledge on what exactly a 'Tree' is. A Tree is a data structure. It consists of many 'Nodes', in a Binary Tree, each Node has two things, A Value, and Two child Nodes. When you Populate the Data Structure, It ends up looking like an upside down Tree, that's where it got its name.


Here is a Balanced Tree, Balanced meaning every node has both of its child nodes.

meiscooldude - [tut]Understanding and Making a Binary Search Tree - RaGEZONE Forums


Tree's do NOT have to be balanced, Although they preform much better when they are.

Ok, So, now that we know what exactly a tree looks like, Lets look into some rules for inserting values into a Binary Search Tree,

Well, Lets say we want to insert a Value into a Tree who only has a Root Node, and The Root node has a value of 4, and we want to insert 2. Well, because 2 is less than 4, it goes into the Left Node. But if we were to insert 6, it would go into the Right Node. And if we were to try and Insert 4, It would not be inserted at all. But keep in mind that the rules are different for each type of Tree.

Now, You must notice that Tree's are a VERY recursive structure. Recursive meaning that its methods call themselfs, Like so, Here is a very useful Factorial Method:

Code:
    public static int factorial(int i)
    {
        if(i <= 1)
            return 1;
        
        return i * factorial(i-1);
    }

As you can see, Recursion makes it so we can do ALOT in very few lines of code. Although there is a downfall to recursion, If it fails to stop calling itself, you will get a stack overflow exception.


So, now we understand the basic rules of a Tree, and we understand that it uses recursion, and that it can be very powerful.

Lets create a new Class called 'BinarySearchTree',

It will have 2 public members, Add and Search, Add will add a value to the Tree, and Search will tell you if the tree contains a value. And 2 private members, a TreeNode Class, and a TreeNode Object.

Code:
public class BinarySearchTree
{
    public BinarySearchTree()
    {
        rootNode = null;
    }
    
    public void add(int a)
    {
        
    }
    
    public boolean search(int s)
    {
            return false;
    }

    private TreeNode rootNode;

    private class TreeNode
    {
        
    }
}


For now, Lets focus on the TreeNode Class,

Like we said above, each Node must have a Left and a Right node, But we don't want to initialize them when we create a new Node, because we would run out of memory fairly fast. So lets just declare them for now. And lets go ahead and create an int to store our Value.

Code:
    private class TreeNode
    {
        
        private TreeNode left;
        private TreeNode right;
        private int value;
        
    }

Now, I don't know if I said this, but each Node must have a Search and Add Method, that way we can use Recursion. We are also going to need a constructor that allows you to set the value of the node on initialization. So lets add them now.

Code:
    private class TreeNode
    {
        public TreeNode (int v)
        {
            value = v;
            left = null;
            right = null;
        }

        public void add(int a)
        {

        }
        
        public boolean search(int s)
        {
            return false;
        }
        
        
        private TreeNode left;
        private TreeNode right;
        private int value;
        
    }

Now, Lets work on our Add Method, We know that if we add a Node that has a value less that its value, the node to be added goes into the left, and vice versa.

So, Lets add some code that does that,

Code:
    public void add(int a)
    {
        if(a > value) //if the given value is greater than the current value, it goes in the right.
        {
            if(right == null) //if no right Node exists, create one.
                right = new TreeNode(a);
            else
                right.add(a); //call the add method of the right node if it exists.
        }
        else if(a < value) //ect.....
        {
            if(left == null)
                left = new TreeNode(a);
            else
                left.add(a);
        }
    }

I commented my code to help explain what exactly is going on, once again, you should have a strong understanding of java to understand this tutorial.

Ok, Sweet, so we added an 'add' method, so now lets focus on the Search method,

Code:
        public boolean search(int s)
        {
            if(s == value) // if the value of this node is the value you are searching for, return true
                return true;

            // if the value you are searching for is greater than the
            //current node value, search to the right
            else if(s > value) 
            {
                if(right == null) // if there is no right node, the value does not exist
                    return false;
                
                return right.search(s); // search in the right node
            }
            else //ect...
            {
                if(left == null)
                    return false;
                
                return left.search(s);
            }
        }

That is all you need to add to your TreeNode Class.

Now, Lets go back to our BinarySearchTree Class, But before we do, You should have a pretty clear understanding of what is going to go on, If you don't, I suggest you write what is going on in the code on paper, It makes things much easier, trust me.

Alright, Like i Said, Our BinarySearchTree is going to have the Search and Add Methods, So here they are, Only 3 lines of code, Hopefully I should'nt have to explain what they do. :)


Code:
    public void add(int a)
    {
        if(rootNode == null)
            rootNode = new TreeNode (a);
        else
            rootNode.add(a);
    }
    
    public boolean search(int s)
    {
        if(rootNode == null)
            return false;
        
        return rootNode.search(s);
    }



So, Lets create a Little Test Application for this Binary Search Tree.

Code:
public class Test
{
    public static void main(String args[])
    {
        //we create a new Binary Search Tree
        BinarySearchTree bst = new BinarySearchTree();

        //we start adding values to it
        bst.add(256);
        bst.add(256);
        bst.add(405);
        bst.add(223);

        //we search for a value of 1, it returns false
        System.out.println(bst.search(1));

        //we search for a value of 223, it returns true
        System.out.println(bst.search(223));


    }
}

It will generate the following output:

Code:
false
true

Sweet, there you go, Your first Binary Search Tree.

But we are not done teaching you yet. You probably are asking, Why use this, This seems too complicated to do a search, Well your right, with very few values a Binary Search Tree is very Pointless. But lets say its populated with 200,000 integers, We could search a list, and a list searches by looping, so we would have do 199,999 look ups, Thats expensive. But with a Binary Search Tree, should there be 200,000, (if the tree is balanced) the worst case search would take O(log(n)), Thats only about 15-16 look ups, Thats quite a bit better, Right? (I hope my math is right)

Although, Adds on Tree's are quite a bit more expensive than on a List or an Array.

But thats that, There is my Tutorial.


Integration: I bet you can find a way to integrate a Tree with an Item List or NPC's, Speed things up why don't we ? :p
 
There's no RL just AFK
Loyal Member
Joined
May 2, 2006
Messages
473
Reaction score
6
Very interesting tutorial mate, although i still cannot create a reason in my head as of now (midnight) to use it with, as i believe having an npc/item list searched would be more efficient with SQL.

Still very intrequing, someone in my CS class (a year above me) was covering a subject similar to this but using VB, now i know what it is he was doing.
 
Newbie Spellweaver
Joined
Nov 25, 2006
Messages
52
Reaction score
0
Well, most modern databases use Tree's, Thats why look ups are so fast on SQL Databases.
 
Back
Top