I have currently implemented 2 different methods for a binary search tree in pure TI-Basic, both a fairly speedy, and far speedier than having to traverse a list in order.

the first one can hold any real values, but is limited to 98 entries.

the second can hold as many entries as will fit in memory (6 bytes/entry) but can only hold values from 0 to 1368 (this limit is expandable to t2-1, where t is the number of legal tokens in TI-Basic, at the cost of the space available for the tree).
/me glances right and left.
No sample code? Sad Good for you, that's quite impressive.
KermMartian wrote:
/me glances right and left.

Very Happy

Kermizzle wrote:
No sample code? Sad

fear not, I shall arrive home rather shortly.
Kermizzle wrote:
Good for you, that's quite impressive.


Very Happy thanks, 3xN matrices make good trees rather surprisingly as do Strings and lists.

[edit]

OH SNAP!!!!!!!! I had an idea for a third implementation using lists. that would be sortof a middle ground between the 2.
/me is still vainly waiting for the source code to this impressive feat to arrive, but alas, I fear est absum.
whoops forgot to post that, Ill finish up my lists version and post all 3.
elfprince13 wrote:
whoops forgot to post that, Ill finish up my lists version and post all 3.
Eeexcellent. As a matter of fact, I bet this might help some of the people working on 3D stuff for the contest.
you mean for drawing front-to-back for doing solid rendering?
elfprince13 wrote:
you mean for drawing front-to-back for doing solid rendering?
'xactly; much better, certainly, than slow manual flipping through the poly array. Razz
just released it to these very archives.

http://www.cemetech.net/programs/archives.php?mode=file&path=/83plus/basic/graphics/BST.zip


along with a mergesort algorithm, D-Term, and some other helpful stuff.

BASIC Code wrote:
:If θ=1337.1337
:Then
:¦ If not(A
:¦ 2→A
:¦ dim([A]
:¦ If 1=Ans(1
:¦ Then
:¦ ¦ 0
:¦ ¦ Return
:¦ End
:¦ If I=[A](A,1
:¦ Then
:¦ ¦ 1
:¦ ¦ Else
:¦ ¦ If I<[A](A,1
:¦ ¦ Then
:¦ ¦ ¦ [A](A,2→A
:¦ ¦ ¦ Else
:¦ ¦ ¦ [A](A,3→A
:¦ ¦ End
:¦ ¦ If A
:¦ ¦ Then
:¦ ¦ ¦ prgmBST
:¦ ¦ ¦ Else
:¦ ¦ ¦ 0
:¦ ¦ End
:¦ End
:¦ Return
:End
:If θ=42.1337
:Then
:¦ dim([A]
:¦ If 1=Ans(1
:¦ Then
:¦ ¦ 2,3→dim([A]
:¦ ¦ I→[A](2,1
:¦ ¦ Else
:¦ ¦ Ans(1→L
:¦ ¦ L+1→L
:¦ ¦ L,3→dim([A]
:¦ ¦ I→[A](L,1
:¦ ¦ 2→A
:¦ ¦ [A](A,1
:¦ ¦ While ([A](A,2) and I≤Ans) or ([A](A,3) and I>Ans
:¦ ¦ ¦ If I≤[A](A,1
:¦ ¦ ¦ Then
:¦ ¦ ¦ ¦ [A](A,2→A
:¦ ¦ ¦ ¦ Else
:¦ ¦ ¦ ¦ [A](A,3→A
:¦ ¦ ¦ End
:¦ ¦ ¦ [A](A,1
:¦ ¦ End
:¦ ¦ If I≤Ans
:¦ ¦ Then
:¦ ¦ ¦ L→[A](A,2
:¦ ¦ ¦ Else
:¦ ¦ ¦ L→[A](A,3
:¦ ¦ End
:¦ End
:¦ Return
:End
:If θ=1337.42
:Then
:¦ If not(A
:¦ Then
:¦ ¦ 2→A
:¦ ¦ A→L1
:¦ ¦ 1→I
:¦ ¦ 0→dim(L2
:¦ End
:¦ If [A](A,2
:¦ Then
:¦ ¦ [A](A,2→A
:¦ ¦ I+1→I
:¦ ¦ A→L1(I
:¦ ¦ prgmBST
:¦ ¦ I-1→I
:¦ ¦ L1(I→A
:¦ End
:¦ [A](A,1→L2(1+dim(L2
:¦ If [A](A,3
:¦ Then
:¦ ¦ [A](A,3→A
:¦ ¦ I+1→I
:¦ ¦ A→L1(I
:¦ ¦ prgmBST
:¦ ¦ I-1→I
:¦ ¦ L1(I→A
:¦ End
:¦ Return
:End
:1,3→dim([A]
:Fill 0,[A]
Generated by SourceCoder, © 2005 Cemetech
Shock Holy cow, dude, your icons look amazingly pwny! Props for that.
thanks Very Happy
Hate to be a nuisance,a but what is a binary tree (Is it similar to a minimax tree or whatever those move arrays are called?)?
Harq wrote:
Hate to be a nuisance,a but what is a binary tree (Is it similar to a minimax tree or whatever those move arrays are called?)?


Shock http://en.wikipedia.org/wiki/Binary_Search_Tree (this lends itself quite nicely to a treesort and searching for values)

and before anyone asks what mergesort is:
http://en.wikipedia.org/wiki/Mergesort
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement