misc, ternary search tree

Has anyone developed code for a ternary search tree?
I've been looking at this article on Dr. Dobbj Journal

Subject: Ternary Search Trees

http://www.ddj.com/184410528

and thought to implement it but I thought since BASIC uses PASCAL type
strings there may be a better way to implement the code.

Any thoughts on this,


W.

On 23 Aug 2006 16:02:17 -0700, "Waverly" < XXXX@XXXXX.COM >







Yes - don't do a Ternary

That link blows my browser, but using another one I can get the jist

Fully developed and balanced, it is (unless I am wrong) a variation of
the Knuth B*Tree, but it only has three branches per record.

/ A | D \
1 2 B C E F

There are various strategies, some use a fixed record size such as
4096 and the number of keys per record is 'calculated', others have
fixed numbers of keys and the record size is a function.

Just having three branches is a bit inefficient if the tree is going
to be on disk. A reasonable B*Tree should be able to get any one out
of 1mb records in six disk reads an one of 10mb in seven reads

If it is going to be in RAM then one might as well trash the
complexity and keep a sorted list of pointers.

I will check out B*Trees.

Thank you J.

On 29 Aug 2006 06:33:20 -0700, "Waverly" < XXXX@XXXXX.COM >



Only use them for disk based indexes

Memory indexes follow different rules

Well ... yes and no

Personally I reckon that a B*Tree is too complex for simple memory
lookup (well it isif you are updating it on the fly)

- but with Virtual Memory what appears to be RAM is in fact often on
disk

There is some variation that is supposed to be optimized for VM, I
looked at it some time ago, but since I am mean with RAM it was of no
real interest.

If you want to be a purist, a tree is a tree is a tree and is totally and
absolutely independent of medium.


MCM

On Thu, 31 Aug 2006 13:02:22 GMT, "Michael Mattias"


<snip>


Well empirically they aren't on all the machines I've worked on <g>

Then your customers need better developers.

MCM

Well, no ... if you want to be a purist, a tree is a graph. ;)


--
Mail sent to this email address is deleted unread
on the server. Please send replies to the newsgroup.

On Fri, 01 Sep 2006 13:47:48 GMT, "Michael Mattias"








Juvenile