directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lecharny <elecha...@apache.org>
Subject Re: [ApacheDS][AvlTree] remove() operation removes multiple entries in specific configurations
Date Tue, 27 May 2008 16:35:25 GMT
Hi guys,

I gonna spend a couple of day reviewing the AVL implementation we have. 
There are some things we must do in order to be sure that AVL are the 
most appropriate structure :
1) manipulating AVLs is an expensive operation. Unless we have a certain 
number of nodes in the tree, sometime a double linked list is simply 
less expensive. We have to determine what is this number.
2) On the other side, we stop to use an AVL when we have more than 512 
elements in the tree. May be this number is too high, or too low. We 
should also determine when it's valuable to switch to a BTree instead of 
using an AVL
3) We have to check that we are not (de)serializing an AVL each time we 
need to manipulate a tree. I may be wrong, but this may be the case 
(another reason why I need to review the code)
4) Regardless the quality of the code, some javadoc is missing, and some 
formating is needed. I will report

Note that I'm not saying that the code is wrong, it's just a peer review 
in order to be sure that we are all good. This part of the code is so 
fundamental that we have to spend some extra time on it. It has to be 
really bullet proof ! (and Thanks to Kiran hard work, I'm pretty 
confident it's already is, my extra pass might simply not bring any 
value, but anyway :)

Thanks a lot guys, bigbang seems to be close to the end now !

Alex Karasulu wrote:
> Hiya Kiran,
>
> I'm finding an unusual situation where the AvlTree.remove() operation is
> removing more than one entry with certain configurations of the tree.  It
> does not happen with all configurations though.  I started debugging but I
> could not quickly figure it out after looking at how the rotations are
> handled.  Maybe you might have more insight..
>
> For example, I'm finding that a remove( 16 ) operation on a tree with the
> following configuration removes both entries 16 and 13 instead of only entry
> 16 as expected:
>
> [8]
> |--[12]R
> |  |--[16]R
> |  |  |--[17]R
> |  |  |--[14]L
> |  |  |  |--[13]L
> |  |--[10]L
> |  |  |--[11]R
> |  |  |--[9]L
> |--[4]L
> |  |--[6]R
> |  |  |--[7]R
> |  |  |--[5]L
> |  |--[2]L
> |  |  |--[3]R
> |  |  |--[1]L
>
> After the remove( 16 ) operation I get the following tree configuration:
>
> [8]
> |--[12]R
> |  |--[14]R
> |  |  |--[17]R
> |  |--[10]L
> |  |  |--[11]R
> |  |  |--[9]L
> |--[4]L
> |  |--[6]R
> |  |  |--[7]R
> |  |  |--[5]L
> |  |--[2]L
> |  |  |--[3]R
> |  |  |--[1]L
>
> Notice we lost node 13 in addition to 16.
>
> Any insight to what could be happening here?
>
> Thanks in advance,
> Alex
>
>   


-- 
--
cordialement, regards,
Emmanuel L├ęcharny
www.iktek.com
directory.apache.org



Mime
View raw message