directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alex Karasulu" <akaras...@apache.org>
Subject [ApacheDS][AvlTree] remove() operation removes multiple entries in specific configurations
Date Mon, 26 May 2008 02:21:48 GMT
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

Mime
View raw message