Date: Mon, 7 Mar 2005 08:58:05 +0100 (CET) From: Claus Guttesen <none@cguttesen--yahoo.dk.lh.bsd-dk.dk> Subject: Re: binære træer på FreeBSD To: devel@bsd-dk.dk
> 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.
Ja, jeg har læst i en bog om div. algoritmer i C
(Mastering Algorithms with C af Kyle Loudon), hvor han
forklarer AVL-balancering.
> 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.
Han nævner også i korte træk red-green, men ikke så
uddybende som du gør.
> 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.
Takker for henvisningerne.
> 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.
Fine indspil. Vil de - i FreeBSD - indbyggede
træ-funktioner være helt kurante, eller er det bedre
at installére et bibliotek fra ports-samlingen?
Hilsen
Claus
This archive was generated by hypermail 2b30 : Wed 15 Nov 2006 - 18:25:13 CET