Hi Emmanuel,

On Tue, May 27, 2008 at 12:35 PM, Emmanuel Lecharny <elecharny@apache.org> wrote:
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.

Yes a very good point.  We just need to figure out where the break even point is and handle it.  BTW this AvlTree is only used when we have Tables configured to have duplicate keys.
 

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

Right on!  This number is completely arbitrary and some performance metrics should give us more insight.  BTW I cannot wait to get your metrics from the tests you've been running on this branch now that we have it working.
 

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)

No problem let's work it together - should be fun.

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 :)

Yeah the code is really good but another pass is great.
 

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

Yep thanks to you guys.

Alex
 


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