Date: Mon, 07 Mar 2005 12:52:27 +0100 From: Per Engelbrecht <none@per--xterm.dk.lh.bsd-dk.dk> To: devel@bsd-dk.dk Subject: Re: binære træer på FreeBSD
Jesper Louis Andersen wrote:
> Quoting Claus Guttesen (cguttesen@yahoo.dk):
>
>
>>Jeg har set på nogle måder at lave binære søgetræer
>>på. Bl.a man 3 tree_add som er en indbygget funktion i
>>FreeBSD. Det er ikke noget seriøst stort jeg skal
>>bruge det til, så vil denne og relaterede funktioner
>>være OK?
>
>
> Ah, saa maa tree-noerden tage fat:
>
> Et Binaert soegetraae giver dig egentlig kun O(n) lookup tid, fordi det
> i vaerste tilfaelde bliver til en liste (indsaet successivt 1,2,3,4,... og
> se paa det resulterende trae). Derfor skal man have fat i det, der hedder
> et selvbalancerende binaert trae.
>
> Et af disse er et AVL-tree (Adelson-Velsky og Landis). Ideen er, at hvis
> traeet faar for meget ``listeform'', saa omordnes traaet saadan at det stadig
> har paen struktur. Denne omordning foregaar automatisk, deraf selvbalancerende.
> Faktisk kan traaet ikke blive daarligere end et fibonacci-traae. Det garanterer
> ogsaa O(lg n) indsaettelse og opslag. Noget bedre end de O(n) som en liste
> giver.
>
> Et andet er Red-black search trees. Disse er defineret som #define-makroer i
> tree.h (manpage tree(3), glob: RB_*). Disse er ligeledes selvbalancerende, men
> de tillader mere ``slack'' forstaaet paa den maade at der skal mere skaevhed
> til foer de rydder op, set i forhold til AVL traaet. Det goer RB-trees bedre,
> hvis du har relativt mange inserts/deletes i forhold til lookups. De er nemlig
> hurtigere til insert-/delete-operationer.
>
> Splay trees er en 3. form for traer. Disse balancerer efter en simpel heuristik
> og arbejder ogsaa efter et ``move-to-front'' princip, hvor ofte soegte
> noegler er at finde i toppen a dit trae. Dette goer i princippet traaet meget
> hurtigt, hvis du ofte tilgaar en relativt lille maengde af det samlede key-
> space.
>
> En god introduktion til AVL-trees er at finde i ``D.E. Knuth, The art of
> computer programming, Vol. 3: Sorting and Searching''. Det oprindelige paper
> er paa Russisk. En introduktion til RB-trees er at finde i ``Cormen,
> Leiserson, Rivest and Stein: Introduction to algorithms'', men den skal man
> ikke laese, for den er for kompleks. ``Chris Okasaki: Purely functional
> data structures'' har en meget bedre gennemgang (funktionelt), og behandler
> ioevrigt ogsaa Splay trees.
>
> Hvis du nemt kan lave en hash-funktion, der distribuerer paent over dine data,
> kan det dog vaere at du skal overveje en hashtable i stedet. Men hvis ikke du
> kan lave en hash-funktion, der distribuerer paent, saa glem det. Knuth, Vol 3
> har igen betragtningerne omkring det at lave multiplikative og
> divisionsbaserede hash-funktioner (Det er et hamrende spaendende kapitel, hvis
> du godt vil vide hvordan skidtet haenger sammen, men lidt general algebra er
> ikke af vejen hvis du vil studere det naermere).
>
> Hvis du har mindre end 100 elementer, saa kan en liste eller en ordnet liste
> dog nok vaere hurtigere end alt der er naevnt her. ``Premature Optimization
> is the root of all evil'', remember no? Saa lad vaere med at implementere
> det helt vilde foer du har profilet og ved at det faktisk er her din
> flaskehals er.
>
Hej Jesper
Tumbs up!
Kanon forklaring. Herligt.
/per
per@xterm.dk
This archive was generated by hypermail 2b30 : Wed 15 Nov 2006 - 18:25:13 CET