|
|
Warp <war### [at] tagpovrayorg> wrote:
> Darren New <dne### [at] sanrrcom> wrote:
> However, I can think of a much easier solution which doesn't need any
> rebalancing:
>
> Always create every node so that it partitions the alphabet in two equal
> parts. In other words, assuming an alphabet of A-Z, the root node would
> *always* be N.
This would require your data to have a linear distribution.
What if all your keys had the form "img00000000002AC73F.jpg"?
As a matter of fact, there already are good tree concepts out there that include
automatic balancing without any a-priori knowledge of the data. Not perfect, but
with a certain guaranteed minimum quality. Red-Black-Trees are a quite popular
example. I'd expect the same principle to be adaptable to ternary trees, too.
Post a reply to this message
|
|