You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ka...@apache.org on 2008/05/24 23:20:11 UTC
svn commit: r659876 - in /directory/apacheds/branches/bigbang/core-avl/src:
main/java/org/apache/directory/server/core/avltree/AvlTree.java
test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
Author: kayyagari
Date: Sat May 24 14:20:11 2008
New Revision: 659876
URL: http://svn.apache.org/viewvc?rev=659876&view=rev
Log:
AvlTree - fixed an issue with tree rotation after deleting root node
fixed another issue with detaching nodes after deleting root node
AvlTreeTest -added test cases for testing above fixes
Modified:
directory/apacheds/branches/bigbang/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
directory/apacheds/branches/bigbang/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
Modified: directory/apacheds/branches/bigbang/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java?rev=659876&r1=659875&r2=659876&view=diff
==============================================================================
--- directory/apacheds/branches/bigbang/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java (original)
+++ directory/apacheds/branches/bigbang/core-avl/src/main/java/org/apache/directory/server/core/avltree/AvlTree.java Sat May 24 14:20:11 2008
@@ -541,6 +541,18 @@
parentNode.right = temp;
}
}
+ /*
+ when the 'parentNode' param is null then the node under rotation is a child of ROOT.
+ Most likely this condition executes when the root node is deleted and balancing is required.
+ */
+ else if( root != null )
+ {
+ if( root.left == node )
+ {
+ root.left = temp;
+ }
+ // no need to check for right node
+ }
}
@@ -560,7 +572,7 @@
}
else if( node == parentNode.right )
{
- parentNode.right = null;
+ parentNode.right = node.left;
}
}
}
Modified: directory/apacheds/branches/bigbang/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/bigbang/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java?rev=659876&r1=659875&r2=659876&view=diff
==============================================================================
--- directory/apacheds/branches/bigbang/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java (original)
+++ directory/apacheds/branches/bigbang/core-avl/src/test/java/org/apache/directory/server/core/avltree/AvlTreeTest.java Sat May 24 14:20:11 2008
@@ -353,6 +353,41 @@
assertTrue( 7 == tree.getKeys().size() );
}
+ @Test
+ public void testTreeRoationAtLeftChildAfterDeletingRoot()
+ {
+ int[] keys = { 86, 110, 122, 2, 134, 26, 14, 182 }; // order is important to produce the expected tree
+ int[] expectedKeys = { 2, 14, 26, 86, 122, 134, 182 };
+
+ for( int key:keys )
+ {
+ tree.insert( key );
+ }
+
+ tree.remove( 110 );
+
+ for ( int key : expectedKeys )
+ {
+ assertNotNull( "Should find " + key, tree.find( key ) );
+ }
+ }
+
+
+ @Test
+ public void testDetachNodesAtLeftChildAfterDeletingRoot()
+ {
+ int[] keys = { 110, 122, 2, 134, 86, 14, 26, 182 }; // order is important to produce the expected tree
+
+ for( int key:keys )
+ {
+ tree.insert( key );
+ }
+
+ tree.remove( 110 );
+
+ assertEquals( 26, ( int ) tree.find( 14 ).right.key );
+ }
+
private String getLinkedText()
{