Want to view this project? In-Memory Record Database
Creating the Insert Functionality
Most of what we’ll implement is pretty standard as far as AVL trees go with some exceptions. If you follow along with GeeksforGeeks’ implementation in C/C++, it’s a pretty good starting point. Like I said before though, we have to make this work with any of our AVL trees instead of a single key. I’m going to use the insert operation as my example for this section since that’s where most of the fun is.
We’re going to make our public facing insert function rather small. You can do something like this:
enum InsertResult insert(struct RecordAVLTree *tree, struct Record *record)
{
enum InsertResult result = INSERT_SUCCESS;
tree->root = insertInternal(tree->root, record, tree->comparator, &result);
return result;
}
I’m not going over the enums since it isn’t too important to the overall functionality. You can return anything as long as you have proper error handling.
Okay, so what is insertInternal then? That’s where most of our insert function resides.
static struct RecordNode *insertInternal(struct RecordNode *root, struct Record *recordToInsert, RecordComparator comparator, enum InsertResult *result)
{
// Create root if it doesn't exist
if (root == NULL)
{
struct RecordNode *newRecordNode = createNode(recordToInsert);
if (newRecordNode == NULL)
{
*result = INSERT_MEMORY_ERROR;
return NULL;
}
else
{
root = newRecordNode;
*result = INSERT_SUCCESS;
return root;
}
}
int recordCompareResult = comparator(recordToInsert, root->record);
// If root does exist, figure out where it belongs
// Duplicate IDs are not allowed since we want unique IDs
if (recordCompareResult < 0)
{
root->left = insertInternal(root->left, recordToInsert, comparator, result);
}
else if (recordCompareResult > 0)
{
root->right = insertInternal(root->right, recordToInsert, comparator, result);
}
else
{
*result = INSERT_DUPLICATE;
}
root = rebalanceTree(root);
return root;
}
Let’s take it one step at a time when it comes to this function.
// Create root if it doesn't exist
if (root == NULL)
{
struct RecordNode *newRecordNode = createNode(recordToInsert);
if (newRecordNode == NULL)
{
*result = INSERT_MEMORY_ERROR;
return NULL;
}
else
{
root = newRecordNode;
*result = INSERT_SUCCESS;
return root;
}
}
First, we’re checking if the root node is null and creating a node using the struct Record *recordToInsert parameter. The rest is typical error handling. You can make this portion as complicated as you want. I think this is fine for now. The createNode function is straightforward and doesn’t stray away from a typical implementation.
struct RecordNode *createNode(struct Record *record)
{
struct RecordNode *recordNode = malloc(sizeof(*recordNode));
if (recordNode == NULL)
{
return NULL;
}
recordNode->record = record;
recordNode->left = NULL;
recordNode->right = NULL;
recordNode->nodeHeight = 1;
return recordNode;
}
So now we’re onto this bit of code and we can finally talk about what RecordComparator is actually used for.
RecordComparator is, of course, a function pointer. We’re looking for functions that contain two const struct Record*s and returning an int.
typedef int (*RecordComparator)(const struct Record *, const struct Record *);
But why have this at all? If you recall earlier, we indexed all four columns which means we have four different trees to balance: an ID tree, a first name tree, a last name tree, and an age tree. Comparing by ID is easy since each ID is unique.
int compareById(const struct Record *recordA, const struct Record *recordB)
{
if (recordA->id < recordB->id)
{
return -1;
}
else if (recordA->id == recordB->id)
{
return 0;
}
else
{
return 1;
}
}
But what happens when we try to compare by first name and there’s two of the same first name? We’ll have to pair our non-ID comparisons with the ID column if there’s a match. Let’s look at our implementation of this for the first name column.
int compareByFirstName(const struct Record *recordA, const struct Record *recordB)
{
int result = strcmp(recordA->firstName, recordB->firstName);
if (result < 0)
{
return -1;
}
else if (result == 0)
{
return compareById(recordA, recordB);
}
else
{
return 1;
}
}
We’ll use strcmp() on the two records’ first name value as you probably guessed. If the names match, then we’ll compare the ID. You can just as easily compare by something else like last name or age if you wanted to, but I’ll keep mine simple and compare based on the ID. We’ll repeat this process for both last name and age.
So now we have our compare functions which can be associated with the corresponding AVL tree when we initialize them.
void initializeRecordTable(struct RecordTable *table)
{
table->idTree.root = NULL;
table->idTree.comparator = compareById;
table->firstNameTree.root = NULL;
table->firstNameTree.comparator = compareByFirstName;
table->lastNameTree.root = NULL;
table->lastNameTree.comparator = compareByLastName;
table->ageTree.root = NULL;
table->ageTree.comparator = compareByAge;
}
Let’s go back to our insert function…
enum InsertResult insert(struct RecordAVLTree *tree, struct Record *record)
{
enum InsertResult result = INSERT_SUCCESS;
tree->root = insertInternal(tree->root, record, tree->comparator, &result);
return result;
}
Because our struct RecordAVLTree has a comparator function, we can use that inside of insertInternal which is where we get this line from.
int recordCompareResult = comparator(recordToInsert, root->record);
And just like that, we’ve turned struct RecordNode into our “key” which can be used in nearly the same way as most implementations show. If the recordCompareResult is -1, then the recordToInsert goes towards the left. If it’s 1, then it goes towards the right. If it’s 0, then we’ve hit a duplicate and do whatever it is we need to do. For my implementation, I’m simply setting my *result to an enum value: INSERT_DUPLICATE.
if (recordCompareResult < 0)
{
root->left = insertInternal(root->left, recordToInsert, comparator, result);
}
else if (recordCompareResult > 0)
{
root->right = insertInternal(root->right, recordToInsert, comparator, result);
}
else
{
*result = INSERT_DUPLICATE;
}
After that, we rebalance the tree and return the root. I won’t go into detail about it since there’s really no difference between this and your standard implementation, but I’ll show the code just in case you don’t feel like checking out the project.
root = rebalanceTree(root);
return root;
}
struct RecordNode *rebalanceTree(struct RecordNode *root)
{
if (root == NULL)
{
return root;
}
// Update height
root->nodeHeight = 1 + max(getNodeHeight(root->left), getNodeHeight(root->right));
// Check if tree is unbalanced
int balance = getBalanceFactor(root);
// LEFT HEAVY TREE
// Left Left case
if (balance > 1 && getBalanceFactor(root->left) >= 0)
{
root = rightRotate(root);
}
// Left Right case
if (balance > 1 && getBalanceFactor(root->left) < 0)
{
root->left = leftRotate(root->left);
root = rightRotate(root);
}
// RIGHT HEAVY TREE
// Right Right case
if (balance < -1 && getBalanceFactor(root->right) <= 0)
{
root = leftRotate(root);
}
// Right Left case
if (balance < -1 && getBalanceFactor(root->right) > 0)
{
root->right = rightRotate(root->right);
root = leftRotate(root);
}
return root;
}
int getNodeHeight(struct RecordNode *recordNode)
{
if (recordNode == NULL)
{
return 0;
}
return recordNode->nodeHeight;
}
int getBalanceFactor(struct RecordNode *recordNode)
{
if (recordNode == NULL)
{
return 0;
}
return getNodeHeight(recordNode->left) - getNodeHeight(recordNode->right);
}
int max(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
struct RecordNode *rightRotate(struct RecordNode *recordNode)
{
struct RecordNode *leftRecordNode = recordNode->left;
struct RecordNode *temp_LeftRecordNodesRightNode = leftRecordNode->right;
// Perform rotation
leftRecordNode->right = recordNode;
recordNode->left = temp_LeftRecordNodesRightNode;
// Update heights
recordNode->nodeHeight = max(getNodeHeight(recordNode->left), getNodeHeight(recordNode->right)) + 1;
leftRecordNode->nodeHeight = max(getNodeHeight(leftRecordNode->left), getNodeHeight(leftRecordNode->right)) + 1;
return leftRecordNode;
}
struct RecordNode *leftRotate(struct RecordNode *recordNode)
{
struct RecordNode *rightRecordNode = recordNode->right;
struct RecordNode *temp_RightRecordNodesLeftNode = rightRecordNode->left;
// Perform rotation
rightRecordNode->left = recordNode;
recordNode->right = temp_RightRecordNodesLeftNode;
// Update heights
recordNode->nodeHeight = max(getNodeHeight(recordNode->left), getNodeHeight(recordNode->right)) + 1;
rightRecordNode->nodeHeight = max(getNodeHeight(rightRecordNode->left), getNodeHeight(rightRecordNode->right)) + 1;
return rightRecordNode;
}
We can then wrap this all together inside of a new createRecord function. There’s a few other function calls in here (specifically getNextId and treeRollback) that we’ll go over in the next few articles. This function inserts the record that a user creates into each tree. If any insert fails, we'll rollback the other trees appropriately. Notice also upon rolling back all of the trees, we free up the memory that was allocated for this new record.
enum InsertResult createRecord(struct RecordTable *table, const char *firstName, const char *lastName, int age)
{
int nextId = getNextId(table);
if (nextId == -1)
{
return INSERT_FAILED_GENERIC;
}
struct Record *record = malloc(sizeof(*record));
if (record == NULL)
{
return INSERT_MEMORY_ERROR;
}
record->id = nextId;
strcpy(record->firstName, firstName);
strcpy(record->lastName, lastName);
record->age = age;
enum InsertResult idTreeInsert = insert(&table->idTree, record);
if (idTreeInsert != INSERT_SUCCESS)
{
free(record);
return idTreeInsert;
}
enum InsertResult firstNameTreeInsert = insert(&table->firstNameTree, record);
if (firstNameTreeInsert != INSERT_SUCCESS)
{
enum InsertResult idRollback = treeRollback(&table->idTree, record);
if (idRollback == INSERT_FAILED_CORRUPTED)
{
return INSERT_FAILED_CORRUPTED;
}
free(record);
return firstNameTreeInsert;
}
enum InsertResult lastNameTreeInsert = insert(&table->lastNameTree, record);
if (lastNameTreeInsert != INSERT_SUCCESS)
{
enum InsertResult firstNameRollback = treeRollback(&table->firstNameTree, record);
if (firstNameRollback == INSERT_FAILED_CORRUPTED)
{
return INSERT_FAILED_CORRUPTED;
}
enum InsertResult idRollback = treeRollback(&table->idTree, record);
if (idRollback == INSERT_FAILED_CORRUPTED)
{
return INSERT_FAILED_CORRUPTED;
}
free(record);
return lastNameTreeInsert;
}
enum InsertResult ageTreeInsert = insert(&table->ageTree, record);
if (ageTreeInsert != INSERT_SUCCESS)
{
enum InsertResult lastNameRollback = treeRollback(&table->lastNameTree, record);
if (lastNameRollback == INSERT_FAILED_CORRUPTED)
{
return INSERT_FAILED_CORRUPTED;
}
enum InsertResult firstNameRollback = treeRollback(&table->firstNameTree, record);
if (firstNameRollback == INSERT_FAILED_CORRUPTED)
{
return INSERT_FAILED_CORRUPTED;
}
enum InsertResult idRollback = treeRollback(&table->idTree, record);
if (idRollback == INSERT_FAILED_CORRUPTED)
{
return INSERT_FAILED_CORRUPTED;
}
free(record);
return ageTreeInsert;
}
return INSERT_SUCCESS;
}
Alright! Now we've got the ability to insert records into our record table. So let's tackle removing records next.