Balanced Binary Tree Explained

1. Definition of Balanced Binary Tree

A Balanced Binary Tree, also known as an AVL tree, is a height-balanced binary search tree. Its characteristic is that for every node, the height difference between the left and right subtrees is no more than 1. Specifically, for any node (N):

$$| \text{height}(N_{\text{left}}) - \text{height}(N_{\text{right}}) | \leq 1$$

2. Balance Factor

The Balance Factor is an indicator used to measure the height difference between a node's left and right subtrees. For node (N), its balance factor is defined as:

$$\text{BF}(N) = \text{height}(N_{\text{left}}) - \text{height}(N_{\text{right}})$$

3. Operations

The operations of a balanced binary tree include insertion, deletion, and rotation. Below are detailed descriptions and C language implementations of these operations.

3.1 Insertion Operation

Inserting a node may cause the tree to become unbalanced, requiring rotation operations to restore balance.

Code Implementation:

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

// Define node structure
typedef struct AVLNode {
    int key;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;

// Get node height
int height(AVLNode *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

// Create new node
AVLNode* createNode(int key) {
    AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // New node height is 1
    return(node);
}

// Right rotation
AVLNode *rightRotate(AVLNode *y) {
    AVLNode *x = y->left;
    AVLNode *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;
}

// Left rotation
AVLNode *leftRotate(AVLNode *x) {
    AVLNode *y = x->right;
    AVLNode *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;
}

// Get node balance factor
int getBalance(AVLNode *N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

// Insert node
AVLNode* insertNode(AVLNode* node, int key) {
    if (node == NULL)
        return(createNode(key));

    if (key < node->key)
        node->left = insertNode(node->left, key);
    else if (key > node->key)
        node->right = insertNode(node->right, key);
    else // Duplicate keys not allowed
        return node;

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

    int balance = getBalance(node);

    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

3.2 Deletion Operation

Deleting a node may also cause the tree to become unbalanced, requiring rotation operations to restore balance.

Code Implementation:

// Find the minimum value node
AVLNode * minValueNode(AVLNode* node) {
    AVLNode* current = node;
    while (current->left != NULL)
        current = current->left;

    return current;
}

// Delete node
AVLNode* deleteNode(AVLNode* root, int key) {
    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if ((root->left == NULL) || (root->right == NULL)) {
            AVLNode *temp = root->left ? root->left : root->right;

            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else
                *root = *temp;
            free(temp);
        } else {
            AVLNode* temp = minValueNode(root->right);
            root->key = temp->key;
            root->right = deleteNode(root->right, temp->key);
        }
    }

    if (root == NULL)
        return root;

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

    int balance = getBalance(root);

    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

4. Rotation Operations Explained

Rotation operations maintain the balance of AVL trees. Common rotation operations include right rotation, left rotation, left-right rotation, and right-left rotation.

4.1 Right Rotation

Right rotation is a clockwise rotation on a node. Used when the balance factor is greater than 1 and the newly inserted node is in the left subtree of the left subtree.

$$\begin{array}{ccc} & y & \\ / & & \\ x & & y_{\text{right}} \\ / \\ T1 \\ \end{array} \Rightarrow \begin{array}{ccc} & x & \\ / & & \\ T1 & & y \\ / \\ y_{\text{right}} \\ \end{array}$$

4.2 Left Rotation

Left rotation is a counterclockwise rotation on a node. Used when the balance factor is less than -1 and the newly inserted node is in the right subtree of the right subtree.

$$\begin{array}{ccc} & x & \\ / & & \\ x_{\text{left}} & & y \\ / \\ T2 \\ \end{array} \Rightarrow \begin{array}{ccc} & y & \\ / & & \\ x & & T2 \\ / \\ x_{\text{left}} \\ \end{array}$$

Complete Balanced Binary Tree Code Example

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

// Define node structure
typedef struct AVLNode {
    int key;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;

// Get node height
int height(AVLNode *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

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

// Create new node
AVLNode* createNode(int key) {
    AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // New node height is 1
    return(node);
}

// Right rotation
AVLNode *rightRotate(AVLNode *y) {
    AVLNode *x = y->left;
    AVLNode *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;
}

// Left rotation
AVLNode *leftRotate(AVLNode *x) {
    AVLNode *y = x->right;
    AVLNode *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;
}

// Get node balance factor
int getBalance(AVLNode *N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

// Insert node
AVLNode* insertNode(AVLNode* node, int key) {
    if (node == NULL)
        return(createNode(key));

    if (key < node->key)
        node->left = insertNode(node->left, key);
    else if (key > node->key)
        node->right = insertNode(node->right, key);
    else // Duplicate keys not allowed
        return node;

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

    int balance = getBalance(node);

    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

// Find the minimum value node
AVLNode * minValueNode(AVLNode* node) {
    AVLNode* current = node;
    while (current->left != NULL)
        current = current->left;

    return current;
}

// Delete node
AVLNode* deleteNode(AVLNode* root, int key) {
    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if ((root->left == NULL) || (root->right == NULL)) {
            AVLNode *temp = root->left ? root->left : root->right;

            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else
                *root = *temp;
            free(temp);
        } else {
            AVLNode* temp = minValueNode(root->right);
            root->key = temp->key;
            root->right = deleteNode(root->right, temp->key);
        }
    }

    if (root == NULL)
        return root;

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

    int balance = getBalance(root);

    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

// In-order traversal of the tree
void inOrder(AVLNode *root) {
    if (root != NULL) {
        inOrder(root->left);
        printf("%d ", root->key);
        inOrder(root->right);
    }
}

// Main function
int main() {
    AVLNode *root = NULL;

    root = insertNode(root, 9);
    root = insertNode(root, 5);
    root = insertNode(root, 10);
    root = insertNode(root, 0);
    root = insertNode(root, 6);
    root = insertNode(root, 11);
    root = insertNode(root, -1);
    root = insertNode(root, 1);
    root = insertNode(root, 2);

    printf("Inorder traversal of AVL tree:\n");
    inOrder(root);

    root = deleteNode(root, 10);

    printf("\nInorder traversal of AVL tree after deleting 10:\n");
    inOrder(root);

    return 0;
}

Time and Space Complexity Analysis of Balanced Binary Tree (AVL Tree)

Time Complexity

1. Insertion Operation

   • Finding insertion position: Since AVL trees are balanced binary search trees, finding the insertion position has a time complexity of (O(\log n)).
   • Balancing operation: In the worst case, one or two rotations are needed, each with a time complexity of (O(1)). Therefore, the total time complexity of insertion is (O(\log n)).

2. Deletion Operation

   • Finding the deletion node: Similar to insertion, finding the deletion node has a time complexity of (O(\log n)).
   • Balancing operation: After deletion, multiple rotations may be needed to maintain balance, but each rotation has a time complexity of (O(1)). Therefore, the total time complexity of deletion is (O(\log n)).

3. Search Operation

   • The search operation of AVL trees is similar to ordinary binary search trees. Since the tree height is (O(\log n)), the search time complexity is (O(\log n)).

4. Rotation Operation

   • A single rotation operation has a time complexity of (O(1)), as it only involves constant-level node adjustments.

Space Complexity

1. Space Complexity
   • Each node needs to store its height information, so the space complexity per node is (O(1)).
   • The space complexity of the entire tree is (O(n)), where (n) is the number of nodes.
   • Recursive operation space complexity: Since the stack space for recursive operations is proportional to the tree height, and AVL tree height is (O(\log n)), the space complexity of recursive operations is (O(\log n)).

In summary, the time and space complexities of AVL trees are as follows:

Operation	Time Complexity	Space Complexity
Insertion	(O(\log n))	(O(1))
Deletion	(O(\log n))	(O(1))
Search	(O(\log n))	(O(1))
Rotation	(O(1))	(O(1))
Total Space	(O(n))	(O(n))
Recursive Operations	(O(\log n))	(O(\log n))

These complexities make AVL trees excellent in application scenarios requiring frequent insertion, deletion, and search operations, effectively maintaining balance and ensuring operational efficiency.