Implementing a AVL tree in C

Question

I am attempting to implement an array into a BST, after printing out the BST(pre-order), I am balancing it out (AVL tree with pre-order output).

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
    int height;
};

struct node *new_node(int data) {
    struct node *nn = (struct node *)malloc(sizeof(struct node));
    nn->data = data;
    nn->left = NULL;
    nn->right = NULL;
    nn->height = 1;

    return nn;
}

struct node *insert(struct node *root, int data) {
    if (root == NULL)
        return new_node(data);
    else {
        if (data < root->data)
            root->left = insert(root->left, data);
        if (data > root->data)
            root->right = insert(root->right, data);
        return root;
    }
}

void pre_order(struct node *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        pre_order(root->left);
        pre_order(root->right);
    }
}

int height(struct node *n) { 
    if (n == NULL) 
        return 0; 
    return n->height; 
} 

int max(int a, int b) 
{ 
    return (a > b) ? a : b; 
} 

struct node *rightRotate(struct node *y) 
{ 
    struct node *x = y->left; 
    struct node *T2 = x->right; 

    x->right = y; 
    y->left = T2; 

    y->height = max(height(y->left), height(y->right)) + 1; 
    x->height = max(height(x->left), height(x->right)) + 1; 

    return x; 
} 

struct node *leftRotate(struct node *x) { 
    struct node *y = x->right; 
    struct node *T2 = y->left; 

    y->left = x; 
    x->right = T2; 

    x->height = max(height(x->left), height(x->right)) + 1; 
    y->height = max(height(y->left), height(y->right)) + 1; 

    return y; 
} 

int getBalance(struct node *n) { 
    if (n == NULL) 
        return 0; 
    return height(n->left) - height(n->right); 
} 

struct node *AVLbalance(struct node *root, int data) 
{ 
    root->height = 1 + max(height(root->left), 
                           height(root->right)); 

    int balance = getBalance(root); 

    // Left Left Case 
    if (balance > 1 && data < root->left->data) 
        return rightRotate(root); 

    // Right Right Case 
    if (balance < -1 && data > root->right->data) 
        return leftRotate(root); 

    // Left Right Case 
    if (balance > 1 && data > root->left->data) 
    { 
        root->left = leftRotate(root->left); 
        return rightRotate(root); 
    } 

    // Right Left Case 
    if (balance < -1 && data < root->right->data) 
    { 
        root->right = rightRotate(root->right); 
        return leftRotate(root); 
    } 

    return root; 
} 

int main() {
    struct node *root = NULL;

    int arr[] = { 5, 7, 2, 4, 6 };
    int n = sizeof(arr) / sizeof(arr[0]); 

    for (int i = 0; i < n; i++)
        root = insert(root, arr[i]);

    printf("BST Pre-order:\n");
    pre_order(root);

    for (int j = 0; j < n; j++)
       root = AVLbalance(root, arr[j]);
        
    printf("\nBalanced (AVL) Pre-order:\n");
    pre_order(root);

    return 0;
}

After trying for hours, I cannot tell if the tree is balancing itself when being called for. Is there a logical error? Program compiles without any warning or errors. HELP!

Answer 1

The main problem is you rely on nn->height to balance the tree but do not update the node heights when you insert new nodes.

You could modify the insertion function this way:

struct node *insert(struct node *root, int data) {
    if (root == NULL)
        return new_node(data);
    else {
        if (data < root->data)
            root->left = insert(root->left, data);
        if (data > root->data)
            root->right = insert(root->right, data);
        root->height = max(height(root->left), height(root->right)) + 1;
        return root;
    }
}

But this would not suffice: the function AVLbalance only handles the root node of the tree so rebalancing the tree after inserting all values does not work.

You should rebalance the subtree in the insert function when you detect an imbalance, ie when inserting data in a subtree increases the height of the subtree beyond the length of the other subtree + 1. Keeping the height of each node is overkill for this. A single bit per subtree indicating it is already higher than its sibling should suffice to detect the need for rebalancing in insert and keep the tree balanced at all times.

Here is a naive implementation of the insert function that rebalances the tree upon insertion:

struct node *insert(struct node *root, int data) 
{ 
    if (root == NULL) 
        return new_node(data); 
  
    if (data < root->data) 
        root->left  = insert(root->left, data); 
    else if (data > root->data) 
        root->right = insert(root->right, data); 
    else
        return root; 
  
    root->height = 1 + max(height(root->left), 
                           height(root->right)); 
  
    // Handle 4 potential cases of imbalance:
    int balance = height(root->left) - height(root->right); 
    if (balance > 1) {
        if (data < root->left->data) {
            // Left Left Case 
            return rightRotate(root); 
        }
        if (data > root->left->data) {
            // Left Right Case 
            root->left = leftRotate(root->left); 
            return rightRotate(root); 
        }
    } else
    if (balance < -1) {
        if (data < root->right->data) {
            // Right Left Case 
            root->right = rightRotate(root->right); 
            return leftRotate(root); 
        } 
        if (data > root->right->data) {
            // Right Right Case 
            return leftRotate(root); 
        }
    }
    // No imbalance
    return root; 
} 

Answer 2

You over-interpret self-balancing.

Self-balancing search tree means that for client code using "the usual interface routines" is enough to keep the tree balanced.

It does not mean balance is kept without coding it in the tree routines.
It is not enough to keep in each node information potentially instrumental in keeping/restoring balance:
balance needs to be guaranteed at the end of each modifying operation
(insert, delete, union/merge, split …).