From: "Jesper Louis Andersen" <none@jlouis--mongers.org.lh.bsd-dk.dk> Date: Sun, 6 Mar 2005 23:04:14 +0100 To: devel@bsd-dk.dk Subject: Re: binære træer på FreeBSD
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.
-- jlouis
This archive was generated by hypermail 2b30 : Wed 15 Nov 2006 - 18:25:13 CET