hello
this is a purely algorithmical question but if i have posted to an
irrelevant group, apologies.
can anyone point me at some good tutorials or info about the steps involved
in creating a high-end generic binary tree (or, ternary search tree).
The basic method I've got at the moment is having a resource file containing
a series of data structures (which represent strings), specifically
organised such that a test string can be matched against one by examining
the minimum number of characters possible, as dictated by the efficiency
('even-ness') of the tree. However, the data is generated by an algorithm
running once on the initial list of words and laying out the binary resource
file data in an algorithm that is designed to analyze the whole lot at once
and then that's the data written - essentially a "write-once, read-many"
type operation, but what I want is a "write-read-write-read" more sort of a
dynamic high-end tree which can have items added to it, whereupon they will
be sorted so that the minimum number of operations can be done when
comparing it to a test value. When I say the 'efficiency' of the tree is -
if it has got say, n items, then the average (probable) number of members I
would have to examine to match a test value in a completely flat-file system
would be n / 2. If I could get the average number that have to be compared
with the tree to, say, n / 8, then that would be an efficiency gain of
factor 4, adding to that, each 'operation' in the tree system is comparing
one character, while the flat file system has to compare the whole string
for each operation, if each string is an average of 7 characters long then
that's another efficiency gain of factor 7, giving a total efficiency gain
of 28.
there needs to be no 'Fuzziness' - a match has got to be exact.
any ideas appreciated |