Delete

Lesson 11 of 16 in Coddy's AVL Tree - Data Structures Series #10 course.

Deleting is BST delete with the same rebalancing habit as insert. Three shapes to handle for the node being removed: no children (just remove it), one child (replace it with that child), or two children, the tricky case, where you replace the node's value with its in-order successor (the smallest value in its right subtree) and then delete that successor from the right subtree instead.

Just like insert, every ancestor on the way back up recomputes its height and balance factor, applying whichever rotation case fits if it becomes unbalanced. The rebalancing logic is identical to insert, only the condition for choosing which case now looks at the balance factor of the heavy child instead of where a new value landed.

Challenge

Medium

Write a method delete(value) on AVLTree (a recursive helper works well). Remove value using standard BST delete: for a node with two children, replace its value with the smallest value in its right subtree, then delete that value from the right subtree. Do nothing if value isn't found. On the way back up, recompute heights and rebalance exactly like insert does.

Try it yourself

#include <stdio.h>
#include <string.h>
#include "avltree.h"

static void preorderValues(Node* node, int* vals, int* count) {
    if (node == NULL) {
        return;
    }
    vals[(*count)++] = node->value;
    preorderValues(node->left, vals, count);
    preorderValues(node->right, vals, count);
}

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        char cmd[32];
        int arg;
        int parsed = sscanf(line, "%31s %d", cmd, &arg);
        if (parsed >= 1 && strcmp(cmd, "insert") == 0) {
            AVLTree_insert(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "delete") == 0) {
            AVLTree_delete(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "search") == 0) {
            if (AVLTree_search(tree, arg)) {
                printf("true\n");
            }
            if (!AVLTree_search(tree, arg)) {
                printf("false\n");
            }
        }
        if (parsed >= 1 && strcmp(cmd, "preorder") == 0) {
            int vals[10000];
            int count = 0;
            preorderValues(tree->root, vals, &count);
            for (int i = 0; i < count; i++) {
                if (i > 0) {
                    printf(" ");
                }
                printf("%d", vals[i]);
            }
            printf("\n");
        }
    }
    return 0;
}