• Post Reply Bookmark Topic Watch Topic
  • New Topic

Binary Search Tree  RSS feed

 
tom davies
Ranch Hand
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am creating a binary search tree, the tree will be a random size up to 10 000. I am adding nodes to create the tree so that the total equals this random number. I am also assigning a random number to each node between the random size. So if the size is 1000, i would want the numbers 1-1000 randomly distributed among the nodes. I can do this, but i don't want to repeat any of the numbers. What is the best way to check if i have any duplicates before adding? The usual way to search a binary search tree is if the number you want is higher than the current node you would go to the right, else you would go to the left. That wont work in this situation as the values are randomly distributed and have no relation to the node number.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is the best way to check if i have any duplicates before adding?

The best way to get a fixed range of values, all represented exactly once, is to first create the values in a collection (for example List<Integer>) then 'shuffle' the collection so they are in random order. Then pull out the values in the order the shuffle leaves them. The easiest way to shuffle a collection is to use the java.util.Collections#shuffle(List) method.

Another route would be to fill a list with the values you want, and sequentially generate a random index in the range of 0 to list.size(), retrieve the value at index, then remove the value at index (so even though the index may repeat itself randomly, the result pulled from the list never does. Obviously the list will shrink so you would have to calculate the range of the random number each loop.

The usual way to search a binary search tree is if the number you want is higher than the current node you would go to the right, else you would go to the left. That wont work in this situation as the values are randomly distributed

Which brings to question the usefulness of your 'binary search tree' if it can't be used for effective binary searching.
 
tom davies
Ranch Hand
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks, i think i could work using those two suggestions.

Also its a comparison exercise between sorted and unsorted so i am aware of that yes
 
Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is the best way to check if i have any duplicates before adding?

just see the value is already there .. it takes just O(n) time . if you want better than this then go for red-black tree(if you really have too many objects) which takes O(logn)
best way: use hashing technique such as Hashtable or HashMap
 
tom davies
Ranch Hand
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Seetharaman Venkatasamy wrote:
What is the best way to check if i have any duplicates before adding?

just see the value is already there .. it takes just O(n) time . if you want better than this then go for red-black tree(if you really have too many objects) which takes O(logn)
best way: use hashing technique such as Hashtable or HashMap

The problem was i wasn't sure how to search the whole tree to find the value. I would of had to search the entire tree every time i added a new node as well, so if it was 10 000 nodes that would be a lot of searching just to add 1 extra node. I have created a list of integers using the tree size and used collection.shuffle, then when i add a new node i just use the number at that index in the list which seems to work well.

Each node is now assigned a random value between 1 and the tree size. I now want to pick a random number between this size and find the node that contains this value. I am trying to do a in order traversal but it is not returning what i had hoped. I have added a counter with a println statement to see how many times the loop is run.
I have also added println to show the tree size and the number to find in the tree.
My counter shows that my method runs the same amount of times as there is nodes in the tree. There is clearly something wrong with my method not locating the value. Below is my method.

 
Suresh Sajja
Ranch Hand
Posts: 34
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

you need to revise your algorithm for searching BST



Please refer to Binary_search_tree
 
tom davies
Ranch Hand
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That would work for an ordinary binary search tree but the values within my nodes are not ordered. The nodes themselves are ordered,but the values within, that i want to find, have been shuffled as mentioned in the previous posts. This means that traversing to left tree wouldn't nescasarily bring me to a lower value and help my search. What I need to be able to do is traverse the entire tree and check each node until I find the value I want.
Do I understand that correctly?
 
Suresh Sajja
Ranch Hand
Posts: 34
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
tom davies wrote:That would work for an ordinary binary search tree but the values within my nodes are not ordered. The nodes themselves are ordered,but the values within, that i want to find, have been shuffled as mentioned in the previous posts. This means that traversing to left tree wouldn't nescasarily bring me to a lower value and help my search. What I need to be able to do is traverse the entire tree and check each node until I find the value I want.
Do I understand that correctly?


I am confused, by what means nodes are ordered? Do you have other properties?
 
Suresh Sajja
Ranch Hand
Posts: 34
Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
tom davies wrote:



Once you find current, you are not returning or printing anything. May be this is the issue with your code.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Suresh Sajja wrote:
tom davies wrote:



Once you find current, you are not returning or printing anything. May be this is the issue with your code.


Exactly. The if{} statement Suresh quoted actually has no effect, because current is set to node for the if is evaluated.

when you write a recursive mode the first thing you need to define is the case in which the recursion stops. In your case there are two cases where the recursion should stop:
1) when the object is found
2) when there are no more nodes to search.

The pseudocode would be something like:
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
tom davies wrote:. . . The nodes themselves are ordered,but the values within, that i want to find, have been shuffled . . .
If you have a proper binary search tree, your nodes will have reasserted the sorting. When you populate such a tree, the entire collection is sorted, because all the values position themselves relative to one another depending on their values, each testing they are greater or smaller than each other. Such a tree is usually a (sorted) set implementation because the second of two identical values is usually not added.
 
tom davies
Ranch Hand
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you, that seems obvious now, I don't know why I didn't work that out myself.
Campbell Ritchie, my tree nodes each have a key and a value assigned to them. When the tree is created I use the key value to determine their position so they are sorted by key. Each node has a random value assigned to it, so it's not possible to do the usual efficient searching algorithm of the binary tree. This tree has no practical purpose but its to demonstrate against a sorted tree which is more efficient and by how much
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaah!

A case of…You can implement the IJustWantedToSeeWhatHappensIf interface in any app when you are learning, possibly only stopping short of deleting system files.
 
tom davies
Ranch Hand
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yep thats it Campbell ha.
I have what seems to be a working method now
The method i am using is below.

And this is the output is below.

Value = 4205
Number to find :> 4205 size of tree = 8588

This seems fine, and it is finding the value, but i had a print statement outside the loop just before return false;
After the value has been found there are hundreds of println's . . . . I thought the only time i would get to that point would be if the value was not found, and it should stop then anyway when it reaches return false;?
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
tom davies wrote:I thought the only time i would get to that point would be if the value was not found, and it should stop then anyway when it reaches return false;?


If you find the value on the left side of the node, the method doesn't stop - it will still search on the right side of the node. And if it finds the value on the right side of the node it would still finish execution and return false. So essentially, you now print out when the value is found, but continue to search every node and never pass a signal to the caller that the value was actually found. You need to consider the cases when the value is found on either the right or left side so you don't waste time, execute code which shouldn't be, and return the wrong signal to the caller.
 
Suresh Sajja
Ranch Hand
Posts: 34
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It is the order of execution in a recursive function.
Please refer to wiki page here. Order of execution in recursion
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You would expect a printout for every node in your tree. You can reduce that method in size, and this technique also gets rid of multiple returns.Again, it is recursive, and I have in this instance assumed value is a reference type under the formal type parameter V. This method will not seek multiple instances of v.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!