Character Tree code question

[hutch--]

The tree design I want is a simple binary tree as I am going to store words in it that are user defined that contain a user value, usualy a pointer to other text or data. I have hash tables working fine and I have a very fast known word technique but I want a standard binary tree because of its flexibility.

The test pieces I have played with so far have been recursive but I think it can be done simpler by iteration without the stack overhead and parameter passing required. I want the simple binary tree because the tree build time is a factor as well as the word lookup time. With this task, I need only build the tree and test words, I don't need deletion as the task will allow me to dump the entire memory once its finished.

[Biterider]

Hi Mark!
I hope that the offer for Hutch also valid for me. I'm interested in the Zobrist algo. If you have some info or an implementation to share, please let me know.   :wink

Regards,

Biterider

[Mark_Larson]

Hi Mark!
I hope that the offer for Hutch also valid for me. I'm interested in the Zobrist algo. If you have some info or an implementation to share, please let me know.   :wink

Regards,

Biterider

  Sure.  Here's a place to get some sample source code and some information.  They actaully compare quite a few different hashes and show how fast they run relative to each other, and how many collisions they get.  Zobrist hashing has the least amount of collisions for the testing he did.

http://burtleburtle.net/bob/hash/doobs.html

  He also has a main page that has lots of hash stuff

http://burtleburtle.net/bob/hash/

[Biterider]

Thanks  :U

[rea]

Hi there.

Time a go I was playing with something like the attached picture, tought I was stoped because reading something aparently the idea was called a dictionary algorithm??? and because I thinked already such thing exist, I stop my work :D.. LOL (sorry Im that way :S.. trying change that) and also not continue reading more deep in the dicrionary algorithm then at the end I dont know if my taught that what I was doing where the same or not, was only a feeling.......


OK, anyway, here is the "graph" I start doing that for match words at runtime and for generate words with a variety of nice repetition... like supose we have goooooooooooooooool that can be generated with g->o->l... where the nuber of "o" is not handled or puted there for mark ;).. anyway perhaps I will do a little work at this???


gabor, interesting that, then I supose I must define some rules and things like that (a more mathematical way...) in my way of think I supose, also was suposed to compact the data necesary for represent the complete subset, also have some adventages in some cases, for example how you check if goooooooooool is valid with a hash (because is mmore like static) tought like with a tree can be generated and checked very easely, because handled in some way can generate derived words but not defined in the first tree like gogogogooool tought with a hash will be diicult to find that such thing mean gol ;), with this type of tree can be checked and generated very easely... I think ... whant a proof???? :P.....

with the tree (also I remember when I constructructed that I was not thinking in a tree, I was thinking in some more like a spider (or a "enredadera") ), then is more a spider... perhaps I will do more work on this if you say me that is not like the Dictionary algorithm or representation.... :P or perhaps no more than only think in the posbilities????












Im thinking that I have a friend (girl) that I call normally (nickname) gogomounstrua but I can generate (if playng futball) a little modification like gogoooolmoustra not only mean that is the same nickname that I say to she but also that a gol (goal) was marked ;)....   

By the way, I also make a mistake typing the second time, I delete a "n" between "u" and "s" but a human at less I normally cal she in any of the two ways.. gogomoustrua or gogomounstrua... and I still get that is she ;).






By the way I thing that I not clarificate in the graph....., in each node can by attached a information related to the path followed..... in the mean time for identificate if was a gol in any of the ways: gol, gooooogogogogogogoooooooool, goooooooooool or any other or was a diferent path like gogo or go (the last mean go) the anterior can mean go or the dance ala gogo .... I supose ;)

[attachment deleted by admin]

[hutch--]

I found some reasonable reference for creating a simple binary tree.

The document allows it to be reproduced under these conditions.

This is article #110 in the Stanford CS Education Library. This and other free CS materials are available at the
library (http://cslibrary.stanford.edu/). That people seeking education should have the opportunity to find it.
This article may be used, reproduced, excerpted, or sold so long as this paragraph is clearly reproduced. Copyright
2000-2001, Nick Parlante, nick.parlante@cs.stanford.edu.

[attachment deleted by admin]

[James Ladd]

hutch,
I have examples of many algo's in C.
There are also many on the net.
If you want one in C I can give you one, I could also translate it if you wish.
Let me know and Ill help.

[hutch--]

James,

A tree is C would be fine if you have the source available. I have been slowly grinding through test pieces getting bits of it to work but a complete working example in C would be very useful.

[rea]

hutch--

Your fist representation not feet completely a definition of a binary tree ;)..... (one father 2 childs that have the same level)


A little forat show where is the problem ;).

Code Select Expand


m
   \
    o
      \
       v
      /  \
     z    s-------------------0
     /\
    0  x   x---w---d---b---0  [7]
   /  /     |   |   |   |
[1] 0      0   0   0  [6]
    /       |   |   |
   [2]     [3] [4] [5]


I suguest what gabor as suguested plus the suguestion of randall to search for "whole" parts and that give my suguestion ;).


I suguest go in a construction like:

Code Select Expand


         |->s
         |
         |->sb
         |
         |->sd
         |
[mov,6]---->sw
         |
         |->sx
         |
         |->zx



                    |->w
                    |
[mov,2]---->[s,4]----->b
         |          |
         |->zx      |->d
                    |
                    |->x



Also you can get more sense if you use separate emanings ;) (something I have talked attached to each node ;) )

Code Select Expand



                    |->w <-|
                    |      |
[mov,2]---->[s,4]----->b <-|
         |          |      |
         |->zx      |->d <-|
                    |      |
                    |->x   |
[stos,3]-------------------|
[scas,3]-------------------|


[James Ladd]

hutch,
how soon do you need it ?

[hutch--]

Yesterday.  :toothy

[James Ladd]

ok

[hutch--]

James,

Just the C code if you can find it, simpler the better.

rea,

Thanks for your comments, I have a particular approach with handling the terminator that does not require another leaf node. Place the return value in the left structure member and exit. For testing words against the tree, if it find a zero character that does not match, it will branch right to test for the next character. The tree looks something like this.

Code Select Expand


movsx      => 0   0 <= movs
               \ /
movsb    => 0   x
             \ /
movsw  => 0   b   0 <= movsz
           \ /     \
movsd=> 0   w       x   0 <= mov
         \ /         \ /
          d           z
           \         /
            \       /
             \     /
              \   /
               \ /
                s   -  <= not used
                 \ /
                  v   -  <= not used
                   \ /
                    o   -  <= not used
                     \ /
                      m


[James Ladd]

hutch,
i have it right here, just have to type it in. :)

[rea]

I have a little one ;).. finded with look Im cleaning my documents :) and have finded a app for the school, was something for search for capital/country it is not a balanced tree or some like that in that way is a raw tree, see the bt.c (I remember that work ok... :P)

[attachment deleted by admin]