[osy] Re: stromy
- From: Jaroslav Keznikl <jaroslav.keznikl@xxxxxxxxx>
- To: osy@xxxxxxxxxxxxx
- Date: Tue, 25 Nov 2008 22:44:48 +0100
to vypada zajimave, diky
J.
Jiri Horky napsal(a):
A jeste jednou si odpovim :-)
nejake avl stromy jsou snad i tady:
net/ipv4/inetpeer.c
Jirka H.
Jiri Horky wrote:
Jo jeste dokumentace k tem rbtree aji pouziti a vysvetleni je zde:
( /usr/src/linux ) Documentation/rbtree.txt
Koukal jsem na to a pouziva se to stejne jako listy v kalistu.
Jirka H.
Jiri Horky wrote:
Ahoj,
jenom pro info, jsem nasel tohle srovnani stromu:
AVL trees have average height 1.44 * log(N+2) - 0.33
Red Black trees have worst case height of 2.00* log(N+1)
Red Black & AVL trees both have O(log N) search, insert and delete,
min, max, previous, next in terms of nodes.
Somebody said insert was O(1). It is not, as it still take O(log N)
steps to find the correct place to insert. What is O(1) for Red
Black insert, is any rebalancing necessary to restore the trees
properties. At most a double left or right rotation is needed. For
a AVL tree, rebalancing is O(log N). This is where a RB tree gains
over AVL. There is less rebalancing of nodes after an insert.
It is swings and roundabouts. RB trees have faster inserts than AVL
trees but at the expense of slower searches.
RB tree najdes je ve zdrojakach kernelu: (na gentoo: /usr/src/linux),
include/linux/rbtree.h. AVL stromy jsem tam nenasel :-)
Zdravi
Jirka H.
Other related posts:
