Want to view this project? In-Memory Record Database
Creating the Delete Functionality
Deleting records from our record table will look very similar to our insert functions. We left off taking a look at createRecord which calls the treeRollback function which gets called if, for whatever reason, a record fails to be inserted in one of the AVL trees. We wouldn’t want a Record to be pointed to in the ID tree, but not in the first name tree otherwise, our entire table would be corrupted. Let’s take a look at treeRollback now:
static enum InsertResult treeRollback(struct RecordAVLTree *tree, struct Record *record)
{
enum DeleteResult treeRollback = deleteNode(tree, record);
if (treeRollback != DELETE_SUCCESS)
{
printf("*** ERROR: DATABASE TREES CORRUPTED ***\n");
return INSERT_FAILED_CORRUPTED;
}
return INSERT_ROLLBACK_SUCCESS;
}
Fairly straightforward, right? As you can see, if we fail to delete a node we simply return the enum INSERT_FAILED_CORRUPTED which gets carried back up to createRecord. For the sake of this exercise, I’m simply leaving it like this since we can conclude that if our deleteNode function fails somewhere along the way, then we’ve got a serious problem. Since it’s an in-memory database, I’m not too concerned if I have to close out of the program and reopen. The entire program is meant to only contain temporary data after all. If I was implementing this for secondary storage, then we’d be adding a lot more safeguards.
Okay that’s all well and good, so what does deleteNode consist of? We’re pretty much doing the same concept as we did for insert and insertInternal.
enum DeleteResult deleteNode(struct RecordAVLTree *tree, const struct Record *recordToDelete)
{
enum DeleteResult result = DELETE_FAILED;
tree->root = deleteNodeInternal(tree->root, recordToDelete, tree->comparator, &result);
return result;
}
static struct RecordNode *deleteNodeInternal(struct RecordNode *root, const struct Record *recordToDelete, RecordComparator comparator, enum DeleteResult *result)
{
if (root == NULL)
{
*result = DELETE_FAILED;
return NULL;
}
int recordCompareResult = comparator(recordToDelete, root->record);
if (recordCompareResult < 0)
{
root->left = deleteNodeInternal(root->left, recordToDelete, comparator, result);
}
else if (recordCompareResult > 0)
{
root->right = deleteNodeInternal(root->right, recordToDelete, comparator, result);
}
else
{
// Record has 1 child or no children records
if ((root->left == NULL) || (root->right == NULL))
{
struct RecordNode *tempNode;
// Record has a left child
if (root->left != NULL)
{
tempNode = root->left;
}
// Record has a right child
else
{
tempNode = root->right;
}
// No children were found for the record to delete
if (tempNode == NULL)
{
tempNode = root;
root = NULL;
*result = DELETE_SUCCESS;
free(tempNode);
}
// At least 1 child was found for the record to delete, return that child record
else
{
free(root);
*result = DELETE_SUCCESS;
return tempNode;
}
}
// Record has 2 children
else
{
// Find minimum value
struct RecordNode *tempNode = minValueRecordNode(root->right);
// Overwrite the current root's record
root->record = tempNode->record;
*result = DELETE_SUCCESS;
// Now, look for the duplicate record to delete. We just assigned this to the current root
root->right = deleteNodeInternal(root->right, tempNode->record, comparator, result);
}
}
root = rebalanceTree(root);
return root;
}
Same thing as before. Let’s go through this code starting with the NULL check. If the root is NULL, simply return NULL and do whatever else you’d like. The reason I’m okay with setting *result to DELETE_FAILED is because later on when we set up the console UI, I’m making it a requirement that you MUST have the ID of the record you want to delete. So if you managed to get here without specifying a valid ID then… uh… good work, I guess, but now our table is going to come back as corrupted. :)
Like I said before, feel free to make this as complicated as you wish.
if (root == NULL)
{
*result = DELETE_FAILED;
return NULL;
}
Then we’ll use our comparator function like we did in insertInternal:
int recordCompareResult = comparator(recordToDelete, root->record);
if (recordCompareResult < 0)
{
root->left = deleteNodeInternal(root->left, recordToDelete, comparator, result);
}
else if (recordCompareResult > 0)
{
root->right = deleteNodeInternal(root->right, recordToDelete, comparator, result);
}
Next is the else block that contains most of the logic for navigating the tree. Let’s start with the first nested if block. This block checks if the RecordNode* we’re deleting has 1 or no children records. If a child exists, we determine if it’s a left child or right child, free the memory of the RecordNode* to delete, and return the child. If no children exist, we simply set the RecordNode* to NULL and free it from memory. Note that we are freeing the RecordNode* and NOT the Record* itself.
else
{
// Record has 1 child or no children records
if ((root->left == NULL) || (root->right == NULL))
{
struct RecordNode *tempNode;
// Record has a left child
if (root->left != NULL)
{
tempNode = root->left;
}
// Record has a right child
else
{
tempNode = root->right;
}
// No children were found for the record to delete
if (tempNode == NULL)
{
tempNode = root;
root = NULL;
*result = DELETE_SUCCESS;
free(tempNode);
}
// At least 1 child was found for the record to delete, return that child record
else
{
free(root);
*result = DELETE_SUCCESS;
return tempNode;
}
}
Finally, let’s take a look at the else block that handles the event of a RecordNode* having 2 children.
// Record has 2 children
else
{
// Find minimum value
struct RecordNode *tempNode = minValueRecordNode(root->right);
// Overwrite the current root's record
root->record = tempNode->record;
*result = DELETE_SUCCESS;
// Now, look for the duplicate record to delete. We just assigned this to the current root
root->right = deleteNodeInternal(root->right, tempNode->record, comparator, result);
}
We’ll first use minValueRecordNode on the RecordNode*’s right child to find the next smallest record in the tree that still follows the typical binary search tree rules.
struct RecordNode *minValueRecordNode(struct RecordNode *rootRecordNode)
{
struct RecordNode *current = rootRecordNode;
while (current->left != NULL)
{
current = current->left;
}
return current;
}
Visualizing this concept is relatively straightforward. Assuming the node we’re wanting to delete is 50, minValueRecordNode would take 70 as an argument and eventually trickle down to return 55 to struct RecordNode *tempNode.
Our struct RecordNode*’s struct Record* would then be overwritten by *tempNode’s struct Record*. In our visualization, we should now have this.
At this point, I’m setting *result to DELETE_SUCCESS, but you can do it after we delete the original node we just copied. I should probably do that too, come to think of it.
Anyways, the last thing we’ll do is delete the original node we just copied! After that’s done, our tree should look something like this:
To wrap up the deleteInternal function, we simply rebalance the tree and return the root. The code for rebalanceTree was given in part 3 if you’d like to take a look. It doesn’t differ much from your standard implementation.
The way we found the node to copy is known as the in-order successor. Had we have gone down the left child and then had something like this:
struct RecordNode *current = rootRecordNode;
while (current->right != NULL)
{
current = current->right;
}
return current;
We would have been trying to find the in-order predecessor. Either implementation is valid, I just liked this way better.
Time to wrap up this article with the deleteRecord function. This function, just like createRecord has another function being called that I won’t touch on in this article. Don’t worry though, because we’ll go over both of them in the next part!
enum DeleteResult deleteRecord(struct RecordTable *table, int id)
{
struct Record *recordToDelete = findRecordById(table, id);
if (recordToDelete == NULL)
{
return DELETE_FAILED;
}
struct Record *firstNameRecord = findRecord(&table->firstNameTree, recordToDelete);
struct Record *lastNameRecord = findRecord(&table->lastNameTree, recordToDelete);
struct Record *ageRecord = findRecord(&table->ageTree, recordToDelete);
if (firstNameRecord != recordToDelete || lastNameRecord != recordToDelete || ageRecord != recordToDelete)
{
return DELETE_CORRUPTED;
}
enum DeleteResult idTreeDeleteResult = deleteNode(&table->idTree, recordToDelete);
enum DeleteResult firstNameTreeDeleteResult = deleteNode(&table->firstNameTree, recordToDelete);
enum DeleteResult lastNameTreeDeleteResult = deleteNode(&table->lastNameTree, recordToDelete);
enum DeleteResult ageTreeDeleteResult = deleteNode(&table->ageTree, recordToDelete);
if (idTreeDeleteResult == DELETE_SUCCESS && firstNameTreeDeleteResult == DELETE_SUCCESS &&
lastNameTreeDeleteResult == DELETE_SUCCESS && ageTreeDeleteResult == DELETE_SUCCESS)
{
free(recordToDelete);
return DELETE_SUCCESS;
}
return DELETE_FAILED;
}
The first thing we’ll do is find the record we want to delete using an ID that the user will enter. If we find that record, then we’ll want to verify it exists in all of our AVL trees because if not, then we’ve got a corrupted table.
I could probably name these
enums better.
If we located the references to our Record* we want to delete in all of the AVL trees, we’ll then proceed with deleting the RecordNode* from each of the trees. We are NOT deleting the Record* itself yet otherwise we’ll be left with dangling pointers and we don’t want that. Only after we confirm that all of the RecordNode*’s were deleted do we free the memory of the Record* itself.
We’re essentially done with the delete functionality! Now we can move onto searching and sorting.