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/25 13:28:55 UTC
svn commit: r659962 - 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: Sun May 25 04:28:55 2008
New Revision: 659962
URL: http://svn.apache.org/viewvc?rev=659962&view=rev
Log:
AvlTree - fixed another issue with preserving child nodes while deleting non-leaf node
AvlTreeTest - added a test case for the above fix
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=659962&r1=659961&r2=659962&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 Sun May 25 04:28:55 2008
@@ -248,13 +248,13 @@
}
else
{
- detachNodes( y, leftTreePath.get( 0 ) );
+ detachNodes( y, leftTreePath.remove( 0 ) );
}
leftTreePath.addAll( treePath );
treePath = leftTreePath;
- y.right = temp.right;
+ y.right = temp.right; // assign the right here left will be assigned in replaceNode()
if( temp == root )
{
@@ -277,13 +277,13 @@
}
else
{
- detachNodes( y, rightTreePath.get( 0 ) );
+ detachNodes( y, rightTreePath.remove( 0 ) );
}
rightTreePath.addAll( treePath );
treePath = rightTreePath;
- y.right = temp.right;
+ y.right = temp.right; // assign the right here left will be assigned in replaceNode()
if( temp == root )
{
@@ -549,6 +549,7 @@
{
if( root.left == node )
{
+ System.out.println("IT IS ROOT");
root.left = temp;
}
// no need to check for right node
@@ -590,6 +591,8 @@
{
if( parentNode != null )
{
+ replaceNode.left = deleteNode.left;
+
if( deleteNode == parentNode.left )
{
parentNode.left = replaceNode;
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=659962&r1=659961&r2=659962&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 Sun May 25 04:28:55 2008
@@ -388,6 +388,22 @@
assertEquals( 26, ( int ) tree.find( 14 ).right.key );
}
+
+ @Test
+ public void testRemoveInRightSubtree()
+ {
+ int[] keys = { 8, 4, 13, 6, 15, 7, 10, 5, 14, 2, 11, 3, 9, 1 }; // order is important to produce the expected tree
+
+ for( int key:keys )
+ {
+ tree.insert( key );
+ }
+
+ tree.remove( 13 );
+
+ assertEquals( 11, ( int ) tree.find( 8 ).right.key );
+ }
+
private String getLinkedText()
{