[Olsr-dev] [PATCH] fix hash handling for IP{v4,v6}

[Henning Rogge]

Am Dienstag 06 Mai 2008 09:30:01 schrieb Hagen Paul Pfeifer:
> > in fact we have converted most data structures to use AVL trees rather
> > than hashed lookups.
>
> Nice! But one question about that: are there any advantages to use AVL
> trees rather then rbtrees? I know that olsrd often remove elements from the
> trees and then the re-balancing is more time and CPU consuming as the
> rbtree.
AVL trees are faster in terms of lookup than rbtrees, because they are less 
deep (~ 1.44*lg(n) compared to 2*lg(n)).

Henning


*************************************************
Diplom Informatiker Henning Rogge
Forschungsgesellschaft für
Angewandte Naturwissenschaften e. V. (FGAN) 
Neuenahrer Str. 20, 53343 Wachtberg, Germany
Tel.: 0049 (0)228 9435-961
Fax: 0049 (0)228 9435-685
E-Mail: (spam-protected)
Web: www.fgan.de
************************************************
Sitz der Gesellschaft: Bonn
Registergericht: Amtsgericht Bonn VR 2530
Vorstand: Dr. rer. nat. Ralf Dornhaus (Vors.), Prof. Dr. Joachim Ender 
(Stellv.)