diff -r e25dc68336ec -r e3aad99d2d80 test/avl_tests.c
--- a/test/avl_tests.c	Mon May 18 19:49:03 2015 +0200
+++ b/test/avl_tests.c	Mon May 18 19:52:03 2015 +0200
@@ -142,3 +142,69 @@
     ucx_avl_free(tree4);
     ucx_avl_free(tree5);
 }
+
+UCX_TEST(test_ucx_avl_remove) {
+    UcxAVLTree *tree1 = ucx_avl_new(ucx_ptrcmp);
+    UcxAVLTree *tree2 = ucx_avl_new(ucx_ptrcmp);
+    UcxAVLTree *tree3 = ucx_avl_new(ucx_ptrcmp);
+    UcxAVLTree *tree4 = ucx_avl_new(ucx_ptrcmp);
+    
+    char *data1 = (char*)"data1";
+    char *data2 = (char*)"data2";
+    char *data3 = (char*)"data3";
+    
+    UCX_TEST_BEGIN
+    ucx_avl_put(tree1, 2, (char*)data2);
+    ucx_avl_put(tree1, 1, (char*)data1);
+    ucx_avl_put(tree1, 3, (char*)data3);
+    void *val = ucx_avl_remove(tree1, 3);
+    
+    UCX_TEST_ASSERT(check_tree(tree1->root), "check_tree failed (tree1)");
+    UCX_TEST_ASSERT(val == data3, "wrong return value (tree1)");
+    UCX_TEST_ASSERT(ucx_avl_get(tree1, 3) == NULL, "value not removed (tree1)");
+    
+    for(int i=0;i<20;i++) {
+        if(i==10) {
+            ucx_avl_put(tree2, i, data3);
+        } else if(i==15) {
+            ucx_avl_put(tree2, i, data2);
+        } else {
+            ucx_avl_put(tree2, i, data1);
+        }
+    }
+    
+    UCX_TEST_ASSERT(
+            ucx_avl_remove(tree2, 10) == data3,
+            "wrong return value for key: 10 (tree2)");
+    UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
+    
+    UCX_TEST_ASSERT(
+            ucx_avl_remove(tree2, 15) == data2,
+            "wrong return value for key: 15 (tree2)");
+    UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
+    
+    for(int i=0;i<20;i++) {
+        ucx_avl_remove(tree2, i);
+        UCX_TEST_ASSERT(check_tree(tree2->root), "check_tree failed (tree2)");
+    }
+    
+    for(int i=0;i<100000;i++) {
+        ucx_avl_put(tree3, i, data1);
+    }
+    for(int i=100000-1;i>=0;i--) {
+        ucx_avl_remove(tree3, i);
+    }
+    UCX_TEST_ASSERT(tree3->root == NULL, "root not NULL (tree3)");
+    UCX_TEST_ASSERT(check_tree(tree3->root), "check_tree failed (tree3)");
+    
+    ucx_avl_put(tree4, 1, data1);
+    ucx_avl_remove(tree4, 1);
+    UCX_TEST_ASSERT(check_tree(tree4->root), "check_tree failed (tree4)");
+    UCX_TEST_ASSERT(tree4->root == NULL, "root not NULL (tree4)");
+    UCX_TEST_END
+    
+    ucx_avl_free(tree1);
+    ucx_avl_free(tree2);
+    ucx_avl_free(tree3);
+    ucx_avl_free(tree4);
+}