删除

Coddy AVL 树：数据结构系列 #10 课程的第 11 课，共 16 课。

删除操作是 BST 删除，只是沿用和插入相同的平衡调整方式。要处理被删除节点的三种情况：没有子节点（直接删除），有一个子节点（用该子节点替换它），或者有两个子节点，这是比较棘手的情况。此时，用它的中序后继（右子树中的最小值）替换该节点的值，然后从右子树中删除这个后继节点。

和插入一样，沿着返回路径上的每个祖先节点都会重新计算高度和平衡因子，如果节点变得不平衡，就应用相应的旋转情况。平衡调整逻辑与插入完全相同，只有选择旋转情况的条件不同：现在要查看较重子节点的平衡因子，而不是查看新值插入的位置。

挑战

中等

在 AVLTree 上编写一个 delete(value) 方法（递归辅助函数会很有帮助）。使用标准的 BST 删除方式移除 value：对于有两个子节点的节点，将它的值替换为其右子树中的最小值，然后从右子树中删除该值。如果找不到 value，则不做任何操作。递归返回时，重新计算高度，并像 insert 那样重新平衡。

亲手试试

#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;
}

AVL 树：数据结构系列 #10中的所有课

1简介

2AVL 树项目

删除

3挑战练习

第 k 小的元素区间和最近公共祖先层序遍历某个值的后继

自己练习： C 在线编译器