Best way to do a lookup tree

[kelvSYC]

Suppose you have a binary tree structure, full of some values, and you
have to use the tree to lookup something based on values from a
bitstream (ie. take the left branch if the bit is zero, the right if
the bit is one, that kind of thing). The values in the tree, as well
as the general layout, is hardcoded.

I've been thinking about various ways, from multidimensional arrays to
"static initializer functions". What do you think would be the best
way to implement it?

 

[Alf P. Steinbach]

* kelvSYC:

Suppose you have a binary tree structure, full of some values, and you
have to use the tree to lookup something based on values from a
bitstream (ie. take the left branch if the bit is zero, the right if
the bit is one, that kind of thing). The values in the tree, as well
as the general layout, is hardcoded.

I've been thinking about various ways, from multidimensional arrays to
"static initializer functions". What do you think would be the best
way to implement it?

Define "best", in a manner that allows clear-cut selection from
different solutions.

 

[Greg]

Suppose you have a binary tree structure, full of some values, and you
have to use the tree to lookup something based on values from a
bitstream (ie. take the left branch if the bit is zero, the right if
the bit is one, that kind of thing). The values in the tree, as well
as the general layout, is hardcoded.

I've been thinking about various ways, from multidimensional arrays to
"static initializer functions". What do you think would be the best
way to implement it?

The best way to implement the program is in whichever way that I (were
I the programmer) find it easiest to understand. And I would only ever
depart from my original design in the event that other issues (such as
suboptimal performance measurements) gave me an good enough reason to
change it.

So if the purpose of the program is to walk down a binary tree, using a
bit stream to select which branch to follow at each step, then that is
exactly the way that I would code it - because that is exactly how you
explained what the program is supposed to do.

Not one of the most sophisticated algorithms, data structures, or
programming techniques is worth anything at all, if the program fails
to deliver the correct results. So write correct code first, and think
about optimizations (should they even be needed) afterwards.

Greg

 

[amparikh]

Suppose you have a binary tree structure, full of some values, and you
have to use the tree to lookup something based on values from a
bitstream (ie. take the left branch if the bit is zero, the right if
the bit is one, that kind of thing). The values in the tree, as well
as the general layout, is hardcoded.

I've been thinking about various ways, from multidimensional arrays to
"static initializer functions". What do you think would be the best
way to implement it?

Look up extendible hashing. It sort of uses a tree like impementation
and fits what you are describing.