Efficient construction of a L/R minmax tree

Hi rubys,

Does anyone know of a quick algorithm for painting a tree with L and R values?

(Don’t worry - this isn’t a uni/college assignment or anything)

eg. For tree
A
B C
D E F G H
I J K

Each node (letter in this case) has two values - a left or L value and a right or R value.

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).

eg. A.L = 1 and A.R = 22
B.L = 2 and B.R = 9
C.L = 10 and C.R = 21
D.L = 3 and D.R = 4
E.L = 5 and E.R = 6
F.L = 7 and F.R = 8

Ruby, pseudo-code or C would be perfect!

Thanks in advance

Lachlan Pitts
Technical Consultant
SoftWorks Australia Pty Ltd

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

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…

“Lachlan Pitts” Lachlan_Pitts@softworks.com.au wrote in message
news:426B71FE520A87419C9C4E1BBD2F18F27269C6@swa02.softworks.lan.au

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).

You could take a look at R-Trees, but they inherit the complexity of B-Trees
http://redbook.cs.berkeley.edu:8000/redbook/lec4.html

Sedgewicks book Algorithms in C has a chapter on Range Search - there are
some simpler approaches.

Mikkel