From: MikkelFJ <mikkelfj-anti-spam@...>
Date: 2002-09-03T18:42:08+09:00
Subject: Re: Efficient construction of a L/R minmax tree


"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