From 40a02032082008d2a1126349e09bc65db7f0fc23 Mon Sep 17 00:00:00 2001 From: a bellenir Date: Wed, 6 Aug 2014 19:37:40 +0000 Subject: [PATCH] +lookup node; WIP: delete --- source/rb/rb.c | 33 +++++++++++++++++ source/rb/rb.h | 3 ++ tests/test_rb.c | 95 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 131 insertions(+) diff --git a/source/rb/rb.c b/source/rb/rb.c index ab7ac00..b05515e 100644 --- a/source/rb/rb.c +++ b/source/rb/rb.c @@ -155,6 +155,39 @@ rb_node_t* rb_tree_insert(rb_tree_t* tree, int value){ } +static rb_node_t* rb_lookup_node(rb_node_t* node, int value){ + rb_node_t* ret = NULL; + if(node){ + if(value == node->contents) ret = node; + else if(value > node->contents) ret = rb_lookup_node(node->right, value); + else if(value < node->contents) ret = rb_lookup_node(node->left, value); + } + return ret; +} + +rb_node_t* rb_tree_lookup(rb_tree_t* tree, int value){ + return rb_lookup_node(tree->root, value); +} + +static void rb_tree_delete_node(rb_tree_t* tree, rb_node_t* node){ + (void) tree; + if(node->left && node->right){ + //has two children. TODO + }else{ + rb_node_t* parent = node->parent; + if(RED == node->color){ + if(node == parent->left) parent->left = NULL; + else parent->right = NULL; + node->parent = NULL; + mem_release(node); + } + } +} +void rb_tree_delete(rb_tree_t* tree, int value){ + rb_node_t* doomed = rb_lookup_node(tree->root, value); + if(doomed) rb_tree_delete_node(tree, doomed); +} + /* THE FOLLOWING FUNCTIONS (TO EOF) ARE USED FOR TESTING PURPOSES ONLY */ //if path to the left != path to the right, return -1 (invalid) diff --git a/source/rb/rb.h b/source/rb/rb.h index 6fac63a..65e27f0 100644 --- a/source/rb/rb.h +++ b/source/rb/rb.h @@ -29,6 +29,9 @@ rb_node_t* rb_node_new(int contents); rb_tree_t* rb_tree_new(); //returns a pointer to the new node rb_node_t* rb_tree_insert(rb_tree_t* tree, int value); +void rb_tree_delete(rb_tree_t* tree, int value); +//look up a node in the tree with the given value +rb_node_t* rb_tree_lookup(rb_tree_t* tree, int value); //TEST FUNCTIONS: bool rb_tree_is_valid(rb_tree_t* tree); diff --git a/tests/test_rb.c b/tests/test_rb.c index 380ab06..4945391 100644 --- a/tests/test_rb.c +++ b/tests/test_rb.c @@ -246,5 +246,100 @@ TEST_SUITE(RB) { CHECK(rb_tree_is_valid(tree)); mem_release(tree); } + + //------------------------------------------------------------------------- + // Test lookup function + //------------------------------------------------------------------------- + TEST(Verify_rb_lookup_returns_null_if_not_found){ + rb_tree_t* tree = rb_tree_new(); + rb_tree_insert(tree, 42); + rb_tree_insert(tree, 33); + rb_tree_insert(tree, 88); + rb_tree_insert(tree, 15); + CHECK(NULL == rb_tree_lookup(tree, 78)); + mem_release(tree); + } + TEST(Verify_rb_lookup_returns_correct_node){ + rb_tree_t* tree = rb_tree_new(); + rb_node_t* node1 = rb_tree_insert(tree, 42); + rb_node_t* node2 = rb_tree_insert(tree, 33); + rb_node_t* node3 = rb_tree_insert(tree, 88); + rb_node_t* node4 = rb_tree_insert(tree, 15); + CHECK(node1 == tree->root); + CHECK(node2 == node1->left); + CHECK(node3 == node1->right); + CHECK(node4 == node2->left); + CHECK(42 == node1->contents); + CHECK(33 == node2->contents); + CHECK(88 == node3->contents); + CHECK(15 == node4->contents); + CHECK(node1 == rb_tree_lookup(tree, 42)); + CHECK(node2 == rb_tree_lookup(tree, 33)); + CHECK(node3 == rb_tree_lookup(tree, 88)); + CHECK(node4 == rb_tree_lookup(tree, 15)); + mem_release(tree); + } + + //------------------------------------------------------------------------- + // Test delete function + //------------------------------------------------------------------------- + //first class: delete nodes that have at most one non-null child + TEST(Verify_rb_delete_red_node_without_children){ + rb_tree_t* tree = rb_tree_new(); + rb_node_t* node1 = rb_tree_insert(tree, 42); + rb_node_t* node2 = rb_tree_insert(tree, 33); + rb_node_t* node3 = rb_tree_insert(tree, 88); + rb_node_t* node4 = rb_tree_insert(tree, 15); + mem_retain(node4); + //delete node 4 + rb_tree_delete(tree, 15); + CHECK(1 == mem_num_references(node4)); + //check node4 no longer in tree + CHECK(NULL == node2->left); + CHECK(node2 == node1->left); + CHECK(node3 == node1->right) + CHECK(node1 == tree->root); + CHECK(BLACK == node1->color); + CHECK(BLACK == node2->color); + CHECK(BLACK == node3->color); + //check node4 pointers are nulld + CHECK(NULL == node4->parent); + CHECK(NULL == node4->left); + CHECK(NULL == node4->right); + CHECK(rb_tree_is_valid(tree)); + mem_release(node4); + mem_release(tree); + } + TEST(Verify_rb_delete_black_node_with_single_red_child){ + rb_tree_t* tree = rb_tree_new(); + rb_node_t* node1 = rb_tree_insert(tree, 42); + rb_node_t* node2 = rb_tree_insert(tree, 33); + rb_node_t* node3 = rb_tree_insert(tree, 88); + rb_node_t* node4 = rb_tree_insert(tree, 15); + mem_retain(node2); + //delete node 2 + rb_tree_delete(tree, 33); + CHECK(1 == mem_num_references(node2)); + CHECK(node1 == tree->root); + CHECK(node4 == node1->left); + CHECK(node3 == node1->right); + CHECK(NULL == node4->left); + CHECK(NULL == node4->right); + CHECK(node1 == node4->parent); + CHECK(BLACK == node1->color); + CHECK(BLACK == node3->color); + CHECK(BLACK == node4->color); + //check node2 pointers are nulld + CHECK(NULL == node2->parent); + CHECK(NULL == node2->left); + CHECK(NULL == node2->right); + CHECK(rb_tree_is_valid(tree)); + mem_release(node2); + mem_release(tree); + } + + //second class: deleting nodes that have two children + //third class: special cases + TEST(Verify_rb_delete_root){} } -- 2.55.0