Forums Register Login

Binary Search Tree

+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
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
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
 

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.

+Pie Number of slices to send: Send
Hi,

you need to revise your algorithm for searching BST



Please refer to Binary_search_tree
+Pie Number of slices to send: Send
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?
+Pie Number of slices to send: Send
 

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?
1
+Pie Number of slices to send: Send
 

tom davies wrote:



Once you find current, you are not returning or printing anything. May be this is the issue with your code.
1
+Pie Number of slices to send: Send
 

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:
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
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
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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;?
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
It is the order of execution in a recursive function.
Please refer to wiki page here. Order of execution in recursion
+Pie Number of slices to send: Send
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.
Then YOU must do the pig's work! Read this tiny ad. READ IT!
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com


reply
reply
This thread has been viewed 2050 times.
Similar Threads
Algorithm to find Nodes having largest distance in Binary tree.
Applying AVL algorithm to an unbalanced binary search tree
Sorting JTree Nodes alphabetically
Question about Tree Node
null pointer exception while closing a node of jtree
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 05:51:45.