Yes - nicely identified, Joel - siblings must have disjoint [L,R] intervals.
SoftWorks Australia Pty Ltd
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.
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…