Author Topic: Binary Search Tree  (Read 3602 times)

0 Members and 1 Guest are viewing this topic.

Offline Halifax

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1334
  • Rating: +2/-1
    • View Profile
    • TI-Freakware
Binary Search Tree
« 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
There are 10 types of people in this world-- those that can read binary, and those that can't.

Offline trevmeister66

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1009
  • Rating: +14/-5
    • View Profile
Binary Search Tree
« Reply #1 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!
Projects:    nameless RPG: 1.0%  |  Reverse Snake v1.5: 100%  |  Secret Project: 5%  |  DUNGEON: 70%

My MW2 Blog <-- Please visit :)

Offline rivereye

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 996
  • Rating: +0/-0
    • View Profile
Binary Search Tree
« Reply #2 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).
>(<')

elfprince13

  • Guest
Binary Search Tree
« Reply #3 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

Offline Halifax

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1334
  • Rating: +2/-1
    • View Profile
    • TI-Freakware
Binary Search Tree
« Reply #4 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.
There are 10 types of people in this world-- those that can read binary, and those that can't.

Offline trevmeister66

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1009
  • Rating: +14/-5
    • View Profile
Binary Search Tree
« Reply #5 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.
Projects:    nameless RPG: 1.0%  |  Reverse Snake v1.5: 100%  |  Secret Project: 5%  |  DUNGEON: 70%

My MW2 Blog <-- Please visit :)

elfprince13

  • Guest
Binary Search Tree
« Reply #6 on: February 04, 2007, 10:42:00 am »

Offline Halifax

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1334
  • Rating: +2/-1
    • View Profile
    • TI-Freakware
Binary Search Tree
« Reply #7 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
There are 10 types of people in this world-- those that can read binary, and those that can't.

elfprince13

  • Guest
Binary Search Tree
« Reply #8 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.