From 3b1eaea14a553f130cbcb50f3f17275bc8000cd0 Mon Sep 17 00:00:00 2001 From: a bellenir Date: Tue, 12 Aug 2014 14:56:37 +0000 Subject: [PATCH] delete complete --- source/rb/rb.c | 22 +++++++++- tests/test_rb.c | 110 +++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 130 insertions(+), 2 deletions(-) diff --git a/source/rb/rb.c b/source/rb/rb.c index 8fad973..8a7ca96 100644 --- a/source/rb/rb.c +++ b/source/rb/rb.c @@ -217,10 +217,30 @@ static void rb_tree_del_rebalance(rb_tree_t* tree, rb_node_t* node){ } } +static rb_node_t* rightmost_descendent(rb_node_t* node){ + return (node->right) ? rightmost_descendent(node->right) : node; +} + 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 + rb_node_t* parent = node->parent; + rb_node_t* replacement = rightmost_descendent(node->left); + mem_retain(replacement); + rb_tree_delete_node(tree, replacement); + if(node->left) node->left->parent = replacement; + if(node->right) node->right->parent = replacement; + replacement->left = node->left; + replacement->right = node->right; + replacement->parent = node->parent; + replacement->color = node->color; + if(NULL == parent) tree->root = replacement; + else if(node == parent->left) parent->left = replacement; + else parent->right = replacement; + node->left = NULL; + node->right = NULL; + node->parent = NULL; + mem_release(node); }else{ //node has at most one non-leaf child rb_node_t* parent = node->parent; diff --git a/tests/test_rb.c b/tests/test_rb.c index 0669112..e12e4f4 100644 --- a/tests/test_rb.c +++ b/tests/test_rb.c @@ -1990,7 +1990,61 @@ TEST_SUITE(RB) { mem_release(tree); } //second class: deleting nodes that have two children - //TODO + TEST(Verify_rb_delete_node_with_two_children_successor_is_left){ + int target = 22; + rb_tree_t* tree = rb_tree_new(); + rb_tree_insert(tree, 42); + rb_tree_insert(tree, 88); + rb_node_t* doomed = rb_tree_insert(tree, target); + rb_tree_insert(tree, 33); + rb_tree_insert(tree, 15); + CHECK(NULL != doomed->left); + CHECK(NULL != doomed->right); + CHECK(NULL == doomed->left->right); + CHECK(OK == rb_tree_is_valid(tree)); + CHECK(doomed == rb_tree_lookup(tree, target)); + mem_retain(doomed); + rb_tree_delete(tree, target); + CHECK(1 == mem_num_references(doomed)); + CHECK(NULL == rb_tree_lookup(tree, target)); + CHECK(NULL == doomed->parent); + CHECK(NULL == doomed->left); + CHECK(NULL == doomed->right); + CHECK(OK == rb_tree_is_valid(tree)); + mem_release(doomed); + mem_release(tree); + } + TEST(Verify_rb_delete_node_with_two_children){ + int target = 42; + rb_tree_t* tree = rb_tree_new(); + rb_node_t* doomed = rb_tree_insert(tree, target); + rb_tree_insert(tree, 88); + rb_tree_insert(tree, 22); + rb_tree_insert(tree, 96); + rb_tree_insert(tree, 11); + rb_tree_insert(tree, 35); + rb_tree_insert(tree, 5); + rb_tree_insert(tree, 18); + rb_tree_insert(tree, 12); + rb_tree_insert(tree, 25); + rb_tree_insert(tree, 55); + rb_tree_insert(tree, 99); + CHECK(OK == rb_tree_is_valid(tree)); + CHECK(doomed != tree->root); + CHECK(NULL != doomed->left); + CHECK(NULL != doomed->right); + CHECK(doomed == rb_tree_lookup(tree, target)); + mem_retain(doomed); + rb_tree_delete(tree, target); + CHECK(1 == mem_num_references(doomed)); + CHECK(NULL == rb_tree_lookup(tree, target)); + CHECK(NULL == doomed->parent); + CHECK(NULL == doomed->left); + CHECK(NULL == doomed->right); + CHECK(OK == rb_tree_is_valid(tree)); + mem_release(doomed); + mem_release(tree); + } //third class: special cases: deleting root TEST(Verify_rb_delete_root_node_with_single_red_left_child){ rb_tree_t* tree = rb_tree_new(); @@ -2044,5 +2098,59 @@ TEST_SUITE(RB) { mem_release(node1); mem_release(tree); } + TEST(Verify_rb_delete_root_node_with_two_children){ + int target = 22; + rb_tree_t* tree = rb_tree_new(); + rb_tree_insert(tree, 42); + rb_tree_insert(tree, 88); + rb_node_t* doomed = rb_tree_insert(tree, target); + rb_tree_insert(tree, 96); + rb_tree_insert(tree, 11); + rb_tree_insert(tree, 35); + rb_tree_insert(tree, 5); + rb_tree_insert(tree, 18); + rb_tree_insert(tree, 12); + rb_tree_insert(tree, 25); + rb_tree_insert(tree, 55); + rb_tree_insert(tree, 99); + CHECK(OK == rb_tree_is_valid(tree)); + CHECK(doomed == tree->root); + CHECK(NULL != doomed->left); + CHECK(NULL != doomed->right); + CHECK(doomed == rb_tree_lookup(tree, target)); + mem_retain(doomed); + rb_tree_delete(tree, target); + CHECK(1 == mem_num_references(doomed)); + CHECK(NULL == rb_tree_lookup(tree, target)); + CHECK(NULL == doomed->parent); + CHECK(NULL == doomed->left); + CHECK(NULL == doomed->right); + CHECK(OK == rb_tree_is_valid(tree)); + mem_release(doomed); + mem_release(tree); + } + TEST(Verify_rb_delete_node_with_four_nodes){ + int target = 42; + rb_tree_t* tree = rb_tree_new(); + rb_node_t* doomed = rb_tree_insert(tree, target); + rb_tree_insert(tree, 88); + rb_tree_insert(tree, 22); + rb_tree_insert(tree, 33); + CHECK(OK == rb_tree_is_valid(tree)); + CHECK(doomed == tree->root); + CHECK(NULL != doomed->left); + CHECK(NULL != doomed->right); + CHECK(doomed == rb_tree_lookup(tree, target)); + mem_retain(doomed); + rb_tree_delete(tree, target); + CHECK(1 == mem_num_references(doomed)); + CHECK(NULL == rb_tree_lookup(tree, target)); + CHECK(NULL == doomed->parent); + CHECK(NULL == doomed->left); + CHECK(NULL == doomed->right); + CHECK(OK == rb_tree_is_valid(tree)); + mem_release(doomed); + mem_release(tree); + } } -- 2.55.0