Omnimaga

Calculator Community => Other Calc-Related Projects and Ideas => Topic started by: Halifax on February 02, 2007, 07:05:00 pm

Title: Binary Search Tree
Post by: Halifax on February 02, 2007, 07:05:00 pm
This would be very good for basic and ASM searching in lists. A binary search tree is very efficient but I don't know if it has been tried before? But it is suspected that if you had a number represent everyone in the world it would only take ~40 checks to find a match to the person you are looking for.

I was just wondering if it has been done before and if it would be good to implement in basic or ASM
Title: Binary Search Tree
Post by: trevmeister66 on February 03, 2007, 03:57:00 am
it sounds like a great idea, and i don't think i've ever heard of it ever being done before, so i say go for it!
Title: Binary Search Tree
Post by: rivereye on February 03, 2007, 05:29:00 am
actually, more like 33 searches, but it has to be all be in order you know (that 33 is for 6 billion people).
Title: Binary Search Tree
Post by: elfprince13 on February 03, 2007, 09:02:00 am
ummm, http://www.ticalc.org/archives/files/fileinfo/393/39374.html

I could have sworn I announced this on Omnimaga <_<dry.gif
Title: Binary Search Tree
Post by: Halifax on February 04, 2007, 08:53:00 am
Oh sorry elfprince I didn't remember you annoucing it but I will look at your source just to see. Also rivereye I know everything has to be sorted. I finished my search tree and it only takes 6 checks to find the rightmost value in a 999 dimension list so its pretty fast. One bug is when there is no value it goes into a continous loop so I need to fix that.
Title: Binary Search Tree
Post by: trevmeister66 on February 04, 2007, 09:49:00 am
yeah, that could be a problem. good job, though, on the 6 checks for 999 dimension list.
Title: Binary Search Tree
Post by: elfprince13 on February 04, 2007, 10:42:00 am
while we're at it:

http://www.ticalc.org/archives/files/fileinfo/393/39377.html

Title: Binary Search Tree
Post by: Halifax on February 05, 2007, 09:53:00 am
Funny you mention that I have been working on sorting too. I have currently been working on Insertion Sort and Lookup Sort and also a ternary tree search and another search I can't quite remember the name of anyways

did you just make that mergesort? its nice
Title: Binary Search Tree
Post by: elfprince13 on February 05, 2007, 10:11:00 am
MergeSort has been out for several months as has the BST....

and MergeSort is probably the most effective well known (and implementable on a calculator) sorting algorithm. It has the same best-case as QuickSort, but less overhead, and the average and worst case runtimes are much better.