BinarySearchTree Implementation

HelloWorld · #1 (**permalink**) 08-03-2007, 05:22 PM

I'm currently working on my "Own" implementation for BinarySearchTree. I'm still trying to figure out how can I check each branch before getting into the programming part... Can anybody give me some suggestions on how should I implement the searching part?

I'm going to implement:
1. Insert
2. Remove

I'm still trying to design the insert part

for some reason it's getting complicated lol... I'm stucked into an endless loop...

Bench · #2 (**permalink**) 08-03-2007, 06:25 PM

Here's some pseudocode for an insert.. Binary trees are very difficult without recursion, so if you're trying to do it with a while or for loop, then you're in for an interesting time.

Code:

Begin Method: Insert(Tree, NewNode)
    if ( NewNode.data < Tree.data ) Then
        If ( Tree.left is NULL ) Then
            Tree.left = NewNode
        Else
            Insert( Tree.left, NewNode)
        End If

    Else if ( NewNode.data > Tree.data ) Then
        If ( Tree.right is NULL ) Then
            Tree.right = NewNode
        Else
            Insert( Tree.right, NewNode)
        End If
    End If
End Method 


Begin Method: Grow(Data)
    NewNode = New Node(Data)
    If ( Root is NULL ) Then
        Root = NewNode
    Else
        Insert( Root, NewNode )
    End If
End Method

HelloWorld · #3 (**permalink**) 08-03-2007, 06:54 PM

Quote:

Here's some pseudocode for an insert.. Binary trees are very difficult without recursion, so if you're trying to do it with a while or for loop, then you're in for an interesting time.

damn, no wonder lol... I'm stuck!!!! thanx a lot Bench

Edit: Btw, I'm not trying to do Binary Tree, but Binary Search Trees. No wonder your psuedo code looks much simpler than I've thought

HelloWorld · #4 (**permalink**) 08-03-2007, 09:08 PM

I found the solution for insert after a little bit of thinking and design in on paper. Although I'm not exactly sure whether this is the correct, but it works and seems correct to me

here's the pseudo code for it:

Code:

/* assuming that root is the constructor of BinarySearchTree
that inherits from the BinaryTree or however you implement it.
Keep in mind that root is a BinaryNode */
If Node < Root
     While Root.GetLeft != Null
             If Node < Root.GetLeft
                     // Set the Left Node of Root
             Else If Node > Root.GetLeft
                     // Set the Right Node of Root
     Root = Root.GetLeft
     End While
Else if Node > Root
     While Root.GetRight != Null
             If Node < Root.GetRight
                    // Set the Left Node of Root
             Else If Node > Root.GetRight
                   // Set the Right Node of Root
      Root = Root.GetRight
      End While
EndIf
End

Tell me what you think?

Edit: After I tested this, I think there's something wrong at this line

Code:

Root = Root.GetRight

and

Code:

Root = Root.GetLeft

But I need to somehow change the root in a real time so that it can compare when it's getRight or getLeft though

Bench · #5 (**permalink**) 08-04-2007, 06:17 AM

Quote:

Originally Posted by HelloWorld

But I need to somehow change the root in a real time so that it can compare when it's getRight or getLeft though

I'm not sure what you meant by the root being the constructor, although I think you've just discovered why while-loops don't cut the mustard. As I hinted at before, recursion is really the only elegant way to do these kinds of operations.

the pseudocode I posted is for a Binary search tree (try it). Binary search trees are deceptively simple - based on the mathematical concept of a binary search. In fact, they're far more difficult to explain than to create.
The best analogy I can think of is looking up a word in a dictionary, by starting in the middle, and eliminating half the remaining dictionary at a time - your "root node" is always whatever portion of the dictionary remains at each dictionary-traversal.

Here's some traversal psuedocode for the binary search tree. Again, really simple, but it works a treat.

Code:

Begin Method: In_Order_Traversal( Root )
    If( Root is not NULL )
        In_Order_Traversal( Root.left )
        Write( Root.data )
        In_Order_Traversal( Root.right )
    End If
End Method

Recursion perhaps isn't the most naturally easy concept to visualise - For a BSTree, it involves two "jumps" at each node (and generally not one-after-the-other, unless the node is a 'leaf' - ie, left and right are NULL), so it doesn't fit any ordinary looking flowcharts. Any accurate flow chart can only end up looking like the schematic of the BSTree itself.

HelloWorld · #6 (**permalink**) 08-05-2007, 12:19 PM

Here's the last code that I got for "insert" implementation, please take a look and see if there's anything wrong. For some reason, I don't get ordered number when I did "inorder" to my BinarySearchTrees

PHP Code:

      public void insert(BinaryNode node) {
        BinaryNode n = this.root;
        if (Double.parseDouble(node.getValue().toString()) < Double.parseDouble(n.getValue().toString())) {
            while (n != null) {
                if (Double.parseDouble(node.getValue().toString()) < Double.parseDouble(n.getValue().toString()) && n.getLeft() == null) {
                    n.setLeft(node);
                } else if (Double.parseDouble(node.getValue().toString()) > Double.parseDouble(n.getValue().toString()) && n.getRight() == null) {
                    n.setRight(node);
                }
                n = n.getLeft();
            }
        } else if (Double.parseDouble(node.getValue().toString()) > Double.parseDouble(n.getValue().toString())) {
            while (n != null) {
                if (Double.parseDouble(node.getValue().toString()) > Double.parseDouble(n.getValue().toString()) && n.getRight() == null) {
                    n.setRight(node);
                } else if (Double.parseDouble(node.getValue().toString()) < Double.parseDouble(n.getValue().toString()) && n.getLeft() == null) {
                    n.setLeft(node);
                }
                n = n.getRight();
            }
        } else {
            System.out.println("SAME NUMBER EXCEPTION!");
        }
    }

here's the inorder implementation

PHP Code:

      public void inorder(BinaryNode node) {
        if (node == null) {
            return;
        }
        inorder(node.getLeft());
        System.out.println(node.getValue()); // visit the code
        inorder(node.getRight());
    }

Bench · #7 (**permalink**) 08-05-2007, 01:09 PM

Your inorder looks good. I can see that you insist on using a while loop for this.

Recursion causes the entire function to become one loop, what you seem to have done is broken it into half with 2 loops - therefore your function as it is will only traverse down one side of the loop or the other

try something like this (Without having your BinaryNode implementation, I made my own simplified version to test this one using a built-in type rather than a Double)

Code:

    public void Insert(BinaryNode node)
    {
        BinaryNode n = this.root;
        while( n != null )
        {
            if (node.data < n.data) 
            {
                if (n.left == null)
                {
                    n.left = node;
                    return;
                }
                else
                    n = n.left;
            }
            else if (node.data > n.data)
            {
                if (n.right == null)
                {
                    n.right = node;
                    return;
                }
                else
                    n = n.right;
            }
        }
    }

HelloWorld · #8 (**permalink**) 08-05-2007, 01:24 PM

Bench, truly.. I'm kind of confused with recursion method, probably I need some practice to read recursion more

can you please explain what happened to my inorder method?
Let's say the inputs are: 5, 2, 9, 1, 3, 11

PHP Code:

      public void inorder(BinaryNode node) {
        if (node == null) {
            return;
        }
        inorder(node.getLeft());
        System.out.println(node.getValue()); // visit the code
        inorder(node.getRight());
    }

I fixed the problem already lol, just forgot return; in each of the if statement within the while loop, that causes set the number 3 both on the right side of 1 and 2

Bench · #9 (**permalink**) 08-05-2007, 02:01 PM

Recursion causes multiple different calls of the same function to be placed on a stack frame. Each call to the function relies on the previous call beneath it on the stack frame for input, and returns to the previous call after its finished. In effect, each function call is like a new dependent object.

if your inputs are in the order of 5, 2, 9, 1, 3, 11, then your BSTree will look like this (Sorry for the crude Text-art)

Code:

                           5
                   _______/ \_______
                  2                 9
          _______/ \_______          \_______
         1                 3                 11

The root node is "5" (Referring to each node by its data contents), So, for an in-order traversal which outputs the above tree to the console window, the process goes a bit like this. Assuming a new, empty, stack frame:

The first function pushed on to the stack frame is inorder( "5" )

when inorder("5") runs, its first statement calls inorder("5".left) which is inorder("2")

when inorder("2") runs, its first statement calls inorder("2".left) which is inorder("1")

when inorder("1") runs, its first statement calls inorder("1".left) which is inorder(NULL)

the stack frame now looks like

Code:

-top-
  inorder(NULL)
  inorder("1")
  inorder("2")
  inorder("5")
-bottom-

Note, that at this point no output has been sent to the console window, all we've done is execute the first statement of each function (Well, actually we've checked to make sure they're not NULL too, but that's a minor detail). Each of which has caused a new function to be added to the stack.

At all times, the active function is the function at the top of the stack frame

Next, inorder(NULL) returns. This removes it from the stack frame, leaving inorder("1") back at the top. Inorder("1") must take up from where it left off, so the next statement is

Code:

  System.out.println("1");

after that, it calls inorder("1".right) which is also inorder(NULL).

Finally, inorder("1") is finished, and can be removed from the stack frame.

the function at the top is now inorder("2"). it has already completed inorder("2".left), so it moves onto the next statement

Code:

  System.out.println("2");

Then, it moves on to the next statement, inorder("2".right), which, on our schematic is inorder("3")... Now the stack frame looks like

Code:

-top-
  inorder("3")
  inorder("2")
  inorder("5")
-bottom-

and so on, so forth. Just to re-iterate, that the active function is always the one at the top. the ones lower down are 'hanging in wait' from the moment that a new function call is pushed to the top of the stack, until the moment that function call returns.

HelloWorld · #10 (**permalink**) 08-05-2007, 02:28 PM

Thanx a lot Bench
I'm now working on the remove() implementation for BinarySearchTrees, it's weird that I can't set anything unless if I'm using this.root directly instead of referenced it to n. I can see why, but if I update the value based on the this.root, it will remove the root right away

I'm looking on solution into remove() implementation

I tested this doesn't work:

PHP Code:

      public void remove() {
        BinaryNode n = this.root;
        n = null;
    }

However, this one works:

PHP Code:

      public void remove() {
        this.root = null;
    }

sigh.. I need some idea to get the updated root

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

The Following User Says Thank You to Bench For This Useful Post:
HelloWorld (08-03-2007)

The Following User Says Thank You to Bench For This Useful Post:
HelloWorld (08-04-2007)

The Following User Says Thank You to Bench For This Useful Post:
HelloWorld (08-05-2007)