Re: Ternary search trees for Unicode dictionaries

From: Markus Scherer (markus.scherer@jtcsv.com)
Date: Tue Nov 18 2003 - 12:14:52 EST

  • Next message: Markus Scherer: "Re: Ternary search trees for Unicode dictionaries"

    Philippe Verdy wrote:
    > From: "Theodore H. Smith" <delete@elfdata.com>
    >
    >>I've looked into the TST thing.
    >>
    >>I'm not sure that it is optimal, despite how popular they are!
    >>
    >>Look at this, if I add "1", "2","3", "4", "5", "6", "7", "8", "9" to a
    >>TST, they will all be in a line, in the tree. All will be reference via
    >>the "high" node.
    >>
    >>So, to find "9", I have to read through 9 items!
    >
    > Nothing forbids to code each n-ary node as a binary tree for faster
    > searches.

    Or, more simply and obviously, do a binary search on the line array in your node if the node
    contains more than just a few items.

    markus

    This archive was generated by hypermail 2.1.5 : Tue Nov 18 2003 - 13:20:06 EST