Of trees and stuff

Dimitris Tasoulis dtas at math.upatras.gr
Tue Dec 17 20:12:01 EET 2002


On Mon, 16 Dec 2002, Andreas Vlachos wrote:

> http://www.brics.dk/MassiveData02/slides/arge3.pdf
> 
> To parapanw link periexei thn apanthsh sthn aporia sou. Kai nomiza oti
> hksera kati gia dentra! Ta kefalia mesa kai kalo diabasma!
> ----- Original Message -----
> From: "Άγγελος Οικονομόπουλος" <aoiko at cc.ece.ntua.gr>
> To: <linux-greek-users at hellug.gr>
> Sent: Δευτέρα, 16 Δεκεμβρίου 2002 7:58 πμ
> Subject: Of trees and stuff
> 
> 
> > On Monday 16 December 2002 02:51, William Lee Irwin III wrote:
> > [...]
> > > My first thought is a length-constrained address minimization on a 2-d
> > > tree, quadtree, or 2D k-d-b tree keyed on address and length; the
> > > duelling tree solutions aren't really capable of providing O(lg(n))
> > > guarantees for address-ordered first fit (or implementing address-
> > > ordered first fit at all). I have no clue how to do this both
> > > nonrecursively and without frequently-dirtied temporary node linkage,
> > > though, as it appears to require a work stack (or potentially even a
> > > queue for prioritized searches) like many other graph searches. Also,
> > > I don't have a proof in hand that this is really O(lg(n)) worst-case,
> > > though there are relatively obvious intuitive reasons to suspect so.
> >
> > ΟΚ, παραδίνομαι. ΤΙ ΣΤΟΝ ΚΟΡΑΚΑ είναι ένα 2d k-d-b δέντρο;
> >
> > --
> > Make input easy to proofread.
> >             - The Elements of Programming Style (Kernighan & Plaugher)

Einai ena binary tree se poles diastaseis vasika.
Diladi pio sigkekrimena se ka8e epipedo tou binary to split ginete kai se 
diaforetiki diastasi. Px an to provlima einai 4 diastaseon
sto depth 0 kano split stin diastasi 1 sto 1 stin 2 sto 2 stin 3 sto 3 
stin 4, sto 5 stin 0 k.o.k. 

Vasika fantasou to psaximo stis dio diastaseis san ena saligkari poy 
koulouriaete katevainontas to dentro giro apo tin apantisi.

To psa3imo sto dentro ayto einai tis ta3is tou O(sqrt(n)) opou n to pli8os 
ton simion. 

Einai iso i kaliteri epilogi otan den fes na 3eperaseis ton gramiko xoro 
pou xrteiazete.

Iparxoun epiloges  tis ta3is O(log(n)) vlepe multi-diamensional segment 
tree, pou omos apaitoun xoro ek8etiko pros tin diastasi

Dimitris Tasoulis

> >
> >
> > --
> > linux-greek-users mailing list -- http://lists.hellug.gr
> >
> 
> 
> 
> 




More information about the Linux-greek-users mailing list