binary search trees

Hello there,

I need 2 learn binary search tree 4 my assinement in java but canot find anything useful.

If anyone no of a useful link please tell me. Why is there no source code for deleting a node...that's all i ask how to delete a freaking node arg. :eek:

[jwenting]

in a binary tree every branch has 2 branches leading from it (ok, in reality it could be one but I'm taking the perfectly ballanced tree here).
It's therefore impossible to remove a node without rebuilding the entire tree, as just linking the children of that node to the parent of the removed node would mean you now don't have a binary tree anymore.
You could remove the entire branch, but then your tree would no longer be ballanced.

If you want that you can simply remove the reference to the element at the top of the branch you're removing from its parent node and it's gone.

There are tons of examples of trees online, though most may be in C or C++.
Look for artificial intelligence, path finding algorithms, things like that.

thank u jwenting.

Yes I meant to say rebuild the tree as well upon deletion of the node. I know tutorials exist in c/c++ but I would looking for a really good one in java.

They tell me how to do all the other things, traverse a tree in pre/post/in order, insert nodes and just about everything else.

But, I'm guessing due to it's complicated nature, they leave out deletion. If u or anyone else could provide a link i wud b so greatful.

:cry:

My assinement requires me to add names of students to a binary tree then sort then in alphabetical order. And then ask the user to delete one name whilst still retaining the inherent structure of a binary search tree.

God bless.

[jwenting]

Deletion is usually left out because it constitutes recreating the tree minus the deleted element, and therefore is no different from building a new tree from scratch (or more likely by moving branches to different positions in the tree until the tree is once again ballanced).

Examples in C and C++ should be no problem for someone who's at the stage of more complicated data structures than an array or single linked list, you should really know enough to at least understand them by now (I regularly read books using examples in languages I've no experience in, it's a good mental exercise).

The principles and algorithms are the same after all, except in Java you don't have to mess with all that dereferencing pointers because you have references and can reference those directly ;)

Best way to sort them is to do an insertion sort, sorting them during insertion. If that leaves the tree unballanced, you can then ballance sections of the tree until the entire thing is ballanced (copying entire branches to fall under other branches).

I've not much experience with trees in my line of work (Maps and Lists are far more common in most fields, and if a tree is needed a TreeSet will let me use a built in tree through a Set interface).
But that's the theory at least in a nutshell.

Hullo,

I've followed your advice by looking at the algorithm for deletion. Ur right regardless of the language the implementation should be similar.

Here's what I've broken it down to.

For the sake of brevity I am using integers to illustrate my point, however, in my actual assinement I will need to use actual names. Since the names will be cast as strings, direct comparison of their size will be possible. By size I mean, alphabetical precidance.

Most of this i red of the net:

Deletion

The algorithm must ensure that when the node is deleted from the tree, the ordering of the binary tree is kept intact.

Special Cases that have to be considered:

1)The node to be deleted has no children.

In this case the node may simply be deleted from the tree.

Before deletion of 2

       3
      / \
     2   7

After deletion of 2

       3
        \
         7

2)The node has one child.

The child node is appended to the parent of the node to be deleted.

Before deletion of 2

       4
      / \
     2   7
     \
      3

After deletion of 2

       4
      / \
     3   7

3)The node to be deleted has two children.

The algorithm must determine which node to use in place of the node to be deleted:

i)Use the inorder successor of the node to be deleted.

Before Deletion of 5

              7
             / \
            5   8
           / \
          3   6
         /   /
        1   4

After deletion of 5
              7
             / \
            4   8
           / \
          3   6
         /   
        1

ii)Else if no right subtree exists replace the node to be deleted with the it's left child.

Deletion before 5

              7
             / \
            5   8
           / \
          3   6
         /   
        1

Deletion after 5

             7
            / \
           3   8
          / \
         1   6

Deletion of the root node is also a special case. I think.

And that's it. Although the integers would be names instead.

Best way to sort them is to do an insertion sort, sorting them during insertion.

I think the whole idea of my teacher giving me this assinement is to show that the names can be sorted in alphabetical order using 'in-order' traversal, or at least that what I was assuming.

I've not much experience with trees in my line of work

Perhaps it's time to dust of those books and help me out. ;)

How would I put that into code?

[jwenting]

first and second case are easy, first you just null the reference, second you replace the reference with the only child it has.

Third you determine the node to move up one spot and set one of its children to the other node that was a child of the deleted node.
You then reorder that entire branche.
If the node you're moving up has an empty child that's easy as there's nothing to do, if it has children those will start to move down.

[wimper]

Hello. See binary search tutorial.

[stultuske]

Hello. See binary search tutorial.

if you're not capable of reading and interpreting date's, don't bother to go check about binary search trees.

there's no need to revive threads that haven't been open for two years

[wimper]

Actually I didn't notice, that the thread is too old. Quite sorry for that.

[stultuske]

if it's not on page 1 or maybe 2, you may consider it to be old, or inactive, to give a better description

[wimper]

I do get here from Google :-)

[kdc]

Thanks! Very Helpful!