[osy] stromy
- From: Jiri Horky <jiri.horky@xxxxxxxxx>
- To: osy@xxxxxxxxxxxxx
- Date: Tue, 25 Nov 2008 20:17:15 +0100
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:
