BinarySearchTree Implementation - Page 2

Bench · #11 (**permalink**) 08-05-2007, 04:10 PM

I take it to mean that you're confident with your insert now? (Your inorder function looked fine). Obviously, if the insert has any problems, the likelyhood is that the rest will fall apart too.

The delete algorithm is a bit more complicated, since the method of removing a node depends on the number of 'children' that node has (one, two, or none).

If you're still wrapping your head around recursion, try making a 'find' method, or, maybe something unrelated to the BST (in general, any 'while' loop can be rearranged as a recursive loop some way or another)

HelloWorld · #12 (**permalink**) 08-05-2007, 04:51 PM

Quote:

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

That part is the most confusing to me, since it returns, doesn't that meant hat it should be getting out from the method itself? How can it pick up from where it left off?

#13 (**permalink**) 08-05-2007, 05:01 PM

Don't know if this will help but wikipedia has some C++ code for deletion.

Binary search tree - Wikipedia, the free encyclopedia

Best of luck on your coding.

HelloWorld · #14 (**permalink**) 08-05-2007, 05:20 PM

Quote:

Originally Posted by Leech

Don't know if this will help but wikipedia has some C++ code for deletion.

Binary search tree - Wikipedia, the free encyclopedia

Best of luck on your coding.

LOL Leech,
I appreciate that. Unfortunately,
1. I've been there
2. I've been to many places that gives example, but most of them uses Comparable, which something that I don't want to use for now to keep it simpler. (if this is even possible)
3. I've been Googling

Quote:

I take it to mean that you're confident with your insert now? (Your inorder function looked fine). Obviously, if the insert has any problems, the likelyhood is that the rest will fall apart too.

The delete algorithm is a bit more complicated, since the method of removing a node depends on the number of 'children' that node has (one, two, or none).

If you're still wrapping your head around recursion, try making a 'find' method, or, maybe something unrelated to the BST (in general, any 'while' loop can be rearranged as a recursive loop some way or another)

Yes, I finished implementing the new one, I forgot return;

Bench · #15 (**permalink**) 08-05-2007, 06:02 PM

Quote:

Originally Posted by HelloWorld

That part is the most confusing to me, since it returns, doesn't that meant hat it should be getting out from the method itself? How can it pick up from where it left off?

I'd like to elaborate on something I mentioned in my previous post

Quote:

Originally Posted by Bench

Recursion causes multiple different calls of the same function to be placed on a stack frame.

In other words, recursion causes multiple instances of a method-call to be created. In this context, it would be sensible to think of a method-call as an object with a presence in memory.. or at least, on the stack frame, which will be active in memory somewhere, recording the state of individual method-calls.

You can think of a Method/function as a Named block of code. Its almost like meta-programming, where a single-line method-call is replaced by the contents of that entire method.

for example, here's a program with some nested method calls. Exactly the same thing happens with the stack frame as the recursive calls before, just with different methods.

PHP Code:

  public static void DoSomething()
{
    System.out.println("DoSomething is added on-top of the stack frame");
}

public static void SomeMethod()
{
    System.out.println("SomeMethod is added on-top of the stack frame");
    DoSomething();
    System.out.println("SomeMethod at the top again");
}

public static void main(String args[])
{
    System.out.println("main is at the top of the stack frame");
    SomeMethod();
    System.out.println("main is at the top of the stack frame again");
}

If you un-rolled the stack frame in-to main, the program would look like this

PHP Code:

  public static void main(String args[])
{
   System.out.println("main is at the top of the stack frame");

      //Begin SomeMethod()
      System.out.println("SomeMethod is added on-top of the stack frame");
         //Begin DoSomething()
         System.out.println("DoSomething is added on-top of the stack frame");
         //End DoSomething()
      System.out.println("SomeMethod at the top again");
      //End SomeMethod()

   System.out.println("main is at the top of the stack frame again");

at the point when DoSomething() is called, the stack frame looks like this

Code:

-top-
  DoSomething()
  SomeMethod()
  main()
-bottom-

If you run the program, you should be able to see that when DoSomething() ends, the function returns to the point in SomeMethod() where DoSomething() was called from. Because SomeMethod is temporarily 'frozen', with its state recorded on the stack frame - therefore, it picks up where it left off when it becomes active again