Efficient construction of a L/R minmax tree


Yes - nicely identified, Joel - siblings must have disjoint [L,R] intervals.


Lachlan Pitts
Technical Consultant
SoftWorks Australia Pty Ltd

email: mailto:Lachlan_Pitts@softworks.com.au
voice: +61 7 3511 7000

There are two kinds of companies:
Good ones ask you to think for them.
The others tell you to think like them.
Once you see that, it’s easy to tell whether you’re in the right place.
-Benjy Feen


-----Original Message-----
From: Joel VanderWerf [mailto:vjoel@PATH.Berkeley.EDU]
Sent: Tuesday, September 03, 2002 3:42 PM
To: ruby-talk ML
Subject: Re: Efficient construction of a L/R minmax tree

Lachlan Pitts wrote:

I need an algorithm that paints the entire tree with L and R
values such that any ancestor’s L and R values strictly bound
all its descendants L and R values. (A sort of pre-stored
transitive closure approach).

…and such that the [L,R] intervals of siblings are disjoint?

Otherwise you can take L = 0, R = 2*depth for the root and do L–, R++
for each level down…