|
|
 Up |
|
|
  |
Author: Jonah ThomasJonah Thomas Date: Jul 7, 2008 14:08
I finally wrote up something about this method, and I'd like to get some
sense how hard it is to read. It isn't thoroughly tested, but more
important if it's too hard to understand or use then it's useless even
if completely correct.
------------
0 value example
1 value extension1
1 value extension2
0 [IF]
An efficient way to arrange a searchable binary tree that does not
need to be added to or rebalanced often.
First, an easy example. Say you have six items you want to arrange into
a searchable tree. We'll number them 1 through 6.
We put the items or pointers to the items into an array. The zero'th
item will be the number of items+1, 7. Then we have the middle item, 4.
Then the middle item of the first three, 2, followed by the middle item
of the secont three, 6. Etc.
7 4 2 6 1 3 5
|
| Show full article (5.42Kb) |
|
| | 8 Comments |
|
|
Author: GerryGerry Date: Jul 22, 2008 00:07
On 7 Jul, 22:08, Jonah Thomas gmail.com> wrote:> I finally wrote up something about this method, and I'd like to get some
> sense how hard it is to read. It isn't thoroughly tested, but more
> important if it's too hard to understand or use then it's useless even
> if completely correct.
>
> ------------
> 0 value example
> 1 value extension1
> 1 value extension2
>
> 0 [IF]
>
> An efficient way to arrange a searchable binary tree that does not
> need to be added to or rebalanced often.
>
> First, an easy example. Say you have six items you want to arrange into
> a searchable tree. We'll number them 1 through 6.
>
> We put the items or pointers to the items into an array. The zero'th ...
|
| Show full article (5.94Kb) |
|
| | no comments |
|
|
Author: Jonah ThomasJonah Thomas Date: Jul 22, 2008 17:48
Gerry jackson9000.fsnet.co.uk> wrote:
> On 7 Jul, 22:08, Jonah Thomas gmail.com> wrote:>> I finally wrote up something about this method, and I'd like to get
>> some sense how hard it is to read. It isn't thoroughly tested, but
>> more important if it's too hard to understand or use then it's
>> useless even if completely correct.
> Taken as an isolated bit of code this doesn't map 1 to 4 as
> stated in the sentence above. But setting tree-depth to 4 does
> work. It looks as if the name tree-depth is a little misleading
> as it needs to be a power of 2 (I think).
Thank you. That advice is some of what I was looking for. So I took that
out.
> Is the following true for your scheme? Taking your example above:
>
> The tree can hold between 4 and 7 values, if it was lower than 4
> then the array would be smaller so we ignore those cases. So...
|
| Show full article (9.79Kb) |
| no comments |
|
|
Author: GerryGerry Date: Jul 24, 2008 03:57
On 23 Jul, 01:48, Jonah Thomas gmail.com> wrote:
[...]
>
>> Of course instead of having your b->a mapping we now have to
>> calculate the middle index for the root of the tree (and for the
>> subtrees). This is easily done e.g. if n is the number of items...
|
| Show full article (3.46Kb) |
| no comments |
|
|
Author: Jonah ThomasJonah Thomas Date: Jul 24, 2008 04:40
Gerry jackson9000.fsnet.co.uk> wrote:> Jonah Thomas gmail.com> wrote:
>
> [...]
> >>> The root item is:
>>> hibit 2/ - 1+ hibit min ( n -- rt )
>>
>>> with similar calculations for the left and right subtrees.
>>
>> I didn't like that, it takes two recursions for most nodes and it
>> wound up heavy on the stack juggling in my hands. So instead I found
>> a way to find the next larger location, given any single location.
>> With that I can start at the left-most leaf and work my way
>> rightward. It seems simpler to me. So here's the revised version.
>
> I'm not sure I agree that it is simpler, see a recursive version
> below
>
> [...] ...
|
| Show full article (4.69Kb) |
| no comments |
|
|
Author: GerryGerry Date: Jul 24, 2008 13:33
On 24 Jul, 12:40, Jonah Thomas gmail.com> wrote:> Gerry jackson9000.fsnet.co.uk> wrote:>> Jonah Thomas gmail.com> wrote:>
[...]
> Suppose something had gone wrong, and you had to debug it. I don't like
> debugging recursive routines. Even worse with locals.
>
> (Though locals aren't really so bad, just declare a VALUE for each
> local, and you can test the exact same code interactively. Until you
> recurse.)
>
I can't say that I find debugging recursive routines any worse
than debugging other routines. I think that using locals in
recursive code actually makes developing such routines simpler,
locals can always be removed once the recursion has been
perfected.
[...]
Gerry
|
| |
| no comments |
|
|
Author: Jonah ThomasJonah Thomas Date: Jul 26, 2008 18:13
Gerry jackson9000.fsnet.co.uk> wrote:> Jonah Thomas gmail.com> wrote:
> >> Suppose something had gone wrong, and you had to debug it. I don't
>> like debugging recursive routines. Even worse with locals.
>>
>> (Though locals aren't really so bad, just declare a VALUE for each
>> local, and you can test the exact same code interactively. Until you
>> recurse.)
>
> I can't say that I find debugging recursive routines any worse
> than debugging other routines.
That's a personal preference thing, I can't argue with you. Usually I
don't have a problem with them but when something goes wrong in the
recursive part it can sometimes be hard to find. I can look for ways to
simplify the routines, I can put in methods to get it to dump stack
states, etc. Usually it isn't a problem but a few times I had to revert
to debugging methods I don't need with Forth.
|
| Show full article (2.55Kb) |
| no comments |
|
|
Author: Albert van der HorstAlbert van der Horst Date: Aug 3, 2008 03:36
>On 7 Jul, 22:08, Jonah Thomas gmail.com> wrote:>> I finally wrote up something about this method, and I'd like to get some
>> sense how hard it is to read. It isn't thoroughly tested, but more
>> important if it's too hard to understand or use then it's useless even
>> if completely correct.
>>
>> ------------
>> 0 value example
>> 1 value extension1
>> 1 value extension2
>>
>> 0 [IF]
>>
>> An efficient way to arrange a searchable binary tree that does not
>> need to be added to or rebalanced often.
>>
>> First, an easy example. Say you have six items you want to arrange into
>> a searchable tree. We'll number them 1 through 6. ...
|
| Show full article (1.98Kb) |
| no comments |
|
|
|
|
|
Author: Jonah ThomasJonah Thomas Date: Aug 4, 2008 11:07
Albert van der Horst wrote:>> Jonah Thomas gmail.com> wrote:>>> First, an easy example. Say you have six items you want to arrange
>>into> a searchable tree. We'll number them 1 through 6.
>>>
>>> We put the items or pointers to the items into an array. The...
|
| Show full article (3.01Kb) |
| no comments |
|
|
