I am trying to encode an AVL binary tree in the C language. My implementation uses an over-arching struct to keep track of the length of the binary tree (i.e. number of nodes), as well as a pointer t the root, and the init status of the data structure. I have been able to encode an implementation correctly balances the tree at every insertion. However, I am having problems balancing the tree when I delete a node. I am trying to use an example listed on GeeksforGeeks (https://www.geeksforgeeks.org/deletion-in-an-avl-tree/) and I am consistently getting an incorrect answer. The problem must be in the delete_int8_node function, but i cannot see where. Unfortunately the example is lengthy, as several functions are required to provide a working example. Any help would be appreciated.
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdbool.h>
typedef struct int8_btree {
int8_t key;
struct int8_btree *left;
struct int8_btree *right;
int height;
} int8_btree;
typedef struct {
size_t active_length;
struct int8_btree *root;
bool status;
} Int8BT
void init_int8_btree(Int8BT *tree) {
tree->active_length = 0;
tree->root = NULL;
tree->status = true;
}
// ================================================================================
// ================================================================================
// NEW_TYPE_NODE (PRIVATE FUNCTIONS)
int8_btree *new_int8_node(int8_t key) {
struct int8_btree *node = malloc(sizeof(int8_btree));
if (node == NULL) return node;
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
// ================================================================================
// ================================================================================
// TYPE_NODE_HEIGHT FUNCTIONS (PRIVAT FUNCTIONS)
int int8_node_height(int8_btree *node) {
if (node == NULL) return 0;
return node->height;
}
// ================================================================================
// ================================================================================
// MAX_TYPE_NUM FUNCTION (PRIVATE FUNCTIONS)
int max_num(int a, int b) {
return (a > b)? a : b;
}
// ================================================================================
// ================================================================================
// RIGHT_TYPE_ROTATE FUNCTIONS (PRIVATE FUNCTIONS)
int8_btree *right_int8_rotate(int8_btree * y) {
struct int8_btree *x = y->left;
struct int8_btree *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
x->height = max_num(int8_node_height(y->left), int8_node_height(y->right)) + 1;
y->height = max_num(int8_node_height(x->left), int8_node_height(x->right)) + 1;
return x;
}
// ================================================================================
// ================================================================================
// LEFT_STRING_ROTATE FUNCTIONS (PRIVATE FUNCTIONS)
int8_btree *left_int8_rotate(int8_btree *x) {
struct int8_btree *y = x->right;
struct int8_btree *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
x->height = max_num(int8_node_height(x->left), int8_node_height(x->right)) + 1;
y->height = max_num(int8_node_height(y->left), int8_node_height(y->right)) + 1;
return y;
}
// ================================================================================
// ================================================================================
// TYPE_NODE_BALANCE FUNCTION (PRIVATE FUNCTIONS)
int int8_node_balance(int8_btree *node) {
if (node == NULL) return 0;
return int8_node_height(node->left) - int8_node_height(node->right);
}
// ================================================================================
// ================================================================================
// PUSH_TYPE_BTREE FUNCTION (PRIVATE FUNCTIONS)
int8_btree *insert_int8_btree(int8_btree *node, int8_t key) {
/* 1. Perform the normal BST insertion */
if (node == NULL)
return new_int8_node(key);
if (key < node->key)
node->left = insert_int8_btree(node->left, key);
else if (key > node->key)
node->right = insert_int8_btree(node->right, key);
else // Equal keys are not allowed in BST
return node;
/* 2. Update height of this ancestor node */
node->height = 1 + max_num(int8_node_height(node->left),
int8_node_height(node->right));
/* 3. Get the balance factor of this ancestor
node to check whether this node became
unbalanced */
short int balance = int8_node_balance(node);
// If this node becomes unbalanced, then
// there are 4 cases
// Left Left Case
if (balance > 1 && key < node->left->key)
return right_int8_rotate(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
return left_int8_rotate(node);
// Left Right Case
if (balance > 1 && key > node->left->key)
{
node->left = left_int8_rotate(node->left);
return right_int8_rotate(node);
}
// Right Left Case
if (balance < -1 && key < node->right->key)
{
node->right = right_int8_rotate(node->right);
return left_int8_rotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
// ================================================================================
// ================================================================================
// PUSH_TYPE_BTREE FUNCTIONS
int push_int8_btree(Int8BT *btree, int8_t key) {
if (btree->status != true) {
fprintf(stderr, "Binary tree struct not initializex\n");
return -1;
}
btree->root = insert_int8_btree(btree->root, key);
if (btree->root == NULL) {
fprintf(stderr, "Malloc failed in file %s on line %d\n", __FILE__, __LINE__);
return -1;
}
btree->active_length += 1;
return 1;
}
// ================================================================================
// ================================================================================
// FREETYPE_FUNCTIONS (PRIVATE FUNCTIONS)
void freeint8(int8_btree *root) {
if (root == NULL) return;
freeint8(root->right);
freeint8(root->left);
free(root);
}
// ================================================================================
// ================================================================================
// FREE_TYPE_BTREE FUNCTIONS
void free_int8_btree(Int8BT *btree) {
if (btree->status != true) {
fprintf(stderr, "Unitialized binary tree struct cannot be freed\n");
return;
}
freeint8(btree->root);
}
// ================================================================================
// ================================================================================
// MIN_TYPE_NODE (PRIVATE FUNCTIONS)
int8_btree *min_int8_node(int8_btree *root) {
struct int8_btree *current = root;
while (current->left != NULL) {
current = current->left;
}
return current;
}
// ================================================================================
// ================================================================================
// DELETE_TYPE_NODE (PRIVATE FUNCTIONS)
int8_btree *delete_int8_node(int8_btree *root, int8_t key) {
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;
// If the key to be deleted is smaller than the
// root's key, then it lies in left subtree
if ( key < root->key )
root->left = delete_int8_node(root->left, key);
// If the key to be deleted is greater than the
// root's key, then it lies in right subtree
else if( key > root->key )
root->right = delete_int8_node(root->right, key);
// if key is same as root's key, then This is
// the node to be deleted
else
{
// node with only one child or no child
if( (root->left == NULL) || (root->right == NULL) )
{
struct int8_btree *temp = root->left ? root->left :
root->right;
// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
struct int8_btree* temp = min_int8_node(root->right);
// Copy the inorder successor's data to this node
root->key = temp->key;
// Delete the inorder successor
root->right = delete_int8_node(root->right, temp->key);
}
}
// If the tree had only one node then return
if (root == NULL)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = 1 + max_num(int8_node_height(root->left),
int8_node_height(root->right));
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to
// check whether this node became unbalanced)
short int balance = int8_node_balance(root);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && int8_node_balance(root->left) >= 0)
return right_int8_rotate(root);
// Left Right Case
if (balance > 1 && int8_node_balance(root->left) < 0)
{
root->left = left_int8_rotate(root->left);
return right_int8_rotate(root);
}
// Right Right Case
if (balance < -1 && int8_node_balance(root->right) <= 0)
return left_int8_rotate(root);
// Right Left Case
if (balance < -1 && int8_node_balance(root->right) > 0)
{
root->right = right_int8_rotate(root->right);
return left_int8_rotate(root);
}
return root;
}
// ================================================================================
// ================================================================================
// POP_TYPE_BTREE FUNCTIONS
void pop_int8_btree(Int8BT *btree, int8_t key) {
btree->root = delete_int8_node(btree->root, key);
btree->active_length -= 1;
//if (btree->status != true) {
// fprintf(stderr, "Cannon pop binary tree struct that is not initialized\n");
// return;
//}
//struct int8_btree *current = btree->root;
//btree->root = delete_int8_node(btree->root, key);
//if (btree->root == current && btree->root != NULL) btree->active_length -= 1;
}
void print_preorder(int8_btree *root)
{
if(root != NULL)
{
printf("%d ", root->key);
print_preorder(root->left);
print_preorder(root->right);
}
}
// --------------------------------------------------------------------------------
void print_int8_tree(Int8BT *tree) {
print_preorder(tree->root);
printf("\n");
}
// --------------------------------------------------------------------------------
void test_repeat_int8_list(void **state) {
Int8BT tree;
init_int8_btree(&tree);
push_int8_btree(&tree, 9);
push_int8_btree(&tree, 5);
push_int8_btree(&tree, 10);
push_int8_btree(&tree, 0);
push_int8_btree(&tree, 6);
push_int8_btree(&tree, 11);
push_int8_btree(&tree, -1);
push_int8_btree(&tree, 1);
push_int8_btree(&tree, 2);
print_int8_tree(&tree);
// Correctly prints 9 1 0 -1 5 2 6 10 11
pop_int8_btree(&tree, 10);
print_int8_tree(&tree);
// Incorrectly prints 9 1 0 -1 5 2 6 11
// Should print 1 0 -1 9 5 2 6 11
free_int8_btree(&tree);
}
